Puzzle of the week - Max Rect


#1

Hi, I’m currently doing th ‘Puzzle of the week - Max rect’, and even if all the tests pass, two of the after-submitting validators (3 et 4) keeps to fail…

Is there a way to know if those failures come from an error? A timeout?

I suspect a timeout, but I’m already using an O(3) algorithm and I don’t think that it could be faster…

Thanks by advance!


#2

It’s a timeout because my O(n^3) Python script used to timeout too.


#3

Seriously? More efficient than an O(n3) for that kind of algo? Do such thing exist?


#4

Yes, such thing does exist.
Some people call it dynamic programming. Someone call it memorization. The principle is simple: if you know a + b = x, memorize it. When you want to calculate a + b + c, you should calculate x + c only. Never re-calculate the known fact (a+b). Then you have another known fact (a+b+c = y). Keep this in memory for future reuse.

Planning out how to implement it is another story. It can be challenging, interesting, and from time to time frustrating.