Hi all!
The main phase of Codeforces Marathon Round 2 has ended. In the preliminary standings, contestants Rafbill and hakomo have got very close results, at the same time getting far enough from the next group of contestants. Will they manage to maintain the lead after the final testing, and who will come out on top? We will know in a few hours.
For now, I encourage the contestants to share their solution ideas in the comments below, or in separate posts. I'll start by mentioning a few solutions which I tried myself.
One of the easiest solutions which gets a stable score is this: move chameleon 0 with color
d[0], chameleon 1 with colord[1], ..., chameleon 9 with colord[9], then again chameleon 0 with colord[10], and so on until you move chameleon 9 at which you throw a bottle of colord[9999]. Such solution earns a score of 9719.44 on preliminary tests, getting place ~250 of ~275 non-zero scores.A more witty yet simple solution is greedy. First, we will always throw a bottle at the chameleon which is now the last. Simulate what happens, and pick the color which makes this chameleon move as far as possible. This already earns a score of 32096.7 on preliminary tests, getting place ~130.
One of the next possible ideas is to collect one particular color in Kurt's hands until he has at least X bottles of this color (for example, all 10). The other colors are used as in the previous greedy solution. After this, we use the color we collected for as long as possible (we may eventually get more than X consecutive bottles of this color in the process). It seems that the latter phase allows the chameleons to move fast. However, it turns out that this solution is worse than greedy: for example, when X = 10, it earns only a score of 29269.37 on preliminary tests, getting place ~195. Nevertheless, maybe this idea helps in combination with some others?
When one of the important parameters in the problem is time (for example, the number of move from 0 to 9999), what often helps is Beam Search. I'll describe it briefly.
Instead of acting greedily all the time, consider possible moves, and at each moment of time, store W (tens, hundreds, thousands...) best states. From each of the states stored for the moment t, make one or more moves in different ways, and maintain the W best results for every consecutive moment t + 1, t + 2, ... to which we get.
Here is another look at Beam Search. Consider a dynamic programming solution which depends on the moment t and the state s. Sure, there are too many possible states, so we will store not all of them, but the W states for each moment t which gave the best possible answer.
In order to use this technology, we have to decide how to evaluate the states. For example, first by the last chameleon's position, and in case they are equal by the sum of all chameleons' positions. Furthermore, we have to decide what will be the local changes: the moves to get to the next states. This can be, for example, one arbitrary next move, or several moves at a time using the same color.
A moderately easy solution using Beam Search earns a score of 33508.39 on preliminary tests. This corresponds to a mere 55-th place. So I'm very interested in what contestants say about the problem!
In the end, I'd like to thank Natalya Ginzburg (naagi) and Andrei Lopatin (KOTEHOK) for their help in preparing the problem, and also Mike Mirzayanov (MikeMirzayanov) for his help with Codeforces and Polygon platforms.
Update. A few hours passed, and then again, a few times, and we are finally ready to announce the results! Here is the top ten with a few numbers: lowest score (or the number of tests passed out of a thousand), average score (which determined the rank), highest score.
4154342432.93943550Rafbill4132742412.58443332hakomo(996)41031.78442175teapotd4010340980.62042016yarrr(995)40652.14741887UminchuR3967540620.65341682hatoo3977340617.44541605Coder3889940084.29141186Hoi_koro3895639935.62941032ts_3905739888.40840944MrDindows
Congratulations to the winners, and thanks to everyone who participated!
