## 10902 - Pick-up Sticks

Moderator: Board moderators

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### 10902 - Pick-up Sticks

I have no idea about any algorithm which is better than exhaustive search. Who can help me.
I stay home. Don't call me out.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### hm...

it seems that o(n^2) algorithm with efficient cutting makes AC,

if the number of top sticks is small.

also waterloo's solution is o(n^2).

BUT there can be worst case,

by 1st~99999th stick, every sticks are top sticks,

and 100000th stick crosses all of them;

then answer is 1 < 1000, satisfying problem's statement;

but o(n^2) algorithm will be get TLE.

i think that faster algorithm exists;

but i have no idea about it..
Sorry For My Poor English..

GeorgeBusch
New poster
Posts: 10
Joined: Fri Jun 10, 2005 5:30 pm
I think there are better solutions than O(n^2).
One easy thing is to go backwards through the sticks and do something like a sieve. If the actual stick is one of the top stick you try do find the cutting with all of the sticks thrown before.
This works in worstcase O(n*nr_of_topsticks)

Another possibility, but I cannot implement it: There exists an algorithm that finds all the cuttings in O(N*logN) i think, its described in Sedgewick.

I have another problem with the task, cause i am getting WA all the time. What should i do with sticks where one point lies on the other stick or when they are lying above each other...

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
GeorgeBusch wrote:I think there are better solutions than O(n^2).
One easy thing is to go backwards through the sticks and do something like a sieve. If the actual stick is one of the top stick you try do find the cutting with all of the sticks thrown before.
This works in worstcase O(n*nr_of_topsticks)
hmm, i think this is not correct algo;

we have 3 sticks, we put them in order 1,2,3
2 cross 1
2 cross 3
1 do not cross 3

the correct answer is 3 but the sieve algo give us 1,3

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
GeorgeBusch wrote: Another possibility, but I cannot implement it: There exists an algorithm that finds all the cuttings in O(N*logN) i think, its described in Sedgewick.
There can be O(n^2) intersections. A sub - O(n^2) algo will have to skip some of them.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Read it more carefully, the worst case is actually (n+k)log n (page 8 ) - there is also a reference to an algorithm that is k + n log n.

These are both *worse* in the worst case than n^2 (k is already in n^2), furthermore for this problem it seems that the algorithm needs to be chosen according to the input (unfortunately).

Latinboy@Taiwan
New poster
Posts: 1
Joined: Mon Sep 26, 2005 12:12 pm

### Re: hm...

[quote="wook"]
it seems that o(n^2) algorithm with efficient cutting makes AC,
if the number of top sticks is small.
also waterloo's solution is o(n^2).
BUT there can be worst case,
by 1st~99999th stick, every sticks are top sticks,
and 100000th stick crosses all of them;
then answer is 1 < 1000, satisfying problem's statement;
but o(n^2) algorithm will be get TLE.
i think that faster algorithm exists;
but i have no idea about it..
[/quote]

After my test, I'm sure that no more than 1000 sticks are on the top at anytime.
I just use arrays[1001] and got A.C.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### qe

Latinboy@Taiwan wrote:After my test, I'm sure that no more than 1000 sticks are on the top at anytime.
I just use arrays[1001] and got A.C.
I also agree that no more than 1000 sticks are on the top anytime,
(it seems to sub-n^2 algorithm was problemsetter's mean)

but in general case,
i can't find efficient algorithms.

btw, o(n^2) is enough
[/quote]
Sorry For My Poor English..

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Thank you very much, Latinboy, my Taiwan friend. The same to wook. You are right. Now I get AC.
I stay home. Don't call me out.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Quantris wrote:Read it more carefully, the worst case is actually (n+k)log n (page 8 ) - there is also a reference to an algorithm that is k + n log n.

These are both *worse* in the worst case than n^2 (k is already in n^2), furthermore for this problem it seems that the algorithm needs to be chosen according to the input (unfortunately).
I think that you need to consider only O(n) intersection points, because with each intersection you can remove the "bottom" segment; it may still intersect with some segments coming later, but they are always on top of it. I don't know though if the set of segments can be held dynamic in these algorithms.

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:
Quantris wrote:Read it more carefully, the worst case is actually (n+k)log n (page 8 ) - there is also a reference to an algorithm that is k + n log n.

These are both *worse* in the worst case than n^2 (k is already in n^2), furthermore for this problem it seems that the algorithm needs to be chosen according to the input (unfortunately).
I think that you need to consider only O(n) intersection points, because with each intersection you can remove the "bottom" segment; it may still intersect with some segments coming later, but they are always on top of it. I don't know though if the set of segments can be held dynamic in these algorithms.
if i remember correctly these algorithms only have n intersection points memorized in their event points structure at any given time, but they can have O(n^2) removements / insertions of such (potential) intersection points during the course of the algorithm.

regarding removal of sticks that are already classified as 'not on top'. I'm not sure wether that will work. Consider an input where a is covered by b, and b is covered by c, a, b and c inserted in that order. If you first encounter the intersection between b and c, your idea will make me remove stick b, thus preventing us from ever finding out about a being covered by b, leading to the output (a, c) instead of c only which is correct.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
My idea of removing segments is of course only correct if I process them in the input order, which may not work for the n log n + k algorithm (I don't know how it works).

dispanser
New poster
Posts: 18
Joined: Wed May 01, 2002 4:12 pm
Location: Jena/Germany
Contact:
Adrian Kuegel wrote:My idea of removing segments is of course only correct if I process them in the input order, which may not work for the n log n + k algorithm (I don't know how it works).
hm... it's a sweepline algorithm where your event points are in increasing order along some line (like x-axis)... I can't possibly see how to get these two things together. if you use the order in which the sticks are thrown you're totally breaking up your sweep state structure .

Maybe the problemsetter is reading here: I don't like problems where you have to implement algorithms that would clearly break for at least some possible inputs. During the contest, i skipped the problem because i was unable to find an algorithm below O(n^2). Those lucky enough to misinterpret the constraints where able to solve it .

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
well, maybe we could either build an AABB tree, or maybe even do some quad-partitions of the plane (each line segment is gonna intersect at most three of the four squares). this should be sub-n^2 algorithm (still n^2 in the worst case).

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am