This year's Asia-Pacific Informatics Olympiad (APIO) will take place on the 18-th of May.

For those who don't know about APIO, it's an IOI-style competition with 3 tasks and 5 hours and it serves as one of the main team selection tests for IOI 2024 for most of the participating countries. You can find more on apio2024.org

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

Looking forward to a great contest!

I was also wondering, is getting a bronze/silver medal in APIO harder than in IOI ? and what would be a good strategy for someone aiming for them ?

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 also suffered from the long queue last year, but unfortunately we always participate in the very first hours of the window and I don't have influence over this

My country is also participating in the first hours of the first day of the window and this leaves me really surprised as it seems like the people who can determine the participate time doesn't learn from their own mistakes.

As a first-time participant, I chose a relatively early participation time unaware of this issue :(

Hopefully the queue isn't that bad.

I hope you know that you can change it.

This year's APIO judging has been moved to qoj, so I think the situation might improve significantly

Is it faster?

does qoj add up all the subtasks i got like cms or do I have to merge my codes

it adds up all the subtasks like cms.

GLHF

good luck for all participants

I'm in Hangzhou now, where it's held. Good luck!

Ann will win APIO 2024!

evenvalue will win APIO 2024!

I agree. evenvalue orz.

evenvalue I agree2.(2 is even) Hence by evenvalue thm, he will win APIO 2024!

2024 is even, which means evenvalue will win APIO 2024!

NeroZein will win APIO 2024!

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

Nah you'd win

Everyonewho gives APIO 2024 is a winner!FerjaniSassi will win APIO 2024!

In which level you have to be to get at least bronze in APIO? (first time participating)

CM, xD.

☠️

no i am specialist and i will get GOLD

not even top 6

im newbie and i will get GOLD

you are late

I am first time participating, but I'm curios about why APIO lets participants choose their start time, can it be a reason of cheating?

It is because of different timezones.

so in theory, there may be cheating? If yes, it's sad

Yes. There can be, but in general, in all of these olympiads, there is a fairly large reliance on sportsmanship or self honesty, like the team leader of any team gets the problems a lot earlier in both IOI and IMO (I don't know about other olympiads, but at least for these two I do know for sure), and if they want to, they can pretty easily share it with their team. But this obviously goes against the spirit of the olympiad (and in fact, I think for most countries, even if the team leader did that, no student would be willing to cheat), so like there's not a huge reliance on fully cheating proof regulation. Of course, they try their best, but in the end, it falls to the participants themselves to uphold the spirit of the olympiads.

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.

owoovo_shih will win APIO 2024!

This will also be the last contest of Taiwan's provincial team selection! Good luck to everyone competing for the last spot of Taiwan(Province of China)'s IOI team

ideograph_advantage

How to solve practice session A problem?

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.

ImplementationThanks.

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

initPart 1First let's make two sparse tables, one for min and one for max. Now I claim that from an element it's always optimal to go to the maximum point I can, and I'm allowed to, reach from it, to the right or to the left.

ProofProof is left as an exercise for the reader. 8 )

Part 2We'll make two more sparse tables which will store what's the maximum point to the left or right I can reach after $$$2^i$$$ moves.

Now let's find out how to even find the maximum point at the first stageI'll just do for one direction, other's exactly symmetric. Let's say I wanna find that point for some $$$a[l]$$$, we know that $$$a[l]$$$ is maximum/minimum of the range, which can be determined by $$$a[l]<a[l+1]$$$. WLOG $$$a[l]$$$ is minimum, now we find the first element that's less than and to the right of $$$a[l]$$$ which can be found using binary search + $$$O(1)$$$ sparse table query. Let's say index of it is $$$j$$$. Next find the maximum in the range $$$(l,j)$$$, let's say index of it is $$$r$$$. Now it's clear that there's an edge between $$$l$$$ and $$$r$$$ and we can't go further than using no more than one edge.

calc_fNow let's answer a query. : )

Part 1I can just use binary lifting to go to the maximum point I can reach from $$$l$$$, and is less than $$$r$$$, let's say $$$x$$$. Which's optimal according to our claim before.

What to do next, can we just return ans+1?After checking on a few examples, we find that we can't.

WLOG, $$$a[x]$$$ has next reaching point $$$>a[x]$$$, so we've that $$$a[x+1,...,r]$$$ all are $$$>a[x]$$$.

Here comes the use of the left direction sparse table , it's not gonna be useless but a life saviour here, now we apply binary lifting again to reach the minimum point we can reach from $$$r$$$ and is $$$>l$$$, let's say it's $$$y$$$. Now I claim that there's an edge between $$$a[x]$$$ and $$$a[y]$$$

Proof$$$a[x]<a[y]$$$ $$$--->$$$ $$$a[x,...y-1]<a[y]$$$

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.

thanks

I don't like the idea of counting a compilation error as a submission. Still its not that bad, but counting in the rule of 1 minute pause is too bad. It can be so frustrating sometimes.

+25 submission limit

I don't think they'll keep that in contest

Practice is over. Is there any standings?

Is there going to be a mirror?

Sadly no :(

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

When will every country participated and I can discuss problems?

You can discuss problem when the rank list come out.

According to regulation schedule, the contest window is over. But is it truly over? Are there anyone who didn't participate?

Yes, there are countries participating now

When will ranking come out

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

What if someone creates a website where everyone enters their results?

Yeah, As far as I know, in past years the contestants made temporary results before the final result.

why do we need to wait 2-3 days

~~Asia-Pacific Informatics Olympiad~~Asia-Pacific Graphs Olympiad

Anyway, I think problems were cool

But this year the problems were easy, especially problem A

[Unofficial rankings]

Please add your scores in this spreadsheet

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.

Syria top 6

Abito — 115

edogawa_something — 115

aminsh — 115

FarhanHY — 110

NeroZein — 110

YazanAlattar — 110

CPNurd — 110

Amr.7 — 110

Can you please provide the scores for each problem? Thanks.

People who got 115 got 100-10-5 , and who got 110 got 100-5-5

why only top 6?

https://apio2024.org/regulations

what if there are tons of 110 and 105's

https://apio2024.org/regulations#:~:text=same%20score%20as%20the%20sixth%20student

Can you correct the country name of the Uzb participants in excel? (mine and rshohruh's)

Mongolia Top 6

Irmuun.Ch — 115

Onolt_kh — 110

110

105

100

100

100

I don't know other's codeforces names :(

Delete the scores without cf usernames (56 china 300's) I think someone is trolling and putting them

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

I got 100+10+100=210, feeling not good due to not getting subtask 3 of problem B as TLE occurred and there wasn't much time left.

how to solve C?

Pakistan top 6

Ghulam_Junaid 100+0+100=200

Kaleem_Raza_Syed 100+0+100=200

Muhammad_Aneeq 100+10+5=115

Sir-Ahmed-Imran 100+5+5=110

M.UmairAhmadMirza 100+5+5=110

Muhammad-Saram 100+5+5=110

China

56 300s.

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

Guys I totally did not write a random solution for C and got either only st3 correct or both st2 and st3 correct, and in the end wrote a sol for st1 specifically!!!

There were no dependencies set !!!

In my opinion, not a good contest.

The first problem is too easy. It is probably the easiest one in APIO for years.

The second problem is good. A good problem about DP optimization and persistent DS. The official solution is a bit hard (even a LGM failed to pass the problem), but some algorithms with $$$O(n\sqrt{n\log n})$$$ passed.

But the third one is 'fantastic'.

The official solution is long and extremely hard, while there is a much easier solution which can pass at about n=75 in all test cases, and about n=600 at the worst case (if the interactive lib is perfect, which is obviously impossible). What's more, the problemsetter put an $$$X \le 25,000,000$$$ which is supposed to lead the contestants to approach the solution, but it made many people try to solve T2 (at least in China) and some of them failed, getting a low score; while some successfully gets 100 points in T3 using easy solutions.

It's amazing that NOBODY found the easy solution of T3 before the contest.

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

This is a very genius solution I heard from someone in the Errichto server: Connect for all $$$2 \le i \le n$$$, the vertices $$$X \pmod{i - 1} + 1$$$, and $$$i$$$. Clearly the first vertex is always less than the second, so there cannot be any cycles. On the other hand, the graph has exactly $$$n - 1$$$ edges. Thus, it must be a tree. In order to restore the answer, you can use CRT (chinese remainder theorem).

Sorry I was wrong.

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

In India, we have like 10 people at 115 (and some people like me got 110, because they were trying to do P3 subtask 2 the whole contest instead of implementing the remaining subtask on P2 but failed).

I had a solution for p2 subtask 3 but I failed

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 :))

On the technical committee end, I saw a whole bound of n^{1.5}logn get by in between 200-400ms.

2 and 3 both could have had much harder subtasks: trying to get people to put up apio24p2hard and apio24p3hard on DMOJ at the moment...

My solution is O(n^{1.75}) and it passed this problem.

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

the number of vertices being used, I think.

I think problem C was better as "minimizing n" problem(i.e. your solution is judged by the max n it uses)

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.