Обсуждение @ 1002. Телефонные номера @ Timus Online Judge

BFS or DFS

Послано coolfishchen 14 сен 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

Послано Vedernikoff Sergey 15 сен 2007 04:22

Of course! Use DP...

Re: BFS or DFS

Послано coolfishchen 15 сен 2007 07:16

Thanks.

Re: BFS or DFS

Послано Iraq WoLf 15 сен 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

Послано Vedernikoff Sergey 15 сен 2007 22:32

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

Re: BFS or DFS

Послано Alias (Alexander Prudaev) 16 сен 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

Послано AlexF [USTU Frogs] 17 сен 2007 11:40

So as DFS))

Re: BFS or DFS

Послано Alias (Alexander Prudaev) 17 сен 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

Послано AlexF [USTU Frogs] 17 сен 2007 17:29

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

Re: BFS or DFS

Послано mbaros (henc inq@ Vahagn Gevorgyan) 27 мар 2014 23:49

I also do DFS and got Time Limit on test 6

Обсуждение задачи 1002. Телефонные номера