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

Raman Gupta how to choose from which town to start? [4] // Задача 1463. Радость населению! 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.

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: how to choose from which town to start? [3] // Задача 1463. Радость населению! 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.

Raman Gupta Re: how to choose from which town to start? [2] // Задача 1463. Радость населению! 31 мар 2013 21:52

Edited by author 05.04.2013 16:20

Edited by author 05.04.2013 16:20

Raman Gupta Re: how to choose from which town to start? // Задача 1463. Радость населению! 5 апр 2013 16:17

Finally AC! Slight implementation change got me AC!.

Raman Gupta Re: how to choose from which town to start? // Задача 1463. Радость населению! 5 апр 2013 16:19

Edited by author 05.04.2013 16:19

Edited by author 05.04.2013 16:19

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