Обсуждение @ 1463. Радость населению! @ Timus Online Judge

how to choose from which town to start?

Послано Raman Gupta 31 мар 2013 00:31

I am getting TLE on test 24.
How will you choose from which town to start? Because of this I had to start from every town to find the answer. For each town it took me O(n),so for all the towns it becomes O(n^2), causing TLE.

Re: how to choose from which town to start?

Послано Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 31 мар 2013 01:49

Actually that's the main issue for this problem.
If you want a hint - that's it: try to develop some dynamic programming scheme for solution.

Re: how to choose from which town to start?

Послано Raman Gupta 31 мар 2013 21:52

Edited by author 05.04.2013 16:20

Edited by author 05.04.2013 16:20

Re: how to choose from which town to start?

Послано Raman Gupta 5 апр 2013 16:17

Finally AC! Slight implementation change got me AC!.

Re: how to choose from which town to start?

Послано Raman Gupta 5 апр 2013 16:19

Edited by author 05.04.2013 16:19

Edited by author 05.04.2013 16:19

Обсуждение задачи 1463. Радость населению!