A very Strange TLE.

Правка en1, от MedoN11, 2016-07-09 21:40:58

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.

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 on my room as well couldn't find anything wrong with, and just said it's weird. That's why I'm here CF :).

I can see why this code might TLE because of a large amount of calling functions in side the recursion code, I just don't get how it happens when n = 4...

Incase you would like to have a look at the code, here you go :

https://ideone.com/HuKQK3

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский MedoN11 2016-07-09 22:00:29 3 Tiny change: ' takes 850 on CF Servers..\n' -> ' takes 850ms on CF Servers...\n'
en4 Английский 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 Английский MedoN11 2016-07-09 21:47:45 63
en2 Английский MedoN11 2016-07-09 21:42:39 144
en1 Английский MedoN11 2016-07-09 21:40:58 1174 Initial revision (published)