Hello , My name is Mohammad , I am new to competitive programming. I need some help finding a counter example to my code or to find out why it's wrong. It's a classic CSES sorting and searching problem : Collecting numbers
Please read the logic of the code before reading the actual code.
Here is my code :
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int INF = 1e10;
const int N = 1e5 + 1;
signed main(){
int n;
cin >> n;
vector <int> v(n);
for (int i = 0; i < n; i++){
cin >> v[i];
}
set < int > s;
s.insert(v.front());
for (int i = 1; i < n; i++){
int x = v[i];
auto put = s.upper_bound(x);
if (put == s.begin()){
s.insert(x);
}
else {
put--;
s.erase(put);
s.insert(x);
}
}
int ans = (int) s.size();
cout << ans << endl;
return 0;
}
The logic of the code :
I am going to explain it directly on an example (I think it's easier to explain):
5
4 2 1 5 3
I am going to visualise the set of vectors $$$s$$$ vertically for the sake of the explanation. The code starts by pushing the first element for the given vector $$$v$$$ to the set which it 4 then it start pushing elements form the vector v starting from the second element into $$$s$$$ in one of the vectors in the set in an increasing order.
The set after each iteration:
4
2
4
2
1
4 5
2
1
4 5
2 3
1
The answer in going to be the size of the set , which represent the number of rounds needed to collect the numbers. And I wanted to note that I didn't use a set of vectors in the code I used a set which represent the last element of the vectors which all it needed to be stored and I easier to implement.
What I tried:
I already tried all possible permutations for all $$$ 1 \leq n \leq 11$$$ without finding any single dismatch. Here is the code that I tried all the possible permutation : The code
PS : the wrong test case on CSES is when $$$n = 2 \times 10 ^ 5$$$ which make it hard to know what is going on in the code , but the correct output of it is : 99987 and my output is 879.
Thanks for any help in advance.
UPDATE: It turned out that I misunderstood the problem , I thought that I have to collect the numbers in an increasing order and not necessary in the order of 1 , 2 ... n. But the question want the collecting in the order of 1 , 2 ... n. However , there is a problem on Atcoder Sequence Decomposing the way I misunderstood the collecting numbers problem and my code works just fine but you have to replace the set with a multiset and upper_bound with lower_bound.