.

There seems no.

Practice problems have nothing to do with scores and rankings in the official competition, so I think you can discuss problems anytime you want. I have been seeing several discussions on practice problems in some Chinese cp forums.

The Australian team is reporting 35-40 minute judging queues

As a participant from Macau, I can say that during peak hours we have an hour of delay. Sad…

I don't think the contest window is over yet.

Now after the contest is over, there is analysis mode on CMS. Here you can upsolve the problems.

https://apio2023.org/ranking

But they haven't post the ranking on there yet, probably because they need to check if there are any cheaters or something like that.

It is likely to be segment tree $$$O(n\log n)$$$ or divide and conquer with Fenwick tree $$$O(n\log^2n)$$$ or something else huh.

The first idea is to use binary search to find the answer.

Let's now check if answer $$$mid$$$ is doable. (We check if there're $$$[l, r]$$$ where number of times a median appears is $$$\geq mid$$$)

The key idea is go from smaller values of medians to bigger ones, and check if there's a segment with median value equal to some $$$x$$$. (check for $$$x$$$'s from 1 to n).

How do we do that? Let's put 1s on positions with values > $$$x$$$, and -1s on positions with values < $$$x$$$. Then when segment $$$[l, r]$$$ is acceptable? When $$$|pref_{r+1} - pref_l| \leq W(x, l, r)$$$, where $$$pref_i$$$ is sum of -1's or 1's over $$$j < i$$$.

This probably gives us somthing like $$$O(n^2)$$$, but we want faster!

I don't really like our way of checking if $$$[l, r]$$$ is acceptable, we use abs there, maybe, we can do simpler? It turns out we can.

Let's say that $$$[l, r]$$$ is acceptable if $$$pref_{r+1}$$$ is equal to $$$pref_l$$$. Wait? How?

What does $$$|pref_{r+1} - pref_l| \leq W(x, l, r)$$$ mean? It means that $$$pref_{r+1} \leq pref_l + W(x, l, r)$$$ and $$$pref_l - W(x, l, r) \leq pref_{r+1}$$$

Then imagine our condition $$$pref_{r+1} = pref_l$$$ as putting 1's, -1's and 0's on some $$$x$$$'s in $$$[l, r]$$$.

Let's say we're given some $$$i, j$$$ such as $$$i < j$$$ and know than $$$W(x, i, j)$$$ is equal to $$$mid$$$. Let's try checking if there are some $$$l$$$ and $$$r$$$ such as $$$l \leq i, j \leq r$$$ and $$$[l, r]$$$ is acceptable.

Now, notice that our array consist of only 1s, 0s and -1s! That means than if $$$mn_j$$$ is $$$\min(pref_r)$$$ among $$$j \leq r$$$ (same for $$$mx_j$$$), then we can find every value of $$$mn_j \leq pref_r \leq mx_j$$$ in a segment $$$[j, n - 1]$$$!

You can apply the same logic for $$$i$$$ ($$$mn_i$$$ is $$$\min(pref_l)$$$ among $$$l \leq i$$$).

Now, we have to check if there're $$$[l, r]$$$ with $$$pref_{r+1} = pref_l$$$, so we just have to check if segments $$$[mn_i, mx_i]$$$ and $$$[mn_j, mx_j]$$$ intersect :)

But you have to be a bit careful here, since remember, we put 1s, -1s and 0s on some $$$x$$$'s. (What I did in my code was decrease $$$mn_j$$$ by $$$2 \times mid$$$).

Now, we're almost done :) Say $$$adj_x$$$ is a list of appearences of $$$x$$$ in our array. Let's summarize what we do: Go from smaller $$$x$$$'s to bigger ones

for (int i = 0; i + mid <= adj[x].size(); ++i)
    //check if there're l <= adj[x][i] and r >= adj[x][i + mid - 1] satisfying the conditions.

That gives us something like $$$O(n \log^2 n)$$$. To achieve $$$O(n \log n)$$$ you can memorize every query, and then check for $$$[i, j]$$$ in $$$O(1)$$$. I used two pointers, trying to increase the answer by 1 every time.

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) {
    return {min(a.first, b.first), max(a.second, b.second)};
}

constexpr int inf = 1e9 + 7;

constexpr pair<int, int> neutral{inf, -inf};

namespace SegmentTree {
    constexpr int N_ = 1 << 20;
    pair<int, int> t[N_];
    int tag[N_];
    int sz = 1;

    void init(int n) {
        sz = 1 << __lg(n) + !!(n & (n - 1));
        fill(t, t + sz * 2, neutral);
        fill(tag, tag + sz * 2, 0);
        for (int i = 0; i < n; ++i) {
            t[i + sz].first = t[i + sz].second = i;
        }
        for (int i = sz - 1; i > 0; --i) {
            t[i] = t[i << 1] + t[i << 1 | 1];
        }
    }

    void rangeAdd(int l, int r, int d, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            t[x].first += d;
            t[x].second += d;
            tag[x] += d;
            return;
        }
        int mid = lx + rx >> 1;
        rangeAdd(l, r, d, x << 1, lx, mid), rangeAdd(l, r, d, x << 1 | 1, mid, rx);
        t[x] = t[x << 1] + t[x << 1 | 1];
        t[x].first += tag[x], t[x].second += tag[x];
    }

    pair<int, int> rangeSum(int l, int r, int x = 1, int lx = 0, int rx = sz) {
        if (l >= rx || lx >= r) {
            return neutral;
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int mid = lx + rx >> 1;
        pair<int, int> res = rangeSum(l, r, x << 1, lx, mid) + rangeSum(l, r, x << 1 | 1, mid, rx);
        res.first += tag[x], res.second += tag[x];
        return res;
    }
}


int sequence(int n, std::vector<int> a) {
    vector<vector<int>> adj(n);

    for (int i = 0; i < n; ++i) {
        adj[--a[i]].push_back(i);
    }

    int ans = 1;

    SegmentTree::init(n + 1);

    for (int x = 0; x < n; ++x) {
        for (int i : adj[x]) {
            SegmentTree::rangeAdd(i + 1, n + 1, -2);
        }
        for (int i = int(size(adj[x])) - 1; i >= 0; --i) {
            SegmentTree::rangeAdd(adj[x][i] + 1, n + 1, 2);
            pair<int, int> resL = SegmentTree::rangeSum(0, adj[x][i] + 1);

            while (i + ans < size(adj[x])) {
                int r = i + ans;
                pair<int, int> resR = SegmentTree::rangeSum(adj[x][r] + 1, n + 1);
                resR.first -= 2 * (ans + 1);

                if (max(resL.first, resR.first) <= min(resL.second, resR.second)) {
                    ans += 1;
                } else {
                    break;
                }
            }
        }
        for (int i : adj[x]) {
            SegmentTree::rangeAdd(i + 1, n + 1, -2);
        }
    }

    return ans;
}

There is a more straightforward $$$O(n\log n)$$$ solution though with a seemingly larger constant factor, but it passes anyway.

We first find the answer for each $$$v$$$ when $$$v$$$ is the median of some range. First we show how to check whether a set has $$$v$$$ as its median. If we denote $$$h,c,l$$$ as the number of values strictly larger, equal to, and strictly smaller than $$$v$$$ in the set respectively, then it's easy to see that the condition it has $$$v$$$ as its median is that $$$h\le c+l$$$ and $$$l\le c+h$$$. Thus, if we denote $$$sh_i,sc_i,sl_i$$$ as the prefix sum of the three values in the original array, then a range $$$[l,r]$$$ will have values $$$sh_i,sc_i,sl_i$$$.

Assume that we already have these values, then how to get the answer quickly? We can rewrite the constraints as $$$-c\le h-l\le c$$$. Note that we only care about how many times $$$v$$$ occurs in the final range, thus we first take all occurences of $$$v$$$ in the array, say $$$p_1,p_2,\cdots,p_k$$$, and first check for $$$i\le j$$$ whether it is possible that $$$p_{i-1}<l\le p_i$$$ and $$$p_j\le r<p_{j+1}$$$ (here we assume $$$p_0=-1$$$ and $$$p_{k+1}=n+1$$$). Since we care about the value $$$h-l$$$, we say $$$v_i=h_i-l_i$$$ and $$$sv_i$$$ is the prefix sum of $$$v_i$$$. Then for a pair of $$$i,j$$$, we can first calculate the sum of $$$v_x$$$ for those $$$p_i\le x\le p_j$$$, since these part will always be counted towards the answer. Then notice that $$$v_i\in {-1,0,1}$$$, which means that if $$$l$$$ and $$$r$$$ move in a range, the sum of $$$v_i$$$ will also move in a range. Since the constraint is also a range, we shall just find the minimum and maximum possible values of the sum. If we have all values of $$$sv_i$$$, then it's just a simple range minimum/maximum, which can be done easily.

However, we can only find the answer quickly for a fixed pair of $$$i,j$$$, but we cannot iterate through all $$$i$$$ and $$$j$$$. Now we try to find a minimum $$$i$$$ for a $$$j$$$ that is possible. Now this is the boring and standard part, we can do some reform and rewrite the constraints in the form $$$F_1(i)\le F_2(j)$$$ and $$$G_1(i)\le G_2(j)$$$, where each $$$F(i),G(i)$$$ are values related only to the sum and suffix max/min for each range $$$(p_{i-1},p_i]$$$. Since there are $$$O(n)$$$ ranges in total for all $$$v$$$, we can get all these values directly. What's left is to do a point add rectangle some, which can be done in $$$O(n\log n)$$$ time using sweepline.

The only problem left is how to maintain the value $$$sv,sc$$$ of all places and supports query range minimum/maximum. We can use segment tree to do this. We iterate through $$$v$$$ from $$$1$$$ to $$$n$$$, then the changes to the values can be seen as range add for each occurence of $$$v$$$, which will happen $$$O(n)$$$ times in total. This is a simple segment tree problem. Thus we get a $$$O(n\log n)$$$ solution.

You almost got me

Maybe no one wants to solve that sub?

Well 144 (my score) seems quite common so far so probably bronze cutoff will be 147 (100/35/12)

I almost asked everyone what they got and this is the list.

China: About half of the gold medals are 266 pts. LOL.

`

From what I've heard, it might be a problem with cms and not with the host's resources, but either way it has to be fixed

I don't know if they've been uploaded anywhere yet, so here you go until then. The order they were presented in is: cyberland, sequence, abc.

Shouldn't the tasks and solutions be out by now

its uploaded at http://apio2023.org/tasks

nobody got points on notice? disappointed...

anyone know the cutoffs?

😭😭😭

It seems that Taiwan is not included in the list (probably there is some name format mismatch between the personal schedule and the ranking). From my calculation (including every country/region regardless of whether they are guests or not), the cutoffs are:

• Gold: 236
• Silver: 191
• Bronze: 145 (Since there will be exactly 106 participants greater or equal to 144 points, and thus the cutoff is 145)

I had the same numbers that LittleCube got. I've checked that everyone on this list showed up in calculation so it should be correct.

Weird how they didn’t include the other sri lanka participants who were tied for 0

This is indeed weird.

I and some other people also independently made our own standings based on the participant's scores, and all of them has cutoffs that match Bakry's cutoffs (see his comment above).

Unless they made some assumptions I am not aware of, the official standing is not following the APIO regulations.

Btw they changed it to 194

UPD: they changed it again to 191 it seems like they’re facing some problems