CONGRID - Discussion

editorial
, , , ,
#1

Problem link: CONGRID

Setter: Masahiro physics0523 Inoue

The text-editorial is still in construction, but we already have a video-editorial:

https://www.youtube.com/watch?v=FvHDHBD3lik

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:

  1. Random order and then a single BFS/DFS (not the above mentioned brute force DFS) to try finding some match for every checkpoint.

  2. A general graph matching based approach (0.6-0.7 points right now, so you can check out those solutions for more details)

  3. 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.

CONGRID - EDITORIAL
#2

I found a reasonably straightforward solution for the CONGRID problem, getting me 36 points, even though I was ranked only 405 in the whole contest. I usually like to try the Challenge problem, because I do not need to find an optimum solution, merely a fairly good one. Intuition is often more useful in these problems than clever algorithms. I am interested to see what approaches others took, to gain more points.

Given a square grid containing some checkpoints, we want to connect them with paths subject to constraints on their length, where the paths may not intersect, and they cover as much of the grid as possible.

  1. Choose a square block-size B such that on average it contains 2 to 3 checkpoints, by B = floor(N / Sqrt (K/2)) where N is the length of the side of the matrix, and K is the number of checkpoints.

  2. Prepare to work through the checkpoints in the matrix in blocks. Sort the checkpoints first by block in Y, then X, then Y.

  3. Work through the blocks in X then Y. As we come to each block, we maintain a list of unused checkpoints in the entire vertical strip to the left (lower Y), and a similar list for the partial strip above (lower X).

  4. Attempt to link each unused checkpoint from each of the lists to each of the unused checkpoints in the current block by the following method:

    If they are not too far apart, attempt to link them first in X then in Y, rejecting the solution if any cell is already occupied by another checkpoint or path. If this fails, try linking them in Y then X.

    If we can add at least 2 further cells to the path, set upper limits in X and Y so that we do not go beyond any further checkpoints in this block, or beyond the extent of the block.
    Try adding further points to the path, until either no more are possible or we have reached the limit on number of points

    If consecutive points are at the same Y, and the two cells to the left are unoccupied, inserting these cells between them.
    Do the same for each pair of points in each direction up to the limits.

  5. Attempt to link each unused checkpoint in the current block to each other unused checkpoint in the current block in the same way.

You can find details about the maintenance of the lists, the order of adding points and so on in the code, at https://www.codechef.com/viewsolution/39575286

1 Like