A very Strange TLE.

Revision en4, by MedoN11, 2016-07-09 21:59:37

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 :

https://ideone.com/HuKQK3

It also takes 850 on CF Servers..

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English MedoN11 2016-07-09 22:00:29 3 Tiny change: ' takes 850 on CF Servers..\n' -> ' takes 850ms on CF Servers...\n'
en4 English MedoN11 2016-07-09 21:59:37 37 Tiny change: 'm/HuKQK3\n' -> 'm/HuKQK3\n\nIt also takes 850 on CF Servers..\n'
en3 English MedoN11 2016-07-09 21:47:45 63
en2 English MedoN11 2016-07-09 21:42:39 144
en1 English MedoN11 2016-07-09 21:40:58 1174 Initial revision (published)