# 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  ;
}

2 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;
}


2 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?

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?

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.

can you explain the second variation of this question

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 ;
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 ;
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() ;
}
}

3 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.