Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @Mortis_666,validated by @lolTempest,@VizGhar and @Westicles.
If you have any issues, feel free to ping them.
A fine puzzle, I liked it.
The most naive implementation’s time complexity would be Θ(n ** 6), where n is the grid height or width. (I did not check whether this would timeout or not.)
Using some dynamic programming approach I could do it in Θ(n ** 4), which was fast enough for such small test cases even in a rather slow language.
I am wondering: is it possible to solve this with an algo better than Θ(n ** 4) ?
It’s not too hard to find a O(n^3) algo with some bounds precalc.
I checked the contrib page after solving it in O(n^3) and a user provided a link with a O(n^2) algo.
If you want to give it a try, it uses the same precalc as in the O(n^3) solution and additionnally cleverly uses a stack to compute the other dimension bounds in amortized constant time.
1 Like
Naive approach - flood-fill every 1-cell to find its area and then trim off to become rectangle?
I am using simple loops, without dp, without precalc, and got a seemingly very fast result.
The approach is to group each line of cells into ranges or intervals so that I got some rectangles of thickness of 1. Then I tried to expand the thickness of these ranges, to merge with adj lines, and at the same time re-adjust the start and end of the ranges. Calculate the area every time I got a new different rectangle.
I tried it on some random test cases of 500 x 500. The answer comes out almost instantly, much faster then I expected. (Most time were spent in reading input of 0.5MB). It could have been helped by the local multi-core CPU and optimization by the compiler to multi-thread it, I’m not sure.