hello codeforces community,
The problem is "any entry P is eliminated if the list has any entries strictly bigger than P below the position of P."
2 9
1 6
5 3
9 6
2 5
1 5
4 8
1 1
6 5
For example: 1 1 is eliminated since there is an entry below it 6 5, which is strictly bigger than 1 1. The problem is to find the entries that are left or are not eliminated? This is a simplified version of a problem already present in codeforces so i am not creating a new problem.
The polynomial O(n^2) algorithm is obvious since we can go from bottom to top and for each entry check if there is any item bigger than it below it. My question is if this can be done in linear time or better than polynomial O(n^2) time. I hope i can get some expert eyes on this problem i am facing. Thanks!
It's easy. Take the first element: this element won't ever be eliminated. All the elements after it that are smaller than P[0] will be eliminated. The next element that's left is the first one that won't be eliminated, e.g. P[i] ≥ P[0]. If an entry was eliminated by P[0], it'd also be eliminated by P[i], so the next element left is the first one ≥ P[i]; etc.
The answer is therefore the smallest (by lexicographic sequence of indices) non-decreasing subsequence, and it can be found by a single traversal in O(N).
hey Xellos,
Sorry the post omits whitespaces...the list is supposed to be.
2 9
1 6
5 3
9 6
2 5
1 5
4 8
1 1
6 5
is your answer still valid after this clarification?
Yes, it is. The algorithm is not dependent on the type of objects in the list, as long as comparison is defined on them.
you said "All the elements after it that are smaller than P[0] will be eliminated" but how are you eliminating all the elements after it smaller than P[0] dont you have to go through all the list which makes it n^2 in worst case. I am sorry i maynot be understanding your algorithm. Can you maybe run down through the above example. I think the following could be a worst case input.
1 5
2 4
3 3
4 2
5 1
"All the elements smaller than P[0]" is an idea. Its consequence, which is used in the algorithm, is that we can easily find the next element that will not be eliminated. After we find it (P[i]), we don't care about P[0] anymore. Think about it a bit.
hey Xellos,
I ran down this example with your algorithm if i understood it. * refers to the elements eliminated so far and <- refers to the current max or P[i]
2 9
1 6
5 3
9 6
2 5
1 5
4 8
1 1
6 5 <-
2 9
1 6
5 3
9 6
2 5
1 5
4 8 <-
1 1 *
6 5
2 9
1 6
5 3
9 6 <-
2 5 *
1 5 *
4 8
1 1 *
6 5
2 9
1 6 <- (here 9, 6 doesnt eliminate this but this has to be eliminated since 4 8 is bigger)
5 3 *
9 6
2 5 *
1 5 *
4 8
1 1 *
6 5
I finally see where your problem lies now. DO NOT WRITE ARRAY ELEMENTS VERTICALLY! When you say "below", I believe you refer to smaller indices, but it's actually the line number.
UPD: How do you define comparison on pairs, anyway? If it's the usual "compare first elements, if equal compare second elements", then 6 5 eliminates all below 9 6 and 9 6 eliminates all above itself.
Note that comparison must be able to sort elements in some order so that if a < b and b < c, then a < c. If this (transitivity) doesn't hold, then my algorithm fails — but then again, we don't say "bigger" in that case.
Xellos is basically correct, but a minor detail: something is eliminated if there is an element below it that majorizes it, not one above. As such you have your indices reversed — the element on the bottom is the one that will never be eliminated. Then we can work backwards, and it works exactly as he described.
The point is that, for any given element, we don't need to check every element in the list below it to see if it is eliminated. It is enough to instead check it against the smallest element below it, which we just calculated in the previous state. So if we just keep track of the smallest element as we go along we save lots of time.
EDIT: Ah, I made the same mistake as Xellos. I'll think about it some more, but it seems at first glance like it would suffice to keep two "minimums" based on the first and second numbers, updating them when we get a bigger x or bigger y respectively. In your example the minimums work like:
So if we treat this as a list of n size m lists this gives a complexity of O(nm).
N log(N) approach is quite straightforward, you just need to transform the way you would formulate a query. So for example you're thinking about adding (1, 1) point. Let's call first part of this pair X and the second part we will call Y. So instead of asking whether you already have anything strictly greater than (X, Y), you can ask a simplier question which is "whether the maximum Y on the [X + 1 ; Infinity) segment is greater than your given Y. With (1, 1) entry it will be "whether maximum Y value with X from [2 ; +Infinity) range is greater than 1. If that condition holds then you have a point which is strictly bigger than the one you're adding.
So the only thing you need for this task is some structure which will allow these two operations: — update value at some point. This happens when you add a new point — query max value on some range.
You can use BST or segment tree for that.
Then you just go from bottom to top and for each point check whether there is any strictly bigger point already added. If yes then just skip this one. Otherwise add it.
BTW, on e-olimp there is a more sophisticated version of this problem where points might have up to 4 dimensions: http://www.e-olimp.com/en/problems/100