10902  Pickup Sticks
Moderator: Board moderators
10902  Pickup 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.
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..
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..

 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...
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...
hmm, i think this is not correct algo;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)
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
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).
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).

 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.
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.
qe
I also agree that no more than 1000 sticks are on the top anytime,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.
(it seems to subn^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..

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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.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).
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.Adrian Kuegel wrote: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.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).
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
hm... it's a sweepline algorithm where your event points are in increasing order along some line (like xaxis)... 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 .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).
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 .

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
I am not sure how to speed this one up, hope someone can help me.
What I do (in Java, mind you) is read segments in and compare them with previous ones that are still unmarked. If any of these intersect with the last one, I mark them.
In the end I just print the list of unmarked ones.
I use array of segments and array of flags, nothing else. Maybe I should use some dynamic structure, but Java 1.1 is very limited in that sense and I really don't feel like reinventing the wheel.
Darko
What I do (in Java, mind you) is read segments in and compare them with previous ones that are still unmarked. If any of these intersect with the last one, I mark them.
In the end I just print the list of unmarked ones.
I use array of segments and array of flags, nothing else. Maybe I should use some dynamic structure, but Java 1.1 is very limited in that sense and I really don't feel like reinventing the wheel.
Darko