Блог пользователя Gassa

Автор Gassa, история, 3 месяца назад, По-русски,

Всем привет!

Основное время Codeforces Marathon Round 2 закончилось. В предварительных результатах участники Rafbill и hakomo получили очень близкие баллы, но при этом достаточно сильно оторвались от следующей группы. Удастся ли им сохранить этот отрыв после итогового тестирования, и кто окажется выше? Это мы узнаем через несколько часов.

А пока предлагаю участникам поделиться идеями своих решений в комментариях ниже или в собственных постах. Начну с упоминания нескольких решений, которые я сам попробовал написать.

  1. Одно из самых простых решений, стабильно получающих какие-то баллы, таково: будем двигать хамелеона 0 цветом d[0], хамелеона 1 цветом d[1], ..., хамелеона 9 цветом d[9], затем опять хамелеона 0 цветом d[10], и так далее до хамелеона 9, в которого мы швырнём баночку цвета d[9999]. Такое решение набирает 9719.44 балла на предварительных тестах, занимая ~250-е из ~275 мест с ненулевыми баллами.

  2. Более разумное простое решение — жадность. Во-первых, будем всегда швырять баночку в хамелеона, который оказался последним. Будем симулировать происходящее и выбирать тот цвет, после которого этот последний хамелеон пройдёт дальше всего. Такое решение набирает уже 32096.7 баллов на предварительных тестах, занимая ~130-е место.

  3. Одна из возможных следующих идей — копить какой-нибудь один цвет в руках, пока баночек этого цвета не станет хотя бы X (например, все 10). Остальными цветами действуем как в предыдущем жадном решении. После этого можно тратить баночки этого цвета, пока они не кончатся (вполне возможно, их в итоге окажется больше X). Кажется, что в этот момент хамелеоны движутся довольно быстро. Но проверка показывает, что это решение работает хуже жадности: например, при X = 10 оно получает всего 29269.37 баллов на предварительных тестах, занимая ~195-е место. Тем не менее, возможно, эта идея помогает в комбинации с другими?

  4. Когда один из важных параметров в задаче — это время (например, номер хода от 0 до 9999), часто помогает Beam Search. Опишу вкратце эту технологию.

Вместо того, чтобы действовать всегда жадно, будем перебирать возможные ходы и в каждый момент времени хранить W (десятки, сотни, тысячи...) лучших состояний. Из каждого из состояний, сохранённых для момента t, будем делать один или несколько ходов разными способами и поддерживать W наилучших результатов для каждого из следующих моментов t + 1, t + 2, ..., до которых мы добрались.

Вот другой взгляд на Beam Search. Рассмотрим решение динамическим программированием, зависящее от момента t и состояния s. Конечно, состояний слишком много, поэтому будем хранить не все, а только те W состояний для каждого момента t, для которых получился наилучший ответ.

Чтобы воспользоваться этой технологией, нужно придумать, как оценивать конфигурации. Например, сначала по позиции последнего хамелеона, а при равенстве по сумме позиций всех хамелеонов. Кроме того, нужно придумать, как делаются локальные изменения: ходы для получения следующих состояний. Это может быть, например, один любой следующий ход, или сразу несколько ходов одним цветом.

Не очень сложное решение с применением Beam Search у меня получило 33508.39 баллов на предварительных тестах. Это всего лишь примерно 55-е место. Так что с интересом жду, что про задачу расскажут участники!


Напоследок хочу поблагодарить Наталью Гинзбург (naagi) и Андрея Лопатина (KOTEHOK) за помощь в подготовке задачи, а также Михаила Мирзаянова (MikeMirzayanov) за помощь с системами Codeforces и Polygon.


Дополнение. Прошло несколько раз по несколько часов, и мы наконец готовы объявить окончательные результаты! Вот первая десятка с несколькими числами: минимальные баллы (или количество пройденных тестов из тысячи), средние баллы (по ним определялись места), максимальные баллы.

Поздравляем победителей, и спасибо всем за участие!

Обсуждение Codeforces Marathon Round 2
 
 
 
 
  • Проголосовать: нравится  
  • +185
  • Проголосовать: не нравится  

»
3 месяца назад, # |
  Проголосовать: нравится +120 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +42 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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).
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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!

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

когда будет системное тестирование?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Основная часть тестирования уже произошла. Мы ещё раз проверим, всё ли в порядке, и после этого объявим результаты окончательными.

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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