Just a question regarding time complexity, in my local machine for N=10, code runs in 400ms whereas on atcoder platform same one runs on 30ms. Which one should I consider?

Apparently, heuristic contests doesn't have editorial. Where can I find editorial/approaches?

Can someone discuss some of the strategies they used to get beyond 35 million?

Here is a short description of my ideas that got me first to 17 million and then to around 35 million with some optimization.

Basic idea for ~15 million:

A simple heurisitic for generating a large tree (hopefully a complete one) is to choose a random point and dfs from it. When we reach a new cell, we will try the 15 non-empty masks in random order satisfies and place a mask if it satisfies the following two conditions:

• Placing the mask in this cell doesn't form a cycle.
• There doesn't exist an adjacent position which this position connects to which already has an adjacent cell with a connection toward it. Basically there does not exist any adjacent cell such that some mask we could place would create a cycle or waste an endpoint (making a complete tree impossible).

This hueristic seems to generate complete trees for n <= 7 but only trees of size 90-95 on average for n = 10. Still a decent start.

To make stuff easier later, lets ensure the empty cell is always at (0, 0)

Now to think about a simple heurisitic for solving the puzzle.

Lets first solve an important problem — how can we move a non-empty cell from $$$(a, b)$$$ to $$$(c, d)$$$.

Suppose we have a valid sequence of cells $$$(x_1, y_1), (x_2, y_2), \cdots, (x_k, y_k)$$$ such that $$$(x_i, y_i)$$$ is adjacent (sharing a side) to $$$(x_{i + 1}, y_{i + 1})$$$, $$$(x_1, y_1) = (a, b)$$$ and $$$(x_k, y_k) = (c, d)$$$. In other words this sequence of cells represents a path from $$$(a, b)$$$ to $$$(c, d)$$$. If our cell is currently at $$$(x_i, y_i)$$$ and we want to move it to $$$(x_{i + 1}, y_{i + 1})$$$, we need to move the empty cell to $$$(x_{i + 1}, y_{i + 1})$$$ (without moving the cell at $$$(x_i, y_i)$$$ in the process) and then move it to $$$(x_i, y_i)$$$. Repeating this will allow us to move our required cell from $$$(a, b)$$$ to $$$(c, d)$$$. To move the empty cell to the target location without moving certain cells we don't want it to move (like $$$(x_i, y_i)$$$ here), we can use a list of 'blocked' cells and bfs around them to find a path.

Note that if we use bfs to find the original path from $$$(a, b)$$$ to $$$(c, d)$$$ as well as the path for the empty cell, we will minimize the number of moves used which is what we want.

Now that we know how to move a cell fairly arbitrarily, lets think about how to transform a grid from the original one to the target one. One simple way is to try to transform it into a smaller subproblem. Since we have an $$$n \cdot n$$$ unsolved grid, lets try reducing it to an $$$(n - 1) \cdot (n - 1)$$$ unsolved grid by solving the last row and column. This seems to be a pretty common idea, so here is a nice blog describing how we can do that.

Solving the last two rows we place in a given column / last two columns we place in a given row seems tough due to the value potentially getting stuck, so lets just forget about it for now. Additionally our method doesn't work once we have a 3x3 left so skip that as well.

Even with this incomplete puzzle solver, it is enough to get close to 15 million. (I didn't submit this, so no submission to link unfortunately.)

15 to 20 million:

• Tree generator — When trying to place masks in a given cell, instead of trying them in random order, lets order them such that they are ordered in descending order of connections and arbitrarily shuffled for those with the same number of connections. The reasoning here is that the cells with a larger number of connections are harder to place so we want to place them earlier when the board is more free.

This allows us to generate a complete tree within ~2s around 90% of the time for n = 10.

• Puzzle solver — To solve the last two of a given row / column, lets just move the value that can get stuck as far away as possible (to (0, 0) in my case) to guarantee it can't get stuck.

Score — 19988760

20 to 25 million:

• Puzzle solver — Lets precalculate all possible 3x3 transformations and see if any allows us to reach the required state at the end.

Since the grid is bipartite and we move the empty cell one step in each move, exactly half the 3x3 states are reachable from a given state at the end. However since we potentially have repeated values in this 3x3, we may have multiple winning states that match the expected values, so our odds are better.

Score — 25412653

25 to 30 million:

• Tree generator:

  • Shuffle the order we check adjacent cells in the dfs. This improves the chance of finding a complete tree to >99% even if run for <1s.

• Puzzle solver:

  • For a given layer, randomly decide whether to process the row part or the column part first to introduce some randomness.
  • Store checkpoints for each layer. After getting an initial answer, roll back i states with probability 1 / (i + 1) and recalculate the layers. If we get a better answer at the end, replace the existing answer with it. Repeat this while we have time left.

These two together also make the chance of finding a 3x3 matching at the end almost 100%.

Score — 30038670

30 to ~35 million:

Basic thought — Different trees from the same masks can have drastically different costs to solve using the puzzle solver.

Until we are out of time, lets repeat the following process:

1. Generate a perfect tree.

2. Run puzzle solver on it for a small amount of runs to get a estimate of how good the tree is.

3. Replace the existing tree if the current run has a better answer.

Once we are done with this, we run the puzzle solver on the "best" tree for some more time to optimize the answer we got.

Score — 34779126

Unfortunately got busy after this an didn't get any time to try out any further ideas. Some ideas I had for > 35 million:

• Tree generator:

  • In addition to selecting masks with a higher number of connections, maybe also favour those with more instances remaining.
  • Add a rollback system for the tree generator as with the puzzle solver, then try to iteratively improve good trees.
  • Try to come up with some approximate metric that ranks a tree without needing to actually solve it (possibly something like best sum of distances between masks in the initial grid and the obtained tree), then we can potentially try to track it during tree generation time and use it generate easier to solve trees.

• Puzzle solver:

  • Instead of just removing the last row and column, lets generalize it to being able to remove the first row or column as well. Then we can remove the restriction of requiring the empty cell to be at (0, 0) but instead just ensure our final 3x3 covers the empty cell. I believe this will drastically reduce the number of attempts required to get a complete tree and increase the answer by a few million. It also introduces more randomness allowing us to minimize the distances further.
  • Instead of always having the last two cells removed in a given row / column be the first and second from the top / left, lets choose them as any random adjacent pair to allow a chance for the distance to be further improved.

Would love to hear what other participants did to reach more than 35 million.