This year's Asia-Pacific Informatics Olympiad (APIO) is approaching, it will be open on the 20-th of May for official participants.

It is an IOI-Style contest with 3 problems and 5 hours. You can find more information on the official APIO 2023 site apio2023.cn.

Let's discuss problems/cutoffs/results here in the comments after the contest (and the mirror, if there's any) ends.

I wish everyone participating good luck!

**UPD**: The contest has ended, you can now discuss the problems in the comments.

Good luck everyone .. Is the competition specific to the Olympics, or is it open to everyone?

.

Will there be an official mirror? If yes, where?

There seems no.

Is there any chance that the mirror will be announced after APIO finishes?

As a top gold of the last year, good luck to everyone!

Any comment from the organizers on when we can discuss practice problems?

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.

Is anybody else having trouble connecting to the CMS? It is taking a long time to get responses.

The Australian team is reporting 35-40 minute judging queues

NZ participants are getting heavy delays too.

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

Good luck everyone, I hope Vietnam's team will get great achievement.

Contest window is over I think? Anyone knows where we can upsolve?

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.

When will be cutoffs decided?

Will you put the problems to an online judge?

The contest window is over. Let's discuss the problems.

Anyone knows where the scoreboard can be accessed?

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.

How to solve B?

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

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.

CodeI've got nearly the same solution except for your last point. Unfortunately, idk if it's due to my solution's constant factor, my $$$O(n \log^2 n)$$$ sol only scored 50 points. I mean, even if the model solution is $$$O(n \log n)$$$, an additional $$$\log n$$$ factor takes away 50 points is quite painful... This is primarily due to the fact that my solution couldn't pass subtasks 3-5 (subtasks with special conditions, rather than ones with a constraint on $$$n$$$).

Well, seems like my last APIO ended with a nearly-full solution that scored 50.

Yeah, I feel like maybe subtasks with special conditions, but with smaller N would have been a better option.

Hi!

I'm sorry to hear that your solution just got 50.

When I set the problem, $$$O(n\sqrt n)$$$ and $$$O(n\log^2 n)$$$ or other non-$$$O(n\log n)$$$ complexities were expected to get $$$82$$$. Because after getting $$$50$$$, you can extend your idea to the previous subtasks(for Sub5, you can change you binary search to $$$l=1,r=2$$$, for Sub4 you can simply change your segtree to brute force, for Sub3 you just need to deal with several cases). The reason I set the other subtasks with $$$n=5\times 10^5$$$ is to let the participants think more.

However the long queue is not expected. I knew several others getting $$$50$$$ because they have no time to implent the subtasks or just simply failed. I guess the situation would be much better if there is more time.

Anyway, good luck in the future!

How can you binary search the answer?

Doesn't it fail on test case like:

Possible answers are:

And it is not possible to achieve $$$6$$$, but possible to get $$$7$$$.

Well, my solution may differ from bashkort's in some small details, but I think at least on this point, we're the same.

When bashkort says "check if answer $$$mid$$$ is doable", he/she means checking whether there's a median which appears at least $$$mid$$$ times in the subarray. Binary search is therefore valid.

We ensure that exactly $$$mid$$$ $$$x$$$'s appear in each $$$[i,j]$$$. When we have a range $$$[l,r]$$$ with $$$l \le i \le j \le r$$$ that has $$$x$$$ as its median, we know that $$$x$$$ appears for at least $$$mid$$$ times in $$$[l,r]$$$. Please correct me if i'm wrong~ lol

In this problem, you don't check "if $$$k$$$ is an answer". You check "if there is an answer $$$\geq k$$$". So you can still binary search it.

Yes, LittleCube and jophyyjh are both correct. In this problem, you check whether answer is $$$\geq mid$$$ rather than exactly equal to $$$mid$$$.

My mistake, should have said that in the beggining.

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.

Scoreboard just got released!

https://apio2023.cn/cms/ranking_unofficial

You almost got me

How to solve last subtask of C?

Maybe no one wants to solve that sub?

Anyone know when cutoffs will be decided?

Let's hear everyone's feeling. What do you think the cutoffs are going to be?

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

Lets compile a list of scores for the top 6 of each country? Maybe this would help us to estimate medal cutoffs. You can reply under this comment.

Egypt1 — Ahmadsm2005 176 (100/40/36)

2 — AbdelmagedNour 168 (97/35/36)

3 — Bakry 165 (97/60/8)

4 — Yahia_Emara 157 (97/60/0)

5 — Ahmed57 151 (100/47/4)

6 — MinaRagy06 144 (97/35/12)

Syria1 — aminsh 147

2 — BERNARD 144

3 — edogawa_something 88

4 — NeroZein 84

4 — Wael_Zaiback 84

6 — Abito 77

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

BangladeshIndiakshitij_sodani 263

blue 236

PoPularPlusPlus 169

Xc4l16r3 147

Dominater069 140

NovusStellachan 140

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

Uzbekistan1 — DilshodbekX 145 (97/48/0)

2 — Erkinoff_Mohammed 136 (97/35/4)

3 — Sunnatov 103 (68/35/0)

4 — drdilyor 100 (28/60/12)

5 — Husanboy 91 (44/47/0)

6 — Alfa 48 (20/28/0)

`

I wasn't able to see a single problem until 40 minutes passed and all of them downloaded in 65 I think. I mean everyone I knew who participated in that time window couldn't take the contest seriously because of things like this and the 20 minute queue. Can't they split everyone more equally between times in future APIO's? (feel like my grammar is shittier than usual but I just woke up, sorry for that)

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

how exactly is queue time an issue with cms and not the host's recourses? i heard there was bugs in cms with missing certain submissions, but the queue time was large for all my submissions (average around 30mins, highest 55mins)

CMS is the system in charge of the entire operation, so it can have a massive effect on performance if it is bugged. Of course hardware has the most straight forward role in queue time, but only improving it might not solve the problem. Again, those are just things I've heard, I don't know to what extent CMS is flawed, but we've been dealing with similar issue in the past year in my NOI

Cyberland ($$$O(n\log n \cdot \min(k, \log (n \epsilon^{-1})))$$$)

Sequence ($$$O(n \log n)$$$)

I don't have a solution for ABC.

Where can we find tasks?

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

The rank got released: APIO 2023 rank

It's without medals and I think there are more than 6 people in each country there.

nobody got points on notice? disappointed...

anyone know the cutoffs?

~~Judging from the result the gold cutoff is 263 or 266. I don't know if that makes sense, tho~~With a ton of Chinese getting 266 and only 6 of them counts I don't think that gold cutoff is 263-266, more like 230-240.

~~In general, if they have same score, they can not be discriminated. In APIO 2019 Korea got 13 silver medals.~~Ok I just read the regulations, you are right

I've generated the standings of official participants with my friends.

Here's the Ranking

UPD:There was an issue with not including Taiwanese contestants and official contestants who got a zero score in the medal cutoff. Now I think that everything is fixed. Please check the Ranking now.UPD 2:Added another page for the Ranking without the guest countries (Canada, Mexico, and Brazil). However, the medal cutoff hasn't changed.UPD 3:The bronze cutoff is 145. We're sorry for that! Some contestants have a different format in the contestants list and the scoreboard and we had to fix that manually. Again we're sorry for that! We've updated the Ranking with their scores.😭😭😭

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:

We fixed it now. I believe it's correct.

Please, use "China Taiwan". taiwanguo

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.

Yeah, we fixed it. There was a problem because the format of the name of Taiwanese contestants in the scoreboard isn't the same as the one in this list.

Where are the official cutoffs going to be posted?

Problems are now available on oj.uz

Official standings with cutoffs have been released.

I just don't understand, how is silver cutoff is only out of 161 points? Shouldn't it be in the 190's? There are literally more silver medalists than bronze medalists(excluding repeated top 6 from the same country). Am I missing something?

UPD: It is now fixed.

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

They changed the cut off. Silver is 194

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.

Updated again. Now silver cutoff is 191.

Btw they changed it to 194

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