How does the greedy algorithm for CSES problem collecting numbers work? [closed]

Question

The collecting numbers problem in the CSES problem set has a greedy solution where we compare the position of a number x with the position of x-1. If pos(x) < pos(x-1) then we increment rounds because this means that x can't be in the same round as x-1. But what if x can go in another round that doesn't have x-1.

For ex:

suppose there are rounds like this:

… x-2
… x-1, x

So till here, I have chosen all numbers in ascending order. Meaning x-2 was put in one round, then pos(x-1) < pos(x-2) so it was put in new round. Then pos(x) > pos(x-1) so it was put in same round as x-1. Now, for x+1, suppose pos(x+1) < pos(x). According to this algorithm, x+1 would go in a new round. But what if pos(x+1) > pos(x-2) ?? It could have gone in the round that has x-2. But instead, we created a new round.

How can we be sure this doesn’t happen?

Because all we know is pos(x-1) < pos(x-2) and pos(x-1) < pos(x) but we don’t know the relation between pos(x) and pos(x-2). It could be that pos(x) > pos(x-2) and now when we choose x+1, it may be that pos(x+1) > pos(x-2) so it could go in the round with x-2 which would mean we don't have to create a new round for x+1

My approach was to count the minimum number of increasing subsequences in the array. And the minimum of that would be the answer (i.e. the number of rounds required). This is passing the sample test case and 2/3 test cases. But it doesn't work on the 3rd case.

Code:

int solve()
{
    int n;
    cin >> n;
    vector<int> a;
    for(int i=0;i<n;++i)
    {
        int x;
        cin >> x;
        x = -x;
        auto ind = upper_bound(all(a), x) - a.begin();
        if(ind < a.size())
            a[ind] = x;
        else
            a.emplace_back(x);
    }
    return a.size();
}

My logic here is, instead of finding the minimum number of increasing subsequences, I find the minimum number of decreasing subsequences. To do this, I convert each number to the negative of itself. This way, an increasing subsequence like [4, 5, 8, 12] will become a decreasing subsequence like this: [-4, -5, -8, -12]

Answer 1

I was actually confused about the problem itself. The problem stated that we had to collect numbers in an increasing order in each round. I assumed that they didn't have to be consecutive. For ex: in one round, I could have [2, 4]

But this is not the case. In the above example, I will have to pick 3 only after 2 in that round, otherwise I will have to start a new round. And no other number can now be added to that round, even if their position is after 2 and they are increasing.