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

coolfishchen BFS or DFS [9] // Задача 1002. Телефонные номера 14 сен 2007 17:51

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

Vedernikoff Sergey Re: BFS or DFS [8] // Задача 1002. Телефонные номера 15 сен 2007 04:22

Of course! Use DP...

coolfishchen Re: BFS or DFS [7] // Задача 1002. Телефонные номера 15 сен 2007 07:16

Thanks.

Iraq WoLf Re: BFS or DFS [6] // Задача 1002. Телефонные номера 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!

Vedernikoff Sergey Re: BFS or DFS [5] // Задача 1002. Телефонные номера 15 сен 2007 22:32

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

Alias (Alexander Prudaev) Re: BFS or DFS [4] // Задача 1002. Телефонные номера 16 сен 2007 12:17

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

AlexF [USTU Frogs] Re: BFS or DFS [3] // Задача 1002. Телефонные номера 17 сен 2007 11:40

So as DFS))

Alias (Alexander Prudaev) Re: BFS or DFS [2] // Задача 1002. Телефонные номера 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

AlexF [USTU Frogs] Re: BFS or DFS [1] // Задача 1002. Телефонные номера 17 сен 2007 17:29

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

mbaros (henc inq@ Vahagn Gevorgyan) Re: BFS or DFS // Задача 1002. Телефонные номера 27 мар 2014 23:49

I also do DFS and got Time Limit on test 6

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