Discussion @ 1002. Phone Numbers @ Timus Online Judge

BFS or DFS

Posted by coolfishchen 14 Sep 2007 17:51

When I used BFS,I found it would exceed the time limit.
Does DFS also will exceed the time limit?

Re: BFS or DFS

Of course! Use DP...

Re: BFS or DFS

Posted by coolfishchen 15 Sep 2007 07:16

Thanks.

Re: BFS or DFS

Posted by Furious Wolf 15 Sep 2007 19:58

BFS got AC. I had AC, when use BFS, I dont know, why you got TL...
Maybe your progrm is incrorrect, because BFS really got AC!

Re: BFS or DFS

If BFS got AC, tests for this problem is extremely weak...

Re: BFS or DFS

Posted by Alias aka Alexander Prudaev 16 Sep 2007 12:17

you are wrong:
we can construct graph with n = 100 verticles
and BFS solve it in O(n^2)

Re: BFS or DFS

Posted by Alex Fetisov 17 Sep 2007 11:40

So as DFS))

Re: BFS or DFS

Posted by Alias aka Alexander Prudaev 17 Sep 2007 17:11

no, DFS is bad for this problem:
we must compute the shortest sequence of words
so DFS can work as slow as backtracking, exponential time

Re: BFS or DFS

Posted by Alex Fetisov 17 Sep 2007 17:29

Maybe you're right but I ment DFS with some changes)

Re: BFS or DFS

I also do DFS and got Time Limit on test 6

Discussion of Problem 1002. Phone Numbers