Discussion @ 1463. Happiness to People! @ Timus Online Judge

how to choose from which town to start?

Posted by Raman Gupta 31 Mar 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?

Posted by Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 31 Mar 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?

Posted by Raman Gupta 31 Mar 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?

Posted by Raman Gupta 5 Apr 2013 16:17

Finally AC! Slight implementation change got me AC!.

Re: how to choose from which town to start?

Posted by Raman Gupta 5 Apr 2013 16:19

Edited by author 05.04.2013 16:19

Edited by author 05.04.2013 16:19

Discussion of Problem 1463. Happiness to People!