I have to say that the most important thing to notice is to participate when the server is not heavily in queue. The problems are not bad but the queue (at least for 2023 when I was a participant and 2021 from what I heard) was unbearable.

I agree. evenvalue orz.

I hope NeroZein doesn't clown like he did in TST day 2

CM, xD.

It is because of different timezones.

So that, everybody is at ease and nobody has to stress out to follow the chosen timeslot.
Otherwise, multiple people would have time zones and other scheduling problems.
Also, Read the rules, it says: Every participant is expected to show good sportsmanship by following the rules.

ideograph_advantage

I think we should wait until the contest is over before discussing problems publicly.

First, we can make $$$4$$$ arrays $$$gr, gl, sr, sl$$$ which stores for index $$$i$$$, what's the nearest greater value to the right, to left and smaller value to left and to right. This can be done using stack in $$$O(n)$$$. Now, let's consider the edges (there is an edge between $$$(i, j)$$$ if we can go from $$$i$$$ to $$$j$$$ in $$$1$$$ move i.e all elements in between are between $$$a_i$$$, $$$a_j$$$). Important thing to notice is that, we will take the edge which brings us closest to $$$r$$$ (considering the query $$$(l, r)$$$). Also, another observation is that it is easily determinable that whether $$$a_i$$$ is a min-point or max-point. We can just check that whether $$$a_{i + 1}$$$ is less or greater than $$$a_i$$$ and then we can't have $$$a_i$$$ as min if $$$a_{i + 1}$$$ is less than it (similar for other case).

Assume that $$$a_i < a_{i + 1}$$$ since other case is similar. Now, $$$a_i$$$ is min and we want the max points. Note that the edges from $$$i$$$ are going to the changes in the max as we go towards right from $$$i$$$. Now, where will the last edge be? It will be to the maximum in the valid range. What is a valid range? the range will be valid such that the min point $$$i$$$ does not change. So, beyond $$$sr_i$$$ (the first index to the right of $$$i$$$ which have smaller value than $$$a_i$$$)we don't have any edge outgoing from $$$i$$$. So, we just get the max in the range $$$[i, sr_i)$$$. Now, we have $$$O(n)$$$ edges added in $$$O(n \space lg(n))$$$.

We can also do binary lifting and store where do I land when I take $$$2^x$$$ edges.

Now, when the query comes, we just go to the rightmost point we can from $$$l$$$ which is $$$\leq r$$$. What to do after that? We can now just do the same things we did for going in the right direction, for the left direction. Now, we starting going left from $$$r$$$ (using binary lifting). And we want the minimum jumps needed to get $$$r \leq l$$$. Now, we add both of the steps and we are done.

Proofs of the observations are not hard, I believe that you should try them.

#include <bits/stdc++.h>
// #include "stub.cpp"
using namespace std;

const int N = 3e5 + 10, LG = 19;
int n, sr[N], gr[N], sl[N], gl[N], pos[N];
int jump_right[N][LG], jump_left[N][LG], MAX[N][LG], MIN[N][LG];

vector<int> a;

int get_max(int l, int r){
    int lg = 31 - __builtin_clz(r - l);
    return max(MAX[l][lg], MAX[r - (1 << lg)][lg]);
}

int get_min(int l, int r){
    int lg = 31 - __builtin_clz(r - l);
    return min(MIN[l][lg], MIN[r - (1 << lg)][lg]);
}

void init_permutation(int N, vector<int> A){
    n = N, a = A;
    for (int i = 0; i < n; i ++)
        pos[a[i]] = i;

    stack<int> st;
    for (int i = 0; i < n; i ++){
        sl[i] = i;
        while (st.size() and a[st.top()] > a[i])
            st.pop();

        if (st.size())
            sl[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();

    for (int i = 0; i < n; i ++){
        gl[i] = i;
        while (st.size() and a[st.top()] < a[i])
            st.pop();

        if (st.size())
            gl[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();

    for (int i = n - 1; i >= 0; i --){
        sr[i] = i;
        while (st.size() and a[st.top()] > a[i])
            st.pop();

        if (st.size())
            sr[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();

    for (int i = n - 1; i >= 0; i --){
        gr[i] = i;
        while (st.size() and a[st.top()] < a[i])
            st.pop();

        if (st.size())
            gr[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();

    for (int i = n - 1; i >= 0; i --){
        MIN[i][0] = MAX[i][0] = a[i];
        for (int step = 1; step < LG && i + (1 << step) <= n; step ++){
            MIN[i][step] = min(MIN[i][step - 1], MIN[i + (1 << (step - 1))][step - 1]);
            MAX[i][step] = max(MAX[i][step - 1], MAX[i + (1 << (step - 1))][step - 1]);
        }
    }

    for (int i = n - 2; i >= 0; i --){
        if (a[i + 1] < a[i]){
            if (gr[i] != i)
                jump_right[i][0] = pos[get_min(i, gr[i])];
            else
                jump_right[i][0] = pos[get_min(i, n)];
        }
        else{
            if (sr[i] != i)
                jump_right[i][0] = pos[get_max(i, sr[i])];
            else
                jump_right[i][0] = pos[get_max(i, n)];
        }

        for (int j = 1; j < LG; j ++)
            jump_right[i][j] = jump_right[jump_right[i][j - 1]][j - 1];
    }


    for (int i = 1; i < n; i ++){
        if (a[i - 1] < a[i]){
            if (gl[i] != i)
                jump_left[i][0] = pos[get_min(gl[i], i + 1)];
            else
                jump_left[i][0] = pos[get_min(0, i + 1)];
        }
        else{
            if (sl[i] != i)
                jump_left[i][0] = pos[get_max(sl[i], i + 1)];
            else
                jump_left[i][0] = pos[get_max(0, i + 1)];
        }


        for (int j = 1; j < LG; j ++)
            jump_left[i][j] = jump_left[jump_left[i][j - 1]][j - 1];
    }
}

int calc_f(int l, int r){
    int ope = 0;
    for (int i = LG - 1; i >= 0; i --){
        if (jump_right[l][i] <= r and jump_right[l][i] > l){
            l = jump_right[l][i];
            ope += (1 << i);
        }
    }

    for (int i = LG - 1; i >= 0; i --){
        if (jump_left[r][i] > l and jump_left[r][i] < r){
            r = jump_left[r][i];
            ope += (1 << i);
        }
    }

    return ope + (l < r);
}

I tried my best to divide the solution into reasonable parts, hopefully it'd be helpful.

P.S: It appears that there are some similarities between my sol and the sol above, which wasn't there when I started writing the comment.

+25 submission limit

Sadly no :(

Although from Monday onwards it can be discussed, so wait for Monday :))))

You can discuss problem when the rank list come out.

Yes, there are countries participating now

After 2-3 days of analysis mode. (info source being [email protected])

But this year the problems were easy, especially problem A

Wow, how dare you get full points on problem C :)

If a person from each country replied with the scores of their official participants there would be less trolling

Since people are apparently too childish, please reply to the comment with your scores and I will add you manually. Thanks.

UZB top 6

Sunnatov — 100 + 40 + 5 = 145
Husanboy — 100 + 10 + 5 = 115
heaven2808h — 100 + 10 + 5 = 115
MardonbekHazratov — 100 + 10 + 5 = 115
Alfa — 100 + 5 + 5 = 110
rshohruh — 100 + 5 + 5 = 110
rythm_of_the_knight = 100 + 5 + 5 = 110

Korea

At least 2 300s and at least 1 235

This is in meme territory.

💀

China's that one country where the first rank page is just filled with red users who are prob younger than 16....

I heard 59... did you not count the CHN IOI team?

On the flip side, CHN IOI team member ranks outside top 300? :manual-doge

I wonder how they will decide the official participants. There must be 6 from each country, right?

I think all of the countries finished taking the APIO can you tell me the full solution for C 100 points?

I agree. In my country the competition was only about 15 points because of easy problem A and hard BC. Maybe we have skill issue, but it's still bad to be able to get A in the first 20 minutes and struggle to get anything else the rest of the contest

I had the $$$O(n \sqrt{n \log n})$$$ solution during the contest but I didn't want to code it since the TL was 1s and $$$n$$$ was up to $$$10^5$$$, why weren't there any subtasks rewarding that solution especially that there aren't that many subtasks to think of in P2 and P3 :))

What is $$$n$$$ (in the third problem)?

Can you explain more about the solution of B?

Cool! Then one of the solutions would be to sample and encode the points of polynomial with degree k such that at least k+1 points will survive.

Reasonable but it is impossible to have a perfect checker, so many solutions based on rng still works. For example, the 'best solution' so far requires 615 vertices in the worst case, but 75 vertices is able to pass all test cases. So the max n where you can get full marks can't be lower than 615 (unless better solutions are found), and some 'bad' solutions can still pass. Also, the solution mentioned above is obviously too easy for a problem C of APIO.

The issue (not really, but) is that the author didn't have a key idea for solving this problem in smaller $$$n$$$. If they did know, there would be a lot of ways to improve the problem anyway (one of them would be the grader strategy).

i think 115 is actually a high score

I got 240 in APIO. So my Codeforces rating is supposed to be $$$3143 \div 115 \times 240 = 6559$$$ :)

orz Kevin

I got 300 in apio. So my Codeforces rating is supposed to be 8199.

is it cutoffs? And what is copper?

Are these cutoffs only based on China's scores, or all scores?

So Which is true

56 chinese 300 or this cutline

but if u have a bigger n it is still OK to pass.

What I mean is that this solution can beat the author, but I did pass this question using $$$n=75$$$ during the competition, and I can also guarantee to pass it when $$$n=615$$$.