Discussion @ 1689. Fisherman and Barbell @ Timus Online Judge

Algo? melkiy 6 Mar 2009 04:35

My step-by-step barbell moving (though improved to add into under and out under the barbell only "right" worms without checking every worm) gives TLE on 8th test.

Is segment tree needed?

Re: Algo? Sfairat 6 Mar 2009 05:19

I solved without it.I also used "improved step-by-step barbell moving",but my solution was quite far from TLE. I modeled groove as int array,but if you use sorting on worms array and then search there some coordinates then you can possibly get TLE.

Edited by author 06.03.2009 05:20

Re: Algo? OpenGL 9 Mar 2009 15:05

I solved this problem without sorting. I found difference
d[this_step]=count[this_step]-count[prev_step],
and after that
count_squash_worm=count_squash_worm+d[this_step].

Edited by author 09.03.2009 15:06

Discussion of Problem 1689. Fisherman and Barbell