How It Went

In problem E we got the third place. I implemented several ideas, here are some examples:

• Sort the tuples $$$(s_i, d_i, q_i)$$$ in decreasing order of $$$q_i$$$, find the closest "free" nodes (degree $$$ \lt r$$$) to $$$s_i$$$ and $$$d_i$$$, and connect them. Variation: instead of sorting by $$$q_i$$$, sort by some $$$f(q_i, \text{dist}(a, b))$$$, where $$$a$$$, $$$b$$$ are the nodes to be connected.
• After this process, add edges greedily between nodes with degree $$$ \lt r$$$.
• For $$$r = 4$$$, you can use the solution of agc050_a — AtCoder Jumper to guarantee that all the distances are $$$O(\log n)$$$.
• You can optimize any of the previous methods with simulated annealing, keeping the structure of the graph fixed and swapping nodes.

In problem I, I did the following:

• Instead of RGB with $$$256^3$$$ possible colors, approximate to $$$16^3$$$ possible colors.
• Main idea: find two adjacent components and merge them. It turned out it's much better to merge components with similar colors, and it's much better if the smaller component is small. Surprisingly, it seems that the size of the larger component does not really matter.
• In several tests, this method is not so effective, because there is a background + several non-adjacent connected components, which would be merged with the background (and disappear). So you actually want to connect them to each other, doing something similar to a MST. This might not work very well (for example, it might create holes which increase the number of connected components), but in that case we run a second round of compression using the algorithm in the previous point.
• I solved test 4 by hand (it's similar to a level of the game Flow Free).

Problem C: ChatGPT misunderstood the statement, and I only realized it after several hours. I spent a lot of time getting a correct solution, and didn't have time to optimize it well.

• Most of the times it's possible to draw a "good" arc which allows to reach the gate in the next step, using a segment. I just try random arcs; if none of them is good, I just choose one randomly and retry (wasting one step).
• It seems that the radius of the arcs does not really matter (bigger radius = higher speed but also greater length). So we mainly want to reduce the number of steps. The point of the problem seems to be "find a segment / arc which passes through many gates simultaneously". Maybe it's possible to recycle the solution to this problem for some tests, but we had no time. 24 hours seem a lot, but they are not.

I started by doing a simple greedy — let's assume every pixel is its own component, and then while we have too many components, unite two neighbouring ones which affect our score the least. Since you only need $$$O(1)$$$ info for every component, it just works fast enough. Though one trick I had is to only recalculate penalty for two components when I extract a pair from my priority queue and see that it's outdated, instead of updating everything after each merge.

Then I added annealing — pick a pixel, check that it's not an articulation point, and assign it to the component of one of its neighbours. A few notes about that:

• Actually checking that the pixel is an articulation point is too slow, so instead I checked that 8 of its neighbours form a single connected component, and if so, then it's safe to delete the pixel. Generally it worked great, but sometimes it did leave these long loops which it couldn't cut anywhere. After the contest I tried allowing it to actually run dfs once in a while to check for articulation points and it did cut the loops, though didn't improve the score that much. But I'm wondering if there is a better solution for that

• A lot of pixels will have all the neighbours from the same component, so maintain the list of all pixels which are on the border of their component, it can be done in $$$O(1)$$$

• And again, maintain all component scores in $$$O(1)$$$

Apparently that was enough to get the best score on some "normal looking" images, but worked terribly on tests like 3, 10 or 12 where you kind of needed to just hardcode a spanning tree/forest. For these tests I did the following:

• Let's find all connected components, assuming that two pixels are connected if the color difference between them is small enough. For test 3 just set some threshold for black/white

• Let's merge all small components into their larger neighbours, it especially helps in test 10 with all the holes in the images

• Then do something like Kruskal's algorithm — on each iteration for every pair of components try to build a path between them, connect them, and check how it affects the score. Unite the two with the minimal effect. I didn't implement this in the most optimal way, so it took a few minutes to run, but having it work once was enough

• And run my beloved annealing in the end

At this point I wanted my annealing to be able to split some component and then merge something else, so it could fix some non-optimal "edges" in tests 3 or 10. But I don't know how to do it in a sane way, would love to hear any ideas.

In the end I just ran a lot of annealings for the best solution of every test again and again, and it improved the score for most of them. I was especially surprised how it managed to fix test 11 — my final solution looks like this (two purple components on the black background):

But initially it looked something like this

and every annealing run which took a few seconds added another one or two letters to each component (thanks to intentionally high starting temperature I suppose).

It also did the similar thing on test 12, but there it didn't look that cool. Nevertheless, here are all of my final in-contest solutions: https://drive.google.com/drive/folders/15WX2bZ1TGCj3DzmVQ5QgZwvvT5VV9660?usp=drive_link. Just look at this beauty of a solution for test 4 for example:

For this problem, I implemented some not-very-advanced solution, and it surprisingly remained okay-ish until the end of the contest (2700 points compared to top 3300). My main ideas were:

• For R=2 let's write a separate solution — every connected component must be a cycle, so let's write down the permutation and do annealing for it. Mutation would be just swapping any two nodes, then it's enough to recalculate scores only for paths starting or ending at one of these two nodes.
• For larger R take the previous solution for R=2 and try to add edges on top of it...
• ... or just start from the scratch and add edges greedily by the weight of the path between then (if any is present in the input and the ends are not saturated yet)

I tried to come up with some way to efficiently do local optimizations/annealing on a final graph and couldn't. The idea from TheScrasse that you can just swap nodes even if your graph is not a cycle is quite beautiful. Is there something you can do for moving edges around?

I experienced death from geometry in this one, don't think I had any unique ideas here. Apparently it's crucial to have a "smooth" path all the way, and the most I managed to do during a contest was to check whether I can visit segments from [i..j] in a single "stroke" (arc or segment), and then do dp on that (also let's mark K evenly distributed points on every gate and then try to go from every point on gate i to every point on gate j so that dp actually works)

A few days after the contest I implemented some UI to draw a path manually and it (would have) improved our score on most tests by a factor of 2x-3x, apparently there are teams who just did that during the contest