MM166 Participation Log

It’s me.

I participated in Topcoder Marathon Match 166.

In the previous AHC069 , I was constantly discussing or brainstorming ideas with Codex. This time, due to token-saving reasons and similar factors, I worked with the following workflow:

1. Discuss with ChatGPT
2. Have ChatGPT create implementation orders
3. Have Codex implement them
4. Have the results summarized

As a result, I managed to use up my tokens really efficiently, so the strategy was a success. Well, I wouldn’t call the contest result a success, but aren’t the other participants way too strong? It’s crazy. I want to get stronger too.

Problem

This problem is about rotating hexagonal tiles to create paths. The board itself is also hexagonal, with $N$ tiles on one side. Each tile has 6 edges, which are paired into 3 lines in total. A tile can be rotated clockwise or counterclockwise in 60-degree increments.

There are exits on the outer perimeter of the board, and correct pairs of exits are given in advance, such as:

Connect Exit 0 and Exit 17 Connect Exit 1 and Exit 42

If you follow the lines on the tiles and connect the two designated exits, that path is considered correct.

Additionally, there are bonus tiles on the board. Let $L$ be the length of a path, and $b$ be the number of bonus tiles that path passes through. The score for that path is:

Therefore, it is not just about connecting the correct exits; ideally, you want to make the path as long as possible and pass through as many bonus tiles as you can.

On the other hand, a cost is incurred every time you rotate a tile from the initial board setup. Let $k$ be the number of correctly connected paths, $t$ be the total score of those paths, $m$ be the number of rotations, and $M$ be the penalty per rotation. The score is:

Since increasing the number of correct paths multiplies the entire score, you want to increase $k$ first. However, rotating a lot to increase paths increases $mM$. Furthermore, for the same $k$, a path that is longer and passes through more bonuses is stronger.

At first glance, I wondered if I should use something like rollback greedy algorithms. In the end, I didn’t use it at all though.

Creating Paths Greedily

I thought I might be able to earn points by completing all paths where exits $i$ and $i+1$ were specified, and then turning all the remaining cells into a single path, so I gave it a try.

The approach was something like:

1. First, create paths that are easy to complete.
2. If other correct paths are completed along the way, save them as well.
3. Once a path is completed, try not to break it if possible.
4. Finally, make a long path using the remaining cells.

As for deciding which tile to rotate next, instead of simply looking at the score at that exact moment, I determined it by checking the following conditions in order:

1. Few dead-end states
2. Many reachable states ahead
3. A new correct path gets completed
4. High score for the completed path
5. Few rotations

Since this was slow, from a certain point on, I focused heavily on optimization before changing the algorithm. I stopped copying the board every time I tested a candidate, changed the path addition check from $O(L^2)$ to $O(L)$, and reused arrays needed for searching.

Along the way, I tried to make an exact solver that solved only the $N=3$ case in an attempt to solve small boards rigorously. However, it ultimately didn’t reach practical use and was removed from the submitted code.

Looking back, I feel like I spent quite a bit of time on things I didn’t end up using. Well, trying out what works is the essence of heuristics, so it’s fine, right? lol

Trying Simulated Annealing

Since the greedy solution was more or less done, I moved on to simulated annealing.

At first, it was simple: select one tile and change its orientation. Later, thinking that changing just one tile would be too local, I added a move that changes two adjacent tiles simultaneously.

Eventually, it became:

1. Change 1 tile with 75% probability
2. Change 2 adjacent tiles with 25% probability

Around this time, recalculating the paths for the entire board every time was naturally not keeping up, so I changed it to disconnect and reconnect paths only around the modified location. Paths are maintained using Treap.

Codex did a great job here. I was just standing next to it, constantly urging it, “You can make it faster.”

Now, while running simulated annealing, evaluating based solely on the official score felt a bit off. For example, there were many cases where the correct answer was:

A - B
C - D

but it ended up like:

A - C
B - D

The paths themselves were properly completed, but only the exit destinations were wrong. Since I didn’t want to treat this state the same as a state where the path was broken midway in the first place, I included the length of paths completed from perimeter to perimeter in the evaluation value, regardless of whether they were correct pairs. In the early stages, I placed some emphasis on this as well, and as time passed, I shifted the weight toward the official score.

Around this time, rather than saying “making paths” was difficult in this problem, it started to feel like:

In fact, in one case, a board was generated where there were no cycles at all, and paths properly led from every exit to another exit, but only 11 out of 15 pairs were connected correctly.

All the lines exist. The destinations are wrong. How annoying!

So, instead of simply changing random tiles, I added a method to select an exit that was not connected to the correct destination and modify tiles on the path extending from that exit. Ultimately, 30% of the modifications used this approach.

I tested a lot of variations here as well, thinking, “If it’s a long path, wouldn’t it be better to focus on modifying the exit side?” Indeed, looking only at the efficiency when modifying the exit side, it got better.

However, running it over 100 cases dropped the score.

I don’t get it at all. It really ticks me off.

Trying Beam Search Too

Since the improvement of the simulated annealing solution began to saturate, I wondered if beam search might be better, so I tried beam search too.

What I was particularly concerned about was that state mentioned earlier: “all paths exist, but the exit destinations are wrong.” Just changing 1 or 2 tiles couldn’t achieve transitions like:

1. First, modify 1 location
2. Score temporarily worsens
3. Modify another location
4. The exit combinations finally get fixed

“Then why not keep a few slightly worse boards along the way and look further ahead?” With that thought, I tried beam search.

Initially, it was a standard setup maintaining multiple boards and generating candidates from them. Keeping boards based solely on the official score resulted in too many similar boards, so I tried keeping boards based on various criteria, such as:

1. Official score
2. Number of correctly connected paths
3. State of all paths, including incorrect ones
4. How close the exit combinations were to the correct answer

I tried mixing in boards that were heavily modified at random, inserting simulated annealing along the way, and searching further around candidates that came out of the beam search; basically, I did a lot of things.

Later, while casually reading through the AHF Vol.1 material , I found a description regarding the choice between beam search and simulated annealing. Realizing, “So it really is simulated annealing this time after all,” I abandoned the beam search approach.

Eventually Returning to Simulated Annealing

I tried beam search for about two days, but since it couldn’t surpass the simulated annealing solution, I ultimately came back to simulated annealing.

However, I didn’t just revert it back as it was. Only when simulated annealing failed to improve for a long time, I restored the state to the best board so far and decided to try a slightly larger modification than usual.

First, I select up to 4 tiles on a path. For 4 tiles, there are

orientations, so I can exhaustively search all combinations if it’s just this part.

After trying the method of doing this once, I thought, “Maybe there are cases where it gets worse on the first try, but improves if another location is changed?” So I kept a few candidates from the first attempt, and performed another 4-tile exhaustive search starting from each of those candidates.

In the current code, the width is 4 and the depth is 2.

In the first pass, I narrow down to a maximum of 4 boards by keeping those with:

1. High official score
2. Large number of correctly connected paths
3. High evaluation on the overall path side

From those 4 boards, I select 4 tiles again to perform an exhaustive search, and finally, I simply use the one with the best official score.

So, in the end, I gave up on “searching the entire board with beam search,” and it took a form like:

Usually, run simulated annealing at high speed. Only when stuck, look a bit further ahead all at once.

In the End

At the stage of writing this article before system testing, I am ranked 37th out of 74. I wish I had gotten a bit higher…

The problem itself was super fun. Simple yet difficult. I want to create optimization problems like this…

From the middle onwards, rather than thinking of improvement ideas myself, I was constantly doing things like:

1. Measure what is bad
2. Formulate one hypothesis
3. Implement it
4. Run 100 cases
5. Discard if it doesn’t work

(I had Codex and GPT do all of this).

The people around me are way too strong. Seriously. I want to go higher next time!