[SOLVED] Finding counter example (misunderstanding)

Правка en5, от Mohammed2002, 2021-03-24 11:14:29

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

Теги #c++, #logic, counter sample, #cses_searching

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Mohammed2002 2021-03-24 11:14:29 19
en4 Английский Mohammed2002 2021-03-24 11:08:54 17
en3 Английский Mohammed2002 2021-03-24 11:06:59 558
en2 Английский Mohammed2002 2021-03-23 23:12:39 10
en1 Английский Mohammed2002 2021-03-23 22:02:56 2492 Initial revision (published)