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

2 different ways of DFS
Posted by - GO - 7 Mar 2005 13:13
this algo got TL
choose the row for each ships
ship 1  try [1,...,m]
ship 2  try [1,...,m]
...
ship n  try [1,...,m]

you could get TLE even you've bounded it (sorting)


another algo ,which is AC
fill the row until full
row 1  try 2^n
row 2  try 2^(n-1)
...
row m  try 2^(n-(m-1))

2^n looks bad but it works!
Re: 2 different ways of DFS
Posted by Krayev Alexey(PSU#2) 17 Jul 2005 01:56
the first way is also possible, you just need some inventiveness to think out good euristic. i got ac in 0.734
Re: 2 different ways of DFS
Posted by blue shading 11 Feb 2006 19:13
Why does the 2nd algo much better? Could U give a little explanations?
Although I got Aced in 200s, but i am not quite clear about that. I think it should be more important to find more questions than just solve it and go.