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…
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.
1st traversal : 1 3
2nd traversal : 2 4
Your task is to collect the numbers from 1 to n in increasing order
1st transversal: 1
2nd transversal: 2
3rd transversal: 3 4
what should be the output for:
I/P: 3 2 1 5 4
1st traversal :- 1
2nd traversal :- 2
3rd traversal :- 3 4
4th traversal :- 5
so the answer is 4.
The question statement is kinda confusing it is saying we have to overall pick number in ascending order.
Try to do this way.
suppose you picked
1st traversal :- 1
2nd traversal :- 2 4
3rd travesal :- 3 5
and form and array
1 2 4 3 5 But this is not question wanted us to solve. Basically, question wants us to pick consecutively then only will valid.
2 Likes
@cubefreak777 I think what @lriuui0x0 is asking is 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 your algo, 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) but it could be pos(x+1) > pos(x-2)
1 Like
I think your logic fails for some cases…
Just try this…
2 1 4 3
The answer according to your logic is 3… but actually it’s 2.
Correct answer is 3, you didn’t understand the question correctly, read the problem again carefully
Ok sorry!! my bad… i thought that i have to pick up numbers in increasing order… actually i got confused in the language of two different questions… 
1 Like
Got it ,loved it
1 Like
how test case given on site
5 3
4 2 1 5 3
2 3
1 5
2 3
gives 2 3 4
in last case
arr = 3 2 1 5 4
and increasing sequences wew can collcet would be 3 5 and 1 4 and 2. so answer should be 3 instead of 4
int n;
cin>>n;
setst;
int ans=0;
for(int i=0;i<n;i++){
int x;
cin>>x;
if(st.find(x-1)==st.end())ans++;
st.insert(x);
}
cout<<ans<<endl;
}
this is my code and it has accepted