Discussion @ 1031. Railway Tickets @ Timus Online Judge

How do you solve this problem very fast , what's the time complexity. please give me some hint. here or piyawut@se-ed.net

Posted by MadPsyentist/Sam 2 Feb 2002 21:27

Re: How do you solve this problem very fast , what's the time complexity. please give me some hint. here or piyawut@se-ed.net

Posted by Jordan 21 Feb 2002 10:33

> The Time complexity is o(n^2),is it fast enough?

Re: How do you solve this problem very fast , what's the time complexity. please give me some hint. here or piyawut@se-ed.net

Posted by Pete Lupherenko 24 Apr 2002 23:45

>>The Time complexity is o(n^2),is it fast enough?
I think yes, but there is a rather simple solution with the
complexity of O(n).
It's really simple, just do some thinking :o)

Besides, I think I can't explain the idea in English... :(

Re: How do you solve this problem very fast , what's the time complexity. please give me some hint. here or piyawut@se-ed.net

Posted by lotus4h 17 Apr 2008 15:56

Yes...You can use DP to solve.but not DFS or other searching method..

Discussion of Problem 1031. Railway Tickets