Gassa's blog

Codeforces Marathon Round 2 has ended
By Gassa, history, 6 years ago, translation, In English

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.

  1. One of the easiest solutions which gets a stable score is this: move chameleon 0 with color d[0], chameleon 1 with color d[1], ..., chameleon 9 with color d[9], then again chameleon 0 with color d[10], and so on until you move chameleon 9 at which you throw a bottle of color d[9999]. Such solution earns a score of 9719.44 on preliminary tests, getting place ~250 of ~275 non-zero scores.

  2. 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.

  3. 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?

  4. 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.

Congratulations to the winners, and thanks to everyone who participated!

  • Vote: I like it
  • +185
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +120 Vote: I do not like it

Thanks to Gassa and the other organizers for the very nice contest. I hope for more marathon contests to be organized in the future.

My solution is indeed based on beam search. The code of my final submissions is available here : https://0bin.net/paste/iruL7y-FkxFbUXe3#PyLGLPPBXS2BzXB8b3GVJjMnf7WTVq0AjToA9srxmQG. (The important part starts on line 944). Thanks to the writers of https://probablydance.com/2016/12/02/investigating-radix-sort/ and https://stackoverflow.com/a/36205084 for their sorting functions that I used for performance reasons.

The states of the beam search are the chameleon positions and the colors of the bottles in the hand. I consider at each step all possible moves for all chameleons.

Here are the main components that made my approach work :

  • Avoid keeping similar states : Beam Search offers little improvement over a greedy algorithm if several equal states are kept (which can happen when independent, commuting moves are possible). For this particular problem, I chose to ignore a state whenever a state with the same hand colors and better sorted chameleon positions had already been considered (lines 1109-1116).

  • Use a good scoring function : At the end, we want to optimize the minimum chameleon position, but this is not a very good scoring function to optimize during the beam search. I tried several different scoring functions to sort the states of the beam search, and ended up with , where (pi) is the sorted list of the chameleons' positions (line 1083). It is probably possible to improve it, by considering for instance the colors of the squares under the chameleons, and the colors of the bottles in hand. It however has the advantage of being rather cheap to compute.

  • Optimize the program and increase the beam width : By doubling the beam width of my last submission, the scores obtained by my code can still increase by more than 500 points. Any small optimization that allows submissions using a larger beam width to fit in the time limit is reflected in the score.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    I also ended up with beam search, with few differences:

    • I only considered maximum jump for each chameleon (it seemed to work equally good to considering all moves)
    • As score function I used
    • Instead of ignoring similar states, I took every third state from first 3W states with best scores

    With optimized max jump calculation I got score ~41100 with W = 4000, here's the final code: https://gist.github.com/teapotd/f81356f24d278989ca57d05cc4254e72

    After reading your comment I decided to try out your way of avoiding similar states. I choose state with better score if hands are equal. And it indeed gave great improvement: with W = 3000 it takes about 13s on my computer and gives ~43100. Here's the improved version: https://gist.github.com/teapotd/4dc4c3a7ca7a187c5ba4eabdfb65c800

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Almost nothing can add after Rafbill's description :)

    My last submission: https://gist.github.com/yarrr-ru/97361c5bca72bb3b5f0e549b811a510b

    I have same ideas in my solution, only differences:

    For this particular problem, I chose to ignore a state whenever a state with the same hand colors and better sorted chameleon positions had already been considered (lines 1109-1116).

    • This helps a lot. I didn't have this like teapotd and seems like this was key feature to get 42k+ score.
    • Have exactly the same scoring function with just different C (instead 0.925 I use 1.0 / 1.07  = 0.934).
    • I manage to squeeze BEAM_WIDTH = 675 to TL without any tricky sorting, I sort positions one time and after making move for single animal I just must remove single value from sorted array and insert new one. This can be done linearly (functions movePositionsAndCalcScore + trickyEvaluateAnimalPositionsScore).
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Hi, just read the problem. Can you explain what the number 1.07 is and how did you come up with it?

      → Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Well the contest was really amazing, I tried many ways and finally my rank was only 62 (not good enough :( ).
But i had no clue as to what beam search was! Well thanks to the editors and other participants who introduced this topic hope i will find this useful!
Anyways i will state the few methods that i tried!
1) I initially i also used the sol. NO. 1 in the blog and got 9k points
2) Then i tried to play with random numbers i would randomly select a chameleon and a random color in the hand.(This didn't get me anywhere worse than method 1 :p)
3) Then i wrote the greedy solution which got me the 32096 points.
4) Fourth time what i did was that would select the last 5 chameleons and try all permutations of sending these 5 chameleons one by one to the best location greedily and among all permutations i would select the best and then would update the positions and then i would repeat the process (This gave me the best score 33285.278). I also tried taking last 6 but that would give a TLE so i tried skipping some permutations but that did not help!

Anyways it was fun and kept me engaged for a while and i would to attend more such marathons!

Thank You Gassa, naagi, KOTEHOK for this contest!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

I'm very surprised that the top solutions are essentially just smart brute-force.

I personally tried a lot to optimize the greedy algorithm with heuristics.

Initial greedy: If a chameleon can't catch up to any chameleon, throw the best bottle at it (so nobody gets left behind). Otherwise, pick the chameleon-color combination that goes the furthest, and use that. I found this was better than always throwing it at the last one, though i had some bugs in my solution early on so I'm not sure :P

Then, later, instead of just calculating the chameleon that went furthest, I tried to add a number of heuristics, such as

  • If a chameleon is standing in a useful spot — that is, it is standing on a square of color C, the next square of color C is pretty far away, there are chameleons behind that chameleon, and you are holding bottle(s) of color C, then decrease the priority of throwing a bottle at that chameleon.

  • If throwing a bottle of color C at a chameleon would put it in a useful spot (useful means as above), then increase the priority of throwing a bottle of color C at that chameleon.

Ultimately, though, these heuristics barely made it better than the greedy solution.

I'm wondering if anyone managed to improve the greedy solution by a lot using some similar heuristics.

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

it makes me think of alpha go and reinforcement learning, where you use some kinds of expansion at the end to estimate the current state...

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks all for designing the problems. Here are some thoughts during the week. I don't know about beam search so I mainly brute force all choices.

1) Choose the colour appears most in hand, and keep throwing to the last chameleon If that colour appears a lot in hand , then probably the chameleon can skip a lot since the next few locations of that colour are occupied.
Result : ~20k

2) Brute force on current step and choose the greatest move. However some chameleon moves a lot but some didn't. Possibly the 10 chameleon are divided into several groups at the beginning sincetheir relative position are not considered and one group lag behind.
Some chameleons at ~10k and some at ~30k
Result : ~10k

3) Taking both the number of squares moved and their relative position as consideration, movement - dist(Chameleon, Last Chameleon)
Result : ~33k , time <0.1s

4) Looking at (k + 1)th step when deciding the (k)th step. Brute force on all possible choices. I take the average of best few cases on (k + 1)th step instead of the best to prevent some extreme cases. Adjust weightings between current step and next step. Get the best choice and move a step.
Result : ~34k , time 2~3s

5) Repeating (4) on (k + 2)th step with some methods tried to reduce time:
- Not searching all choices on k + 2 step, but the last few chameleons.
- Ignore chameleons far away from the last one, say by 50 squares.
And finally try different values for parameters, such as:
- weighting of movement - dist(Chameleon, Last Chameleon) dependent on step
- weighting between current step and next steps
- non-linear measure for dist(Chameleon, Last Chameleon)
Result : 35.7k , time ~10s
However I don't know how they works. Also small improvement can be done if I can remove some possible choices at a earlier stage and search deeper.

Final submission: https://github.com/kmyiu/Codeforces_Marathon_R2/blob/master/cf_marathon.cpp

→ Reply