Hello! I was thinking on the nature of practice and working hard today, and I noticed how most hardworking competitive programmers really like solving problems (probably common knowledge for everyone by now). This makes sense, as this would lead to solving a lot of problems, which usually leads to progress. However, the particular case of China came to my mind. I am sure that there are a lot of students there that do CP because they find it enjoyable, but the sheer number of high schoolers who are practicing ultra-hard for CP just felt mind-blowing to me. Are there really that many Chinese people who like CP very much? Or are there other factors at play? I am particularly interested as I currently don't care much about enjoying the process and just want to grind as much as possible :p

it's creepy, is there at least an option to turn it off?

TL;DR: I shuffled the array, got 100 points, and have no idea why.
(every instance of BOI here refers to the Baltic Olympiad in Informatics.)

I was working on BOI23 d1p2 yesterday, and came up with the following solution for 50 pts:

#include "bits/stdc++.h"
using namespace std;
 
int query(int i, int j) {
    cout << "? " << i << ' ' << j << "\n";
    cout.flush();
    int res;
    cin >> res;
    return res;
}
 
int main(){
    int n;
    cin >> n;
    int ab = query(1, 2), a = 1, b = 2;
    vector<int> sol(n + 1, -1);
    for(int c = 3; c <= n; ++c) {
        int ac = query(a, c), bc = query(b, c);
        if(ac < ab) {
            sol[c] = ac;
        }
        else if(ac > ab) {
            sol[b] = ab;
            b = c;
            ab = ac;
        }
        else {
            sol[a] = ac;
            a = c;
            ab = bc;
        }
    }
    sol[a] = sol[b] = ab;
    cout << "! ";
    for(int i = 1; i <= n; ++i) {
        cout << sol[i] << ' ';
    }
    cout.flush();
}

Here, there were 2 obvious optimizations:

1. Since I only need the value of $$$\min(b, c)$$$ if $$$\min(a, c) = \min(a, b)$$$, we can throw out some unnecessary queries

2. Might as well randomize the array since it might reduce such occurrences, idk ¯\_(ツ)_/¯

#include "bits/stdc++.h"
using namespace std;
 
int query(int i, int j) {
    cout << "? " << i << ' ' << j << "\n";
    cout.flush();
    int res;
    cin >> res;
    return res;
}
 
mt19937 rng(234981239);
 
signed main(){
    int n;
    cin >> n;
    vector<int> sol(n + 1, -1), people(n);
    iota(people.begin(), people.end(), 1);
    shuffle(people.begin(), people.end(), rng);
    int ab = query(people[0], people[1]), a = people[0], b = people[1];
    for(int i = 2; i < n; ++i) {
        int c = people[i];
        int ac = query(a, c);
        if(ac < ab) {
            sol[c] = ac;
        }
        else if(ac > ab) {
            sol[b] = ab;
            b = c;
            ab = ac;
        }
        else {
            sol[a] = ac;
            a = c;
            int bc = query(b, c);
            ab = bc;
        }
    }
    sol[a] = sol[b] = ab;
    cout << "! ";
    for(int i = 1; i <= n; ++i) {
        cout << sol[i] << ' ';
    }
    cout.flush();
}

And to my surprise...it got 100 points!

Looking at the official code, this seems to be the intended solution. However, even after thinking on it, I'm not really sure why it works. Why is shuffling the array so effective? (only applying optimization 1 without 2 gets you 58 points.)

I was wondering if there was anything similar to this, but for the practice session that took place today.