UKIEPC21G — Getting Square — Geometry Problem

Revision en1, by Starswap, 2024-09-18 15:26:18

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

Thoughts so far

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 : )

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Starswap 2024-09-18 15:26:18 2478 Initial revision (published)