I'm trying to collect some solutions to the problems from UKIEPC (UK and Ireland ICPC sub regional) that don't have any official solutions (for completeness and also training) and I've been thinking about UKIEPC21G "Getting Square". I've come up with an idea about how to approach it but it seems to be quite a lot of effort and I think surely there must be an easier way. It makes me think it might use a topic that I don't know about yet, so I was wondering if anyone has any ideas. ↵
↵
The thing that makes the problem quite tricky is the fact that there can be arbitrary holes in the mosaic (see sample 2)↵
↵
I'd be glad to hear any thoughts. The problem is available from this set: [https://archive.algo.is/icpc/nwerc/ukiepc/2021/UKIEPC%202021%20Problems.pdf](https://archive.algo.is/icpc/nwerc/ukiepc/2021/UKIEPC%202021%20Problems.pdf)↵
↵
<spoiler summary="Thoughts so far">↵
I think we can:↵
1. Treat every corner as a node.↵
2. Work out the maximum distance you can travel up, down, left, right from each node by DP from ↵
3. For each 45 degree diagonal in this orientation: \ iterate over nodes on the diagonal from bottom right to top left, treating the current node as the bottom right corner of a target square. Then try to binary search to find the closest top left corner (other node on this diagonal) that can reach nodes reachable by this bottom right corner. I think this essentially requires RMQ on the max up, left, down rights from step 2 and we could use Sparse Table for this.↵
4. Then we have the smallest square with bottom right corner at X for all nodes X. Then the question is how do you ensure that the squares selected don't contain a "hole". This is where the method comes a bit unstuck because detecting holes is a bit annoying, but I think you can maybe do it by sweeping across the grid L to R and maintaining the current y values with holes. Then you have to try and find in n log n or better which squares need to be discounted due to containing or crossing a hole. I think we could use something like this https://stackoverflow.com/questions/61988883/to-find-if-any-overlapping-rectangles-exist-in-n-number-of-rectangles. But it gets very annoying very quickly.↵
</spoiler>↵
↵
PS: On the general project to make data for the missing problems, so far I've made solutions and data for UKIEPC21E and UKIEPC22A (see: https://github.com/starswap/UKIEPCMissingData ). I plan to make the others soon : )↵
↵
The thing that makes the problem quite tricky is the fact that there can be arbitrary holes in the mosaic (see sample 2)↵
↵
I'd be glad to hear any thoughts. The problem is available from this set: [https://archive.algo.is/icpc/nwerc/ukiepc/2021/UKIEPC%202021%20Problems.pdf](https://archive.algo.is/icpc/nwerc/ukiepc/2021/UKIEPC%202021%20Problems.pdf)↵
↵
<spoiler summary="Thoughts so far">↵
I think we can:↵
1. Treat every corner as a node.↵
2. Work out the maximum distance you can travel up, down, left, right from each node by DP from ↵
3. For each 45 degree diagonal in this orientation: \ iterate over nodes on the diagonal from bottom right to top left, treating the current node as the bottom right corner of a target square. Then try to binary search to find the closest top left corner (other node on this diagonal) that can reach nodes reachable by this bottom right corner. I think this essentially requires RMQ on the max up, left, down rights from step 2 and we could use Sparse Table for this.↵
4. Then we have the smallest square with bottom right corner at X for all nodes X. Then the question is how do you ensure that the squares selected don't contain a "hole". This is where the method comes a bit unstuck because detecting holes is a bit annoying, but I think you can maybe do it by sweeping across the grid L to R and maintaining the current y values with holes. Then you have to try and find in n log n or better which squares need to be discounted due to containing or crossing a hole. I think we could use something like this https://stackoverflow.com/questions/61988883/to-find-if-any-overlapping-rectangles-exist-in-n-number-of-rectangles. But it gets very annoying very quickly.↵
</spoiler>↵
↵
PS: On the general project to make data for the missing problems, so far I've made solutions and data for UKIEPC21E and UKIEPC22A (see: https://github.com/starswap/UKIEPCMissingData ). I plan to make the others soon : )↵
