ico-arrow-big-left

Marathon Match 127 - CarRacing

Key Information

Register
Submit
The challenge is finished.
Show Deadlines

Challenge Overview

Important Links

  • Submission-Review You can find your submissions artifacts here. Artifacts will contain output.txt's for both example test cases and provisional test cases with stdout/stderr and individual test case scores.
  • Other Details For other details like Processing Server Specifications, Submission Queue, Example Test Cases Execution.

Overview

You are playing with N toy cars on a race track with K lanes. You can select up to K cars and race them against each other, noting down the order that they arrive. Each car has a distinct speed and will always finish the race in the same amount of time. Your task is to correctly order all the cars from fastest to slowest in the fewest races possible.

Input and Output

This is an interactive problem, so your code needs to interact with the tester for each race. Initially your code will receive as input the following values, each on a separate line:

  • N, the number of cars.
  • K, the number of lanes on the track.

The following loop repeats until you terminate it:

  • You can race M distinct cars, where M is between 2 and K. You create a race by printing a line of M space-separated car ids (0-based): "c1 c2 ... cM" (without the quotes).
  • The tester runs your race and outputs the order that each car finished in the race. This is a line of M space-separated ranks (0-based): "r1 r2 ... rM" (without the quotes). Here r1 is the rank obtained by car c1 and so on. Lower rank means faster car.
  • You can terminate this loop once you have obtained the correct total order. This is done by printing a line of N space-separated car ids (0-based), ordered from fastest to slowest car: "c1 c2 ... cN" (without the quotes). Here c1 is the fastest car and cN is the slowest car.

Example

Here is an example solution for N=6 and K=2. The speed of each car is 4 0 2 3 1 5, where higher is faster. Note that this information is hidden from your code. This solution uses selection sort.

-Race--Cars--Result--Comments-
10 10 1Car 0 is faster than car 1
20 20 1Car 0 is faster than car 2
30 30 1Car 0 is faster than car 3
40 40 1Car 0 is faster than car 4
50 51 0Car 5 is faster than car 0, thus car 5 is the fastest
61 21 0
72 31 0
83 40 1
93 01 0Car 0 is 2nd fastest
102 31 0
113 40 1
123 10 1Car 3 is 3rd fastest
132 40 1
142 10 1Car 2 is 4th fastest
154 10 1Car 1 is the slowest

The final order found by the solution is 5 0 3 2 4 1 and this matches the true order. This solution used 15 races so it receives a raw score of 15.

Scoring

The raw score is the number of races run.

If your return was invalid, then your raw score on this test case will be -1. Possible reasons include:

  • Not formatting the races correctly or using indices that are out of bounds.
  • Not outputing the correct final order.
  • Performing more than floor(N*N/2) races.
  • Exceeding the time-limit.

If your raw score for a test case is negative then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is MIN/YOUR, where YOUR is your raw score and MIN is the smallest positive raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is normalized to 100.

Test Case Generation

Please look at the generate() method in visualizer's source code for the exact details about test case generation. Each test case is generated as follows:

  • The number of cars N is chosen between 6 and 1000, inclusive.
  • The number of lanes K is chosen between 2 and ceiling(N/4), inclusive.
  • The speed of each car is chosen, such that they are all distinct.
  • All values are chosen uniformly at random.

Notes

  • You do not have a stopwatch to time the cars as that would make the problem too easy :)
  • The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
  • The compilation time limit is 30 seconds.
  • There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing.
  • The match is rated.

Languages Supported

C#, Java, C++ and Python

Submission Format

Your submission must be a single ZIP file not larger than 500 MB, with your source code only.
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.

Make sure you name your Source Code file as CarRacing.<appropriate extension>

Sample Submissions

Here are example solutions for different languages, modified to be executed with the visualizer. You may modify and submit these example solutions:

Tools

An offline tester is available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.

Downloads

Offline Tester / Visualizer

In order to use the offline tester/visualizer tool for testing your solution locally, you'll have to include in your solution the main method that interacts with the tester/visualizer via reading data from standard input and writing data to standard output.

To run the tester with your solution, you should run:

java -jar tester.jar -exec "<command>" -seed <seed>

Here, <command> is the command to execute your program, and <seed> is seed for test case generation. If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\CarRacing.exe" or "~/topcoder/CarRacing". In case your compiled solution is to be run with the help of an interpreter, for example, if you program is in Java, the command will be something like "java -cp C:\TopCoder CarRacing".

Additionally you can use the following options:

  • -seed <seed> Sets the seed used for test case generation, default is seed 1.
  • -debug. Print debug information.
  • -N <N> Sets a custom number of cars.
  • -K <K> Sets a custom number of lanes.

Marathon local testers have many useful options, including running a range of seeds with a single command, running more than one seed at time (multiple threads), controlling time limit, saving input/output/error and loading solution from a file. The usage of these options are described here.

Payments

Topcoder will compensate members in accordance with our standard payment policies, unless otherwise specified in this challenge. For information on payment policies, setting up your profile to receive payments, and general payment questions, please refer to ‌Payment Policies and Instructions.