PROBLEM LINK:
DIFFICULTY:
tie-breaker
PREREQUISITES:
Grid, BFS/DFS, General Matching
EXPLANATION:
If you want to find a single path, you just use brute-force.
But, we can use a cell only once. How to deal with this?
I’ll introduce some ideas.
- Sorting checkpoints by coordinate
This is the most simple idea. Sorting (X_i,Y_i) and use L or U prior to R or D.
By doing so, we can avoid invading grids which are used after path.
- Sorting checkpoints by some conditions about L_i , R_i
For example, when the value R_i-L_i is small, the constraint about the length of the path is strict.
If we use strict constraints earlier, when filled squares of the grid increase, we just only think weaker constraints.
- Create short paths first
Of course, the less squares are used, the more path can be constructed.
If we construct short paths first, we can consider about paths which have a wide variety.
- Brute-force + Random Pruning DFS(or BFS)
We can look up all shorter paths, but we cannot look up longer ones. So, we can use the following method:
- If the current length of the path is small, continue brute-forcing.
- When the path become longer, do some pruning. For example, set 50\% chance to extend the path.
- Decide the matching first
We also can decide the matching of the checkpoints first. By doing so, you can use some approach of General Matching problem.
- Apply an A*-like idea
This idea makes finding a path much faster. When you have a pair of checkpoints, you can use A*-like method.
If you have a path with length l and have (x,y) as an endpoint, If you want to connect this path and i-th checkpoint, you need a path whose length is at least l + |X_i-x| + |Y_i-y|.
I think, it seems that brute-force based algorithms were strong in the ranklist.
Here are the submissions by D1 participants.
Other methods about MM (like divide-conquer, annealing, beam-searching…) can be applied.
Feel free to shere your approach!
Also, you can check out the video editorial or some discussion here.