So recently I was in an SRM, and was solving this problem, I will attach an image as it's not posted yet outside the applet. ( If you would like to check in the applet, it's Div1 694 250)
http://imgur.com/sLxbFSV (^There is an option to zoom in).
Each element is between 0 and 255, and size of the array is at most 50.
Solution is Dynamic Programming in O(255*255*51*8).
After the round I got TLE, I thought it was maybe Java TLEing on a max case, but instead it looks like I TLE'd on a case where n = 5 ( lol ) yet my code passes for cases where N is nearly 50. C++ as copy paste from java passes all tests in around 300ms.
Now how can my code be passing cases where N is nearly 50 yet TLE on this one ? It just doesn't make sense...I did run it on my own machine, and it was fine.
A red guy in my room as well couldn't find anything wrong with, and just said it's weird. That's why I'm here CF :).
If this is a max case, I'd try to convince myself that the recursion overhead is too much, but N is just 5..
Incase you would like to have a look at the code, here you go :
It also takes 850ms on CF Servers...
This seems pretty odd to me. It runs in 552 milliseconds on my computer. I don't use TopCoder much so I'm not sure if this is normal, but it does seem peculiar that the Execution Time and the Peak memory used are both 0. Does this mean that the program could possibly never actually start running?
Maybe Topcoder is showing the cpu time used by your program (which in this case is 0ms), but it's actually measuring the real time (which includes the time needed to allocate and initialize your matrix).
So it may be that (on Topcoder servers) the memory required by your program takes a lot of time to be allocated (a time near to the time limit).
I've seen an accepted Java solution with the same memory.
If the time required to allocate the matrix is near the time limit, then it's possible that one run out of several runs of the same program will require more time (e.g. because the operating system is busy running other things)