[The collecting numbers](https://cses.fi/problemset/task/2216) problem in the CSES problem set has a [greedy solution](https://www.youtube.com/watch?v=lhhHCZYoJvs) 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]



How does the greedy algorithm for CSES problem collecting numbers work?
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.


