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.
Good luck to NeroZein
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
Everyone who gives APIO 2024 is a winner!
Deleted
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 got silver, people take their rating way to seriously, we are here to have fun and to solve cool problems :P
luck
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.
Thanks.
I tried my best to divide the solution into reasonable parts, hopefully it'd be helpful.
First 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.
Proof is left as an exercise for the reader. 8 )
We'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.
I'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.
Now let's answer a query. : )
I 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.
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]$$$
$$$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
3 days are passed to your comment, but still no results ...
How much more we have wait ???
Asia-Pacific Informatics OlympiadAsia-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
Edit: In case the public editing version is vandalized, you can view this backup
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
Edit: Turns out china is just built different...
u r right,coz 56 is not true.
It should be 58.
UPD:OK now the standing is out and I find that is actually only 56 300.My fault.
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.
Btw, I realized this when compiling thoughts about the contest on Zhihu: the 4 teams with 300s averaged roughly one 300 per 25 million of population (slightly lower for Canada, but roughly works out via including Tianjin or half of Shanghai (which some of the contestants have ties with)...).
So my general impression is that good performances on this contest mostly boiled down to having training geared towards such 3 problems, 4 hours, 200~400 lines of code contests. Over the past few years, I get this feeling that a lot of teams simply aren't training to solve standard OI problems anymore...
💀
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?
All of the people who tie with the 6th place become official too
They don't. They just get medals if their score gets medals
This is why youre an expert
wala????
I used to avoid the comments on this platform because of people like you. But this reply sir, is priceless.
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.
Here is how I solved C.
As the comment mentions, the main idea is CRT.
$$$n$$$ (number of vertices)$$$ = 5000$$$. We can add edges from $$$i$$$ to $$$X$$$ % $$$i$$$ (in Alice function). if $$$X$$$ % $$$i == 0$$$ then add edge $$$(i, n)$$$ otherwise $$$(X$$$ % $$$i, i)$$$, for $$$i = 1..(n-1)$$$.
I think the idea came to my mind, when I was thinking on solving for ($$$X \leq 25 000 000$$$) using some divisors technique.
For each $$$v$$$ there is an edge to $$$u < v$$$ or to $$$n$$$. Now, to formally show its a tree, we can show $$$2$$$ things, that edges = $$$n - 1$$$ and there is no cycle.
We are added exactly one edge from $$$i = 1..(n-1)$$$, So we added a total of $$$n - 1$$$ edges.
There is no cycle because each time we add an edge we go backwards. The sole exception being edge to $$$n$$$, which is only forward and does not come backwards again. This shows there is no cycle.
Now, bob gets at least $$$2500$$$ congruency equations for $$$X$$$. Since, at most $$$2499$$$ edges can be removed if $$$n = 5000$$$. If there is an edge $$$(u, v), u < v$$$ and $$$v \neq 5000$$$, $$$X$$$ % $$$v = u$$$ (a congruency equation). If $$$v = 5000$$$, $$$X$$$ % $$$u = 0$$$ (also a congruency equation).
Now, we just use CRT (but I could not get the right implementation of it, So I will just tell my solution) After I failed for the implementation for $$$100$$$ points maybe caused by overflow issues. I went for small points.
Now, for $$$X \leq 5000$$$. I say that check the validity for every $$$X$$$. (checking if some $$$X$$$ is valid or not is to check by putting it in every cong-equation and seeing if it satisfies, So, for each $$$X$$$, we check it's validity in $$$O(n)$$$)
For $$$X \leq 25 000 000$$$, I thought how to make the previous one faster, And I thought that I should only check those $$$X$$$, if they satisfy one of my equation. So I got an equation $$$X$$$ % $$$v = u$$$ (for an edge $$$(u, v)$$$) where $$$v$$$ is maximum possible (note that $$$v \geq 2500$$$). Now I say in my for loop :
(It means that $$$X$$$ should keep satisfying this equation). Now note that, I am checking at most $$$\frac{25 000 000}{2500} = 10^4$$$ values of $$$X$$$ in $$$O(n)$$$ each, This passes as well.
For $$$X \leq 10^{18}$$$. I keep the same idea, I take $$$5$$$ equations having the modulo ($$$v_i$$$) as maximum (and of course they should be pairwise co-prime) and get those equations, note that I will find all of the $$$5$$$ modulos $$$\geq 1000$$$. So, their product will be $$$\geq 10^{15}$$$. This does not causes any overflow issues as well since the product = $$$v_1 * v_2 * v_3 * v_4 * v_5 \leq 5000 ^ 5 \leq 4 * 10 ^ {18}$$$. Now, using CRT I find the final equation $$$X$$$ % $$$product = u_{final}$$$.
Now, I have reduced this again to previous solution ($$$i.e \space X$$$ should satisfy this one congruency equation):
And check every X in O(n), number of X's being checked is $$$\leq 10^{18} / 10^{15}$$$ which is $$$\leq 1000$$$.
Hence, finally got $$$100$$$, and felt satisfied.
What a coincidence! I also used this method to pass this question in the competition.
In fact, you don't need to write a Chinese remainder theorem algorithm because you can directly brute force calculate the answer, which has a time complexity of $$$O(n^2)$$$ and can be solved through this problem.
How do you bruteforce it?
My English is not very good, you can read the detailed instructions here.
I see. I got the rough idea I think; thanks!
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.
u r right
I see. Thanks.
Can you explain more about the solution of B?
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.
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.
Also I think it should specified that it was a random interactor since it is more fair to have actual information about the checker
If the interactor was random, the problem would be totally different and would be too easy for APIO
In an ideal situation, this problem could have been rejected but i guess they have 0 problems lol
They have 8 extra problems. That's why we are unhappy 'bout the contest.
If the interactor was random, it would have lead to more interesting and harder solution that can lower n drastically from 5000.
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).
when will be results publish?
A very hard contest.
Kevin114514 got 115.
i think 115 is actually a high score
I agree.
I can't agree more! But I got a 110 instead.
I agree
I agree.
I agree, Concave Hull Tang.
who asked
R U retarded?
I got 240 in APIO. So my Codeforces rating is supposed to be $$$3143 \div 115 \times 240 = 6559$$$ :)
I got 0 in APIO. So my Codeforces rating is supposed to be $$$3143\div 115 \times 0 = 0$$$ :) I hope I can climb from this rating to 0 soon.
I got 0 in APIO, too. So my Codeforces rating is supposed to be $$$3143\div115\times0=0$$$ :) I hope I can climb from this rating to 0 soon.
I got 240 in APIO. So my Codeforces rating is supposed to be $$$3143÷115×240=6559$$$ :)
I got 115 in APIO, so I should be $$$3143$$$
I got 110, so I should be just under $$$3000$$$
orz Kevin
I got 300 in apio. So my Codeforces rating is supposed to be 8199.
Did he do it on purpose?
round(114.514) = 115
China score line: bronze (Cu) >= 115 silver (Ag) >= 200 gold (Au) >= 240
only got 140 :(
is it cutoffs? And what is copper?
I think he meant bronze.
sr for using google translate. "copper" should be bronze :)
Is an alloy(metals comprising two or more metals or a base metal with non-metallic additions) of copper and tin.
Haha, I know, but bronze means 青铜 in Chinese, and copper means 铜. We rarely say "青铜 medal", but generally call it "铜 medal". This is probably due to my oversight and translation differences. This is also the first time I know that "铜 medal" in English is "bronze medal" :) thanks
Are these cutoffs only based on China's scores, or all scores?
on China, i think
Read me
So Which is true
56 chinese 300 or this cutline
I am very certain that the score line is correct because I participated in the offline competition. As for the number of Chinese people with 300 points, the number 56/59 was also heard from some unofficial channels. I am not sure if this number is accurate, but it should be similar. If anyone is certain, please reply to me :)
56 chinese 300. The list is here
But most of them are unoffical and cannot win international medals. You can get the "Gold Medal in China" if you score more than 240 points.
That makes sense now.
A well known saying in China: "Instead of beating the problem, I only need to beat the author." The person who said it got accepted in C with $$$n=75$$$, and his algorithm's easy to hack.
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$$$.
I guess your solution is to connect $$$(x\bmod i,i)$$$ for all $$$1\le i < n$$$. (The nodes are 0-indexed).
With some modifications to the solution, it can be achieved for $$$n=101$$$, and the correctness is guaranteed.
Instead of connecting $$$(x\bmod i,i)$$$, we can connect $$$(x\bmod a_i,i)$$$.
Proof:
We need to prove that after deleting at most $$$49$$$ elements of $$$a$$$, the $$$\operatorname{lcm}$$$ of $$$a$$$ is still greater than $$$10^{18}$$$.
The sequence $$$a$$$ only contains powers of prime numbers. Therefore, different prime numbers can be considered independent.
For a prime $$$p$$$, let $$$p^k$$$ be the greatest power of $$$p$$$ that occurred in the sequence $$$a$$$, it is optimal for the grader to delete all $$$p^k$$$ first, then delete all $$$p^{k-1}$$$, ..., until $$$p$$$.
We can use dynamic programming to calculate the maximum possible decrease of the $$$\operatorname{lcm}$$$ caused by the grader.
Great, A very wonderful solution.
But how do you obtain the best sequence $$$a$$$?
I don't know. But the length of best sequence $$$a$$$ is at least $$$85$$$, because $$$\operatorname{lcm}(1,2,\dots,42)<10^{18}$$$.
It's hard to determine whether a sequence is valid, so I restrict the elements in $$$a$$$ to be powers of prime numbers.
Even though I added the condition, I can't find the best one that satisfies the condition.
I used DFS with pruning(may cause missing the best one) to find a good one.
Using 60 binary digits $$$x_0,x_1,\cdots, x_{59}$$$ to represent $$$X$$$. Then randomly generate 4998 XOR equations, each taking the form:
$$$\bigoplus_{j=0}^{59} a_{i, j}x_j = \text{ans}_i$$$
where $$$0 \leq a_{i, j} \leq 1$$$. The coefficients $$$a_i$$$ of the $$$i$$$-th equation are generated using a fixed random seed(Same in
Alice()
andBob()
), and $$$\text{ans}_i$$$ can be represented by connecting node $$$i$$$ to node 1 or node 2.During the communication process, some equation results may be lost. However, solving the remaining $$$n/2$$$ equations using Gaussian elimination can determine $$$x_{0}\cdots x_{59}$$$. This method can reduce $$$N$$$ to $$$\log X + \epsilon$$$.
The third problem "magic" is just a retard, but it also warns me that I'm a retard too. lol
Me refreshing the ranking page for the 100000th time
Easy idea for C
Get 2 nodes lets say 0 and 1 and connect them. Then we split X in to 64 groups for each bit. All nodes belonging to the first group will be connected to 1 if the bit at position 1 is '1'. Now we can just see if at least 1 node of group 1 is connected to node 0 then first bit is 0 otherwise first bit is 1. Then we can just reconstruct the number using its bits. We split the nodes to groups using some seed that will be constant no matter what X is.
What if the judge deletes all nodes of group 1?
I didn’t know the judge was smart but then don’t make one node for bit ‘1’ and ‘0’ but make 500 nodes for each let’s say and distribute the nodes among them
EDIT: Idea 2 to fix this issue: If a group is all deleted then just imagine its from the node which has more deleted so for the case which all '1's are deleted then all the deleted nodes u would imagine they are from '1' if it uses its deletes evenly then there is a very high probability that the whole group didn't get deleted
I think this is an easy idea compared to the other ideas I have seen
Encode X in a permutation of numbers from 3 to 22 ($$$20! > 10^8$$$). Add 1 and 2 to the beginning of the permutation. Now make $$$floor(5000/22)$$$ copies of this permutation, the k-th copy consists of numbers from $$$(k-1) \times 22 + 1$$$ to $$$k \times 22$$$, and randomly shift each of the copies. For each copy, connect the vertices corresponding to adjacent elements, and to make the graph a tree, connect the copies in any manner. Each vertex corresponds to a number from 1 to 22 in the original permutation, and two vertices are connected by an edge iff they are adjacent or the beginning and end of the original permutation. Since we know the original permutation starts with 1 followed by 2, we can easily revert the shift and find the correct direction. The chance that all the edges corresponding to a pair of adjacent elements are deleted is very small (didn't prove rigorously), so Bob can reconstruct the original permutation and guess X.
During the contest I suspected this sol was intended, so to avoid failing due to an adaptive grader I generated a random permutation of integers from 1 to 5000 using a fixed seed and replaced all the indices I used with the corresponding ones in this permutation.
where is the standing
wait for answer of this comment.
This is quite appalling. They opened an appeal session but did not give any chance to do any resubmission (as in analysis mode). Neither do they publish on their website the task statements, the test data, nor the unofficial standings.
You can't even see your own submissions and scores in the contest platform, can you? So if you have a late submission that is judged after the contest ends, you don't even know your own score?
Please wait for a while. The result will be eventually posted, including score of every contestant, statement and test data.
UPD: tasks are available on https://github.com/APIO-2024/apio2024_tasks, which is posted on May 22nd.
when
Me refreshing the ranking page for the 1000000000th time
Does anyone know why they are taking so long?
At least give a date on which results will be published so that we need not refresh the page 1000000000 times daily
Can somebody write editorial of problem A please!
There are 2 things to observe in this problem.
$$$1.$$$ If v is falling (is in our day), then we will have to include maximum index value v has in all of m records (so that according to all records v falls today).
$$$2.$$$ If v is falling, that means it's a leaf. Which means that all nodes in the subtree of v must fall first in order to make v fall.
Now, we can have two arrays, max_index[N], max_index[v] tells us the maximum index of v in all of the records, max_sub[N], max_sub[v] tells us the maximum of max_index[u], where u is in the subtree of v.
Now, we start taking values from left and keep shifting the right end to max_sub[v] (since we must include all of these values). When we can stop, such that everything inside can be deleted. We delete them (to maximize the days), days++.
Why is the APIO website just dead? There's no update so far after the contest.
We'll get GTA 6 before the unofficial ranking.
Rankings published.
We finally got rankings before GTA 6.
APMO results still aren't out though
Instead of waiting indefinitely, One suggestion would be to contact your country's delegation leader on this. He should be able to communicate directly with the APIO organizing team to know the status.
The organizers have sent the PRELIMINARY results to the team leaders. According to it:
Gold >= 240 points (40 people)
Silver >= 200 points (39 people)
Bronze >= 135 points (33 people)
Remember, these results are NOT OFFICIAL, yet. Also, we should not expect them until 31st May.
More gold medals than bronze medals ???
[Sent accidentally and cant delete]
The long wait is over, and the ranking has been released.
when the tasks will be in oj.uz
You can attempt them here in the meantime:
https://tlx.toki.id/problems/apio-2024
Thank you, but it's banned in Turkmenistan:(
vpn
https://codeforces.me/blog/entry/118757
You can solve all problems here: https://oj.uz/problems/source/652