Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @java_coffee_cup,validated by @User123,@jordan_codingame and @Xophe.
If you have any issues, feel free to ping them.
I really liked this one! Although it would probably be better to split it in 2 episodes - medium (just correct solution) and hard (solution optimization for big grids).
For me it was a bit strange that the bounding box of the grid is from (1,1) to (side + 1, side + 1) instead of the more natural (0,0) to (side,side). The example drawing in the statement draws it correctly, but it is not referenced in the text anywhere else.
IDE Test #3 puts a size-of-500 square at (501,501) so the constraint “none of the squares extend beyond the grid boundaries” would be not true if using (0,0) based grid. I found it out only the hard way (by spending time with unnecessary debugging).
There is no index on the bounding box. The coordinates, from (1,1) to (side, side), refers to the counting numbers of the grids.
If you prefer to use 0-based indexes, keep a clear mind what the indexes mean to yourself. Does it mean the indexes of the grids, or the boundary lines and division lines between grids? You can define it in the way you prefer.
Thanks, makes sense.
What I meant that for example having a single-tile-size square at the top left corner of the grid corresponds to input (x y s) = 1 1 1, instead of 0 0 1 which I assumed wrongly.
I see this problem is tagged as ‘Flood Fill’ but it quickly became apparent that you cannot simply create a full grid of side^2 to do this or else you run into memory limits. The only way I could figure out out to use the method was to create a ‘bounded’ grid that covers the min/max extentsof all the given square coordinates, and then use x,y offset to check if the query points lie inside/outside the grid components. It works with the given test cases but it feels kind of hacky and error prone and I’m not sure if that’s an intended solution.
This problem seems like it should really be solved with Sweep-Line algo combined with a Segment Tree, especially to answer the queries efficiently. Of course, that would put it squarely into ‘Hard’ difficulty (I’ll be here all night, folks!)