The previous thread has fallen off the front page, feel free to use this for discussions on current problems
Rules: no spoilers, use the handy dandy spoiler preset to mark discussions as spoilers
The previous thread has fallen off the front page, feel free to use this for discussions on current problems
Rules: no spoilers, use the handy dandy spoiler preset to mark discussions as spoilers
Day 12:
P1
Ok. I have been traumatised by computational geometry before, so I was initially spiralling. Luckily, there wasn’t too much comp geo stuff to recall.
My solution was a lot simpler than I initially thought: no need for union-find, accounting for regions inside regions, etc. Just check every square for a given region, and if it touches a square in the same region that you’ve seen before, subtract the common edge. This is linear in the area of the problem, so it’s fast enough.
P2
It took a moment to figure out that I could modify the above perimeter counting to mark the squares containing the perimeter and walk along it afterwards, counting each edge. This is also linear in area.