Problem link: CONGRID
Setter: Masahiro physics0523 Inoue
The text-editorial is still in construction, but we already have a video-editorial:
Meanwhile let us know what approaches did you tried!
Here is the feedback of Radoslav:
Well I’ve also been looking at the top solutions as I’m making a video editorial and it seems the best approaches are simply considering the checkpoints in some order and then trying to match them with a DFS. In a way this actually makes sense as the constraints for L,R are low (<=64), so there won’t be a large time difference between a well written beam search and the brute force approach (+ random pruning when the depth is large). As for the initial order, the best approaches seem to use lexicographical sorting by either (Xi, Yi) or (Ri, -Li).
Maybe a good idea for the editorial would be to discuss some different approaches that the participants did, and how well they performed (at least I’m doing something like that). So far I’m aware of the following solutions:
Random order and then a single BFS/DFS (not the above mentioned brute force DFS) to try finding some match for every checkpoint.
A general graph matching based approach (0.6-0.7 points right now, so you can check out those solutions for more details)
The above-mentioned approach. Depending on the order heuristic and the heuristic based on which we decide the best candidate for a match it gets somewhere between 0.8 an 1 points. The most intuitive approach I saw was to find the number of reachable checkpoints based on simply Manhattan distance for every other checkpoints. We will call this number the degree of a checkpoint. Now the decision between the different candidates can be based on (degree, distance). In a way, the degree will say how hard it is to match a certain checkpoint.