CSES - Collecting Numbers

https://cses.fi/problemset/task/2216

what approach can we use to solve the problem

I’ll share my approach, so the main observation is the following :
If the number x occurs before x+1 then you can always take both of them in a single round and hence it won’t contribute anything to the answer but if x comes after x+1 then we cannot take them in the single round hence we add 1 to the final answer.

AC_CODE_1
#include<bits/stdc++.h>
using namespace std ;
int main(){
  int n,ans=1 ;
  cin >> n ;
  vector<int>a(n),b(n);
  for(int &x:a)
    cin >> x,x--  ;
  for(int i=0;i<n;i++)
    b[a[i]]=i ;
  for(int i=1;i<n;i++)
    ans+=b[i]<b[i-1];
  cout << ans  ;
}
AC_CODE_2
#include<bits/stdc++.h>
using namespace std ;
int main(){
  int n,ans=1 ;
  cin >> n ;
  vector<int>a(n),b(n+1,1);
  for(int &x:a)
    cin >> x ;
  b[a[0]]=0 ;
  for(int i=1;i<n;i++)
    ans+=b[a[i]-1],b[a[i]]=0 ;
  cout << ans  ;
}
7 Likes

Thank’s I understood the approach

AC_CODE_3
#include<bits/stdc++.h>
using namespace std;
int f[200001];
int main()
{
    int n,i,ans=0;
    cin>>n;
    while(n--)
    {
        cin>>i;
        ans+=!f[i-1];
        ++f[i];
    }
    cout<<ans;
    return 0;
}

:grin:

3 Likes

Why do we add one when x+1 comes before x? Isn’t it possible that x+1 is before x but after some numbers smaller than x?

1 Like

Yes it is possible, but you have to collect the numbers in ascending order from 1 to N so we don’t care if any number less than x+1 occurs before it except if it’s x.

But just having the numbers in ascending order doesn’t mean I don’t need to care x - 1, x - 2, …? Let’s say x - 1 is before x + 1, then can’t I just reuse the sequence leading to x - 1, and add x + 1 after it? This is still a valid ascending order? Isn’t it?

No, because you’re bound to take x after x-1, If understood your point correctly

Yes it will still be an ascending sequence but not entirely, let’s say we do what you’re saying so our final sequence would look like x-1 \dots x+1\dots x (Since according to what you’re saying you’ll take x+1 after x-1 and which means you’ll take x after x+1) and hence sequence would no more be ascending.

Maybe we can leave x to another round? Sorry for keep asking, but I’m feeling this algorithm works surprisingly.

Also according to this algorithm, if x + 1 is not to the right of x, then x will be the end of this round of picking. How then do you know this algorithm will result in “collect as many numbers as possible” in each round?

Also just to double check, if one round my picking is x, x + 2, is this a valid round? Or is this invalid?

1 Like

The question says, " Your task is to collect the numbers from 1 to n in increasing order."
Now let’s dry run 2 rounds of algorithm what you’re saying. Assume that we haven’t taken x up until these rounds.
Round 1:
We took only 2 elements which are x-1 and x+1 (As you said they are in ascending order so this seems like a valid round)
Round 2:
We only took x.
Now since the question asks us to pick the numbers in ascending order and our current order of picking is \implies \underbrace{x-1,x+1}_\text{Round 1},\underbrace{x}_\text{Round 2}. Which is not ascending, hence we’re bound to take pick them in the following order \dots x-1,x,x+1,\dots

We can’t pick x after x+1

It’s invalid.

1 Like

can you explain the second variation of this question
https://cses.fi/problemset/task/2217

Just precompute the answer as we did in collecting coins 1 and for each query update the computed answer by some trivial modifications. I’ll leave you with the code, for now, tell me if you don’t get it.

AC_CODE
#include<bits/stdc++.h>
#define ar array 
using namespace std ;
signed main(){
  int n,m ;
  cin >> n >> m ;
  vector<int>a(n),b(n) ;
  for(int &x:a)
    cin >> x ,x-- ;
  for(int i=0;i<n;i++)
    b[a[i]]=i  ;
  int ans =1;
  for(int i=1;i<n;i++)
    ans+=b[i]<b[i-1] ;
  set<ar<int,2>> c ;
  auto add = [&](int i){
    if(a[i]>0)
      c.insert({a[i]-1,a[i]}) ;
    if(a[i]<n-1)
      c.insert({a[i],a[i]+1}) ;
  } ;
  while(m--){
    int i,j ; cin >> i >> j ;--i;--j ;
    add(i);  add(j) ;
    for(ar<int,2> x:c)
      ans-=b[x[1]]<b[x[0]] ; 
    swap(a[i],a[j]) ;swap(b[a[i]],b[a[j]]) ;
    for(ar<int,2> x:c)
      ans+=b[x[1]]<b[x[0]] ;
    cout << ans  << '\n' ; c.clear() ;
  }
}
4 Likes

OK I see now! I didn’t realise x, x + 2 is invalid round…

Here is my solution easy to understand : Collecting Number

1 Like

Hey , Can You Please Explain this approach…

Can you please explain this solution?

If there are any two elements k+1 and k, and k+1 occurs before k then we have to take one more round to collect k+1, so I’ve maintained a pos array in which the index of elements are stored. Now if any element in the original doesn’t satisfy the above condition, increment the answer.

your coding doesn’t work for
2 4 1 3
your code output : 3
correct output : 2

The correct output is 3, not 2.
2 4 1 3
You go back twice (from 1 to 2 and from 3 to 4), +1 for the first traversal, equals 3.