CSES - Collecting Numbers

help
,
22

1st traversal : 1 3
2nd traversal : 2 4

23

Your task is to collect the numbers from 1 to n in increasing order
1st transversal: 1
2nd transversal: 2
3rd transversal: 3 4

24

what should be the output for:

I/P: 3 2 1 5 4

25

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
26

@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
27

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.

28

Correct answer is 3, you didnā€™t understand the question correctly, read the problem again carefully

29

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ā€¦ :sweat_smile: :sweat_smile:

1 Like
30

Got it ,loved it

1 Like
31

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

32

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