Discussion @ 1689. Fisherman and Barbell @ Timus Online Judge

melkiy Algo? [3] // Problem 1689. Fisherman and Barbell 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?

Sfairat Re: Algo? [2] // Problem 1689. Fisherman and Barbell 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

OpenGL Re: Algo? [1] // Problem 1689. Fisherman and Barbell 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

Solver Re: Algo? // Problem 1689. Fisherman and Barbell 14 Jul 2026 08:29

Just slide ahead and once you step on a worm by left or right plate, increase number of times that worm was stepped on (that number will drift between 0, 1, 2). When number of plates intersecting the worm changes between 0 and 1, total amount of affected worms changes accordingly. This algo can support overlapping worms and 1e+9 coordinates with sorting of worm endpoints.

👑TIMOFEY👑`~ wa 6 // Problem 1689. Fisherman and Barbell 10 Jul 2024 12:17

3 1
2 1
2
0 1

Alexander Kouprin Test #16 [5] // Problem 1689. Fisherman and Barbell 5 Mar 2009 03:41

If you have some troubles with passing 16th test, try

20 3
10 5
5
1 4 8 12 16

Vedernikoff Sergey (HSE: EconomicsForever!) Re: Test #16 [4] // Problem 1689. Fisherman and Barbell 5 Mar 2009 15:18

I've passed test 16, but stuck on 17...
And, by the way, what is right answer on your test?

Sfairat Re: Test #16 [3] // Problem 1689. Fisherman and Barbell 5 Mar 2009 20:10

If my solution is correct(it got AC),then it's 0

OpenGL Re: Test #16 [2] // Problem 1689. Fisherman and Barbell 6 Mar 2009 01:32

I'm can't pass test #22 :(

OpenGL Re: Test #16 [1] // Problem 1689. Fisherman and Barbell 9 Mar 2009 14:55

This tests very helped me to pass test #16 and test #22:

7 3
5 2
1
1

answer 0

7 4
6 2
1
1

answer 0

Edited by author 09.03.2009 14:55

toweleen Re: Test #16 // Problem 1689. Fisherman and Barbell 27 Jan 2012 23:37

Could you explain please how to get answer 0 in your tests?
like in 1st for example:

worm is from 1 to 4 [1;4)
it means that empty part are only [0;1) and [4;7)
and I couldn't place the barbell without squashing the worm.

I'm wrong somewhere, please tell me.

Reza Wrong Answer #3 [3] // Problem 1689. Fisherman and Barbell 12 Mar 2009 16:12

Hi,

I got WA at test #3. I have applied all of the samples above to the algorithm and the program output the correct result. Any body can help me?

Reza Re: Wrong Answer #3 [2] // Problem 1689. Fisherman and Barbell 12 Mar 2009 16:14

I meant by above to the samples in the last posts.

LSBG Re: Wrong Answer #3 [1] // Problem 1689. Fisherman and Barbell 30 Aug 2009 13:54

Here are some tests that helped me pass test number 3:
Input:
8 2
4 1
7
0 0 2 3 4 6 6
Output:
2

Input:
10 2
4 1
5
0 1 4 7 8
Output:
3

Input:
20 20
2 1
1
0
Output:
0

unlucky^2 [Vologda SPU] Re: Wrong Answer #3 // Problem 1689. Fisherman and Barbell 14 Mar 2010 03:50

LSBG wrote 30 August 2009 13:54

Here are some tests that helped me pass test number 3:
Input:
8 2
4 1
7
0 0 2 3 4 6 6
Output:
2

Input:
10 2
4 1
5
0 1 4 7 8
Output:
3

Input:
20 20
2 1
1
0
Output:
0

first and second tests are not correct.
Worms cross themself.

Edited by author 14.03.2010 03:51

melkiy Test #8 TLE // Problem 1689. Fisherman and Barbell 7 Sep 2009 03:10

What this test may contain?

I find a solution O(N). On large tests on my PC i get 0.046s at N=100000, but on timus i have TLE...

I can send my solution if anybody would be so kind to look at it :)

yuyan If you have WA on #16 // Problem 1689. Fisherman and Barbell 6 Apr 2009 13:15

    Please try this test.This test helps me a lot.
    20 3
    2 1
    5
    1 4 8 12 16

    The answer is 0.

A.Z Problem discription [3] // Problem 1689. Fisherman and Barbell 28 Feb 2009 17:44

If a worm with length 1 has distance 1 from the left edge of the groove, it will be in range from 1cm to 2cm. if we put the barbell with in distance 2 from left side of groove (left edge of left plate lay on coordinate 2 ) does it squash the worm?

tanas Re: Problem discription [2] // Problem 1689. Fisherman and Barbell 1 Mar 2009 18:45

No, because a worm will be lay in range [1,2)

Vedernikoff Sergey (HSE: EconomicsForever!) Re: Problem discription [1] // Problem 1689. Fisherman and Barbell 1 Mar 2009 20:26

And if just after the barbel? I.e., if the barbel ends at 2, and I put worm at the distance 2, will it squash the worm?

tanas Re: Problem discription // Problem 1689. Fisherman and Barbell 1 Mar 2009 23:03

Style: flat | tree | nested
Thread Order: bubble | fixed

Discussion of Problem 1689. Fisherman and Barbell