CSES - Collecting Numbers

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.

1 Like

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