ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1115. Ships

I just used DFS and got AC with 0.001s!
Posted by Fu Dong 20 May 2005 15:30
850784 15:24:03
20 May 2005 Fu Dong 1115 Pascal Accepted
 0.001 141 KB

I think the most important thing to this problem is to sort ships' length.

First I sorted them from short to long, but I got TLE on test #8, then I sorted from long to short, to my surprise, I got AC with 0.001s!
Re: I just used DFS and got AC with 0.001s!
Posted by N.M.Hieu ( DHSP ) 7 Jul 2005 22:21
My solution is not DFS ! I think it O(x*n*MaxL)
with MaxL = Max( length row[i] , i=1..n ) .
But I haven't define how much x does yet !
Maybe x <= 10 ! I don't think your program run faster than mine because the test are not so hard.
Re: I just used DFS and got AC with 0.001s!
Posted by nickolas stoudemire 22 Aug 2007 14:05
To N.M.Hieu ( DHSP ):
  What's your way?
Re: I just used DFS and got AC with 0.001s!
Posted by N.M.Hieu ( DHSP ) 26 Aug 2007 16:57
Sorry , I'm mistaken .
Mine is backtracking .
At that time , I was too young , so ...
I used DP to reduce the time of searching in bad result .
It's hard to say clearly due to my bad english .
If you want , leave me your email-address , I will mail you my solution , it's not good to pass the tests of problem 1394 ( Ship versions 2 ) but enough to pass those of this problem .