CSES - Collecting Numbers

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  ;
}
1 Like

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:

1 Like