We (me and my teammate johngull) used pure C++ for solving the problem. No additional libraries were used for solving the problem (except the library for JSON parsing).

The algorithm based on the greedy approach. It takes a list of trains in some order and tried to push it one-by-one with the minimal possible score for each. As an initial order, we sorted train by entry earliest on the first station and in topological order by connections (so train that has an outcoming connection to another train, was handled first). On next iterations, we reordered all trains trying to get the better score. We have a few strategies on how to make reordering, one is fully deterministic and some are based on trains score and some random influence. But all strategies have important restrictions - doesn’t break the topological order of trains connections.

After that, we implemented a new starting sort order based on the train’s pairwise scores. So first we solved a lot of small task with each possible pair of two trains ignoring connections. And when we have these pair scores, we construct the initial train’s sort order minimizing the sum of all used pairs. This approach significantly improved the total score and calculation time.

Unfortunately, this approach not worked with task 9, because it has a lot of bi-connections (train A has a connection with train B and vice versa). So in this case impossible to make a topological sort of connections. So when we have seen the first submissions of this task last Monday, we concentrated on solving it and we have a first successful submission on Tuesday.

In this solution, we grouped all trains that have cyclic connections. So in result, we can make a topological sort of groups. Many groups had one train and were handled same as in the first approach. For complicated groups with cycles, we implemented another solver which iteratively tries to guess the arriving time of all trains to transfer stations and use it as a real one. On each iteration, this guess is improved and just with few iterations we got the correct solution for the whole group. Important note, we also added restriction to use sections with different resources on transfer station for trains with bi-connections.

Unfortunately, we haven’t time to fine-tune the solution, while we saw a lot of areas for improvement.

I received lots of errors/warnings (see below) when tried to validate the submission. But the same file was successfully graduated when I submitted it. So whats wrong with it?

There are 6 warnings and 18 errors

the solution has 18 errors. It will not be accepted as a feasible solution. See the error messages for details.

Errors: - Entry time 07:22:46 after einMax 07:02 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “18223#142” and Section Marker “TW_Halt” in service_intention “18223” - Entry time 08:02:41 after einMax 07:41 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “18223#465” and Section Marker “ZB_Halt” in service_intention “18223” - Exit time 08:02:56 after exit_latest 07:45 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “18223#465” and Section Marker “ZB_Halt” in service_intention “18223” - Entry time 07:46:04 after einMax 07:32 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “18225#142” and Section Marker “TW_Halt” in service_intention “18225” - Entry time 08:24:59 after einMax 08:11 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “18225#465” and Section Marker “ZB_Halt” in service_intention “18225” - Exit time 08:25:14 after exit_latest 08:15 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “18225#465” and Section Marker “ZB_Halt” in service_intention “18225” - Entry time 07:49:02 after einMax 07:09 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20423#142” and Section Marker “TW_Halt” in service_intention “20423” - Entry time 08:05:09 after einMax 07:25 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20423#295” and Section Marker “ZG_Halt” in service_intention “20423” - Exit time 08:05:24 after exit_latest 07:29 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20423#295” and Section Marker “ZG_Halt” in service_intention “20423” - Entry time 08:18:21 after einMax 07:55 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20425#295” and Section Marker “ZG_Halt” in service_intention “20425” - Exit time 08:18:36 after exit_latest 07:59 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20425#295” and Section Marker “ZG_Halt” in service_intention “20425” - Entry time 07:24:32 after einMax 07:09 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20424#350” and Section Marker “ZUE_Halt” in service_intention “20424” - Exit time 07:25:26 after exit_latest 07:14 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20424#350” and Section Marker “ZUE_Halt” in service_intention “20424” - Entry time 07:44:42 after einMax 07:17 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20524#740” and Section Marker “ZUE_Halt” in service_intention “20524” - Exit time 07:45:16 after exit_latest 07:25 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20524#740” and Section Marker “ZUE_Halt” in service_intention “20524” - Entry time 08:26:16 after einMax 08:17 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “20528#740” and Section Marker “ZUE_Halt” in service_intention “20528” - Entry time 08:07:10 after einMax 07:59 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “23432#585” and Section Marker “SA_Halt” in service_intention “23432” - Exit time 08:08:08 after exit_latest 08:03 (+ max. Bandabweichung PT5M) for Train run sections with route_section_id “23432#585” and Section Marker “SA_Halt” in service_intention “23432”

Warnings: - Solution with VP-Label “02_a_little_less_dummy” and problem_instance_hash “910955293” has a wrong Hash! Hash: 910955293, expected: -1078720121 - Entry time 07:49:07 after einMax 07:48 for Train run sections with route_section_id “18825#305” and Section Marker “PF_Halt” in service_intention “18825” - Entry time 08:28:04 after einMax 08:28 for Train run sections with route_section_id “20527#402” and Section Marker “ZB_Halt” in service_intention “20527” - Exit time 08:26:50 after exit_latest 08:25 for Train run sections with route_section_id “20528#740” and Section Marker “ZUE_Halt” in service_intention “20528” - Exit time 06:16:39 after exit_latest 06:16 for Train run sections with route_section_id “16920#40” and Section Marker “FRBS” in service_intention “16920” - Exit time 06:46:39 after exit_latest 06:46 for Train run sections with route_section_id “16922#40” and Section Marker “FRBS” in service_intention “16922”