PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica
DIFFICULTY:
CHALLENGE
PREREQUISITES:
2D Grids, Longest Path
PROBLEM:
You are playing a game against Chef on a 2D grid which has some positions blocked initially. At your move you can either create a new snake or extend your current snake by moving one of its endpoints to one of the adjacent empty neighboring cells. If you can’t extend your snake at all, then you can only create a new snake. If there are no empty cells on the grid then the game ends (you can end the game early, but it won’t help you with your score). Chef can make the same moves, plus an additional FREEZE move, in which he basically doesn’t make moves for a fixed number of turns (this helps you because you can occupy more cells while Chef does nothing).
The score you get for each snake is (L-1)xfloor(sqrt(L)) and the total score is the sum of the scores of each snake.
EXPLANATION:
It should be obvious that in any game, both you and Chef will make more or less the same number of moves (if we ignore Chef’s FREEZE moves, which give you a slight advantage). Thus, the total length of the snakes you create will be more or less the same no matter what strategy you use. But the scoring function rewards longer snakes with significantly higher scores. Thus, it is worth trying to construct snakes which are as long as possible. This will be easier to do in the beginning (when there are more empty cells on the board) than later.
Getting Correct answer for this problem is quite easy. There are many approaches which guarantee that you play correctly. Some of these approaches discussed during the testing phase were:
-
Dummy solution: print EXIT and terminate (it gets 0 points, though)
-
Create one snake and extend it randomly as long as possible
-
Use Chef’s strategy (without the FREEZE moves and without restarting snakes, unless you are forced to)
-
Greedy strategy: give each direction a priority and always try to create a part of snake in the direction with higher priority.
However, these approaches are not competitive from a quality perspective, i.e. they get very low scores (the best of them gets less than 0.1 of the best score obtained during the contest). I will present in this editorial an approach which is both simple, yet competitive from a quality perspective (it scores 0.797 of the best score obtained during the contest, which would have been enough for the 4th place in this problem).
The main idea is to always maintain two candidate paths for each endpoint of the current snake and then move the snake endpoints along these paths. Whenever the candidate paths become too short (because the opponent occupied some of the cells on the paths), we just recompute them.
Whenever we need to pick a new snake we will try several starting points and generate a “long” path from each of these points. We will pick the longest path found this way and choose the middle of the path as the new starting point of the snake. Then one of the endpoints will go from the middle towards the end of the path and the other one will go from the middle towards the beginning. We can pick the starting points randomly among the free cells, but I preferred to give preference to starting points closer to the upper-left corner of the grid (at least for the first snake).
When we need to make a move we pick the endpoint which has the longest remaining candidate path (the logic behind this being that if the candidate path is longer then there’s a higher chance that the opponent will block it) and move it along the path. If we can’t make any move, then we try to create a new snake.
When the opponent makes a move, it may occupy cells from the candidate paths of the endpoints. If this happens, the candidate paths are shortened to right before the newly occupied cell.
Before making a move we check for each endpoint if its candidate path was shortened recently by the opponent and, if it became too short, we try to recompute it. If the recomputed path is longer, then we replace the candidate path with the new one. For large grids we might not afford to recompute the candidate paths too often (we might get TLE). Thus, we only do the recomputation at most once every several turns.
Finally, we need a good (and fast!) algorithm for finding long paths starting from a given endpoint. This is probably the critical piece of this approach and better solutions than what I will present below can be found and used.
One algorithm which finds reasonably long paths quickly is the following recursive algorithm. The parameters of the algorithm are the current position and the direction which we are currently facing (this direction needs to be selected for the initial cell only).
FindLongPath(row, col, dir):
if (row, col) was visited: return 0
Mark (row, col) as visited.
maxlen = 1
for d = 0 to 3:
let (rnext, cnext) be the neighbor of (row, col) in the direction ((dir + d) modulo 4)
if (rnext, cnext) is an empty cell:
maxlen = max(maxlen, 1 + FindLongPath(rnext, cnext, (dir + d - 1) modulo 4))
return maxlen
The function returns the length of a long path starting from (row, col). The actual path can be easily reconstructed.
The algorithm considers the directions to be ordered in clockwise-order (e.g. Up, Right, Down, Left) and is based on the idea of the “left-hand” rule for exploring a maze. The meaning of (row, col, dir) is that one is currently located at the cell (row, col) and is facing the direction dir. If possible, the algorithm will first try to keep the direction and, if not, it will pick the first available direction in clockwise order (starting from the current direction). If the algorithm moves in a direction dir’, then it will immediately turn left, to face the direction (dir’-1) modulo 4. This is needed in order to move around obstacles/edges. Note that once a move is explored, moves in the other directions are considered, too. However, since the cells are never unmarked as being visited, this algorithm ends up visiting each cell at most once.
This algorithm can find initial paths containing ~93% of the cells of the grid. However, the length of the initial snake ends up being much shorter than that, because the opponent blocks easily these initially long paths and the algorithm finds shorter and shorter paths as the game progresses.
For better quality approaches I would recommend reading @ceilks’s description of his solution (which got 2nd place during the contest).
TESTER’S AND EDITORIALIST’S SOLUTIONS:
Tester’s solution can be found here (it implements the approaches discussed during the testing phase)
Editorialist’s solution can be found here (it implements the approach presented in this editorial)