Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
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!
It’s a timeout because my O(n^3) Python script used to timeout too.
Seriously? More efficient than an O(n3) for that kind of algo? Do such thing exist?
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.
It’s actually what I’m doing, yet I still can’t pass that time out.
Do you have any tips?
Oh! I might have an idea …
@olinox14 Actually it depends on what you call n.
If n = max(W,H), then O(n^3) is ok (but of course if n = W*H, then it’s not).
Thanks @java_coffee_cup and @Niako for your answers (and sorry for the late reply). I managed to pass the validators since then: this was not a timeout in the end, but a mistake of mine in the adaptation of the Kadane’s subarray algo for a 2d array…
Thanks again!