10902 - Pick-up Sticks

[ImLazy]

I have no idea about any algorithm which is better than exhaustive search. Who can help me.

[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..

[GeorgeBusch]

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]

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]

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]

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]

[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]

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]

[ImLazy]

Thank you very much, Latinboy, my Taiwan friend. The same to wook. You are right. Now I get AC.

[Adrian Kuegel]

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]

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.

[Adrian Kuegel]

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]

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]

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]

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