This year's Asia-Pacific Informatics Olympiad (APIO) is approaching, it will be open on 28 May for official participants for a 48-hours window, and the mirror will be open for everyone on May 30 for 24 hours.
It is an IOI-Style contest with 3 problems and 5 hours. You can find more information on the official APIO 2022 site apio2022.org.
Let's discuss problems/cutoffs/results here in the comments after the contest (and the mirror) ends.
I wish everyone participating good luck!
UPD: You can find more information about the mirror here.
UPD2: Both the contest and the mirror are now over.
UPD3: The final ranking has been announced, you can find it here.
So excited for the contest!
Good luck everyone :)
Does anyine know whether there ll be a mirror ?
Probably yes because it had in previous years and it's international
Yes
Going to be interesting
Good luck ^_^
Good luck to all players
Contest is now over if I'm not mistaken. Anyone solved C? I would really like to see the full solution, I only got 91 points but I think the idea is beautiful!
First, we need to wait after the contest ends. I will contact my friend generic_placeholder_name to explain it for you Second, we all got 91 points on that problem :)) (except for 1 guy who got 93 and 2 guys who got 100)
Orz
Ops yeah my bad I just checked the official page it says to wait a few days... Ty tho! I would really appreciate it. And also woah I didn't know that few ppl got 100! is there a scoreboard btw?
I think the scoreboard will be here after the mirror. (The next part was deleted)
I know another person who participated unofficially and got 94.xx
I think we shouldn't discuss the contest until the mirror is also over (https://www.timeanddate.com/worldclock/fixedtime.html?iso=20220531T00)
I don't know if it's time to announce it yet, but according to the preliminary results, the cutoffs are
If you want to see the cutoffs you can check the previous version. I don't know if it's okay, so I updated my comment. (sorry for the inconvenience)
152.97*
Now the open contest is over. Maybe time to discuss problems?
Official ranking is shown here.
I got 36+30+91.36=157.36pts on the Chinese unofficial group.
Ops I can't access the link :(, maybe it is my end — ty for sharing tho. Could you share your approach for problem A? I didn't understand the statement during competition lol.
I got 0 + 30 + 91.36=121.36 points on the Mexican unofficial group.
Oops it's unavailable now, maybe try again later.
For problem A: (36pts solution)
Look at the sample below. The top left block stores the info of blocks that have the same color with it.
The count of max string length is $$$n^2$$$, so it can pass tests with $$$n\le 10$$$.
I can't open official ranking website,anyone saved that?
The contest server seems to have been taken offline, but there is a preliminary rankings file with medals: https://docs.google.com/spreadsheets/d/1PR6qtlsXOu39HY1PUdPuUpVDa3G9eLnfwxeOvass4tU/edit?usp=sharing
UwU
I'm really curious what the solution for problem B is, I thought about memorizing the last node < k visited in the dfs for every node, and updating this value after each query which could potentially lower the complexity of the brute force but the worst case is still quadratic, idk. Anyone got hints for the full solution?
Bronze medal : hom much score?
301
B (not implemented)
I assume that you can solve 60 points in $$$O(k(m + n))$$$.
Build a segment tree (basically, memoized D&C) over range $$$[1, k]$$$. Take the middle point $$$m = (k + 1) / 2$$$. There is a set of reachable nodes from $$$m$$$, and the nodes that can reach $$$m$$$. Let them be $$$L, R$$$ respectively.
If $$$L \cap R \neq \emptyset$$$, it means there is a cycle, so terminate.
Otherwise, you recurse down. For the left subproblem, you can only consider vertex set $$$L$$$, and for the right subproblem, you can only consider vertex set $$$R$$$: This means, for each vertices, as long as they are not in any cycle, they belong to at most $$$\log k$$$ subproblems.
When adding an edge, you can determine the set of vertices that are either appended to $$$L$$$ or $$$R$$$. If you have to add to both, then you have a cycle. Depending on the position you added, you can determine which direction to recurse down. You may have to add a large set of vertices at once, but the amortized bound still holds.
I think it is related to this thing.
Here's a different point of view which gives an equivalent solution, but may be simpler to implement.
Recall that the $$$O(k(m+n))$$$ solution stores, for each node, the earliest special node you can reach from it, and the latest special node you can reach it from; we'll report a cycle when these values cross. These values get updated only $$$O(k)$$$ times per node/edge, so the total runtime is $$$O(k(m+n))$$$.
We'll start by showing a $$$O(\sqrt{k}(m+n))$$$ solution. Instead of storing these reachable special nodes at full precision, let's break the special nodes into $$$O(b)$$$ buckets of size $$$O(k/b)$$$, and store for each node, the earliest/latest bucket which it can reach/can reach it. Updating this information takes only $$$O(b(m+n))$$$ time, since there are only $$$O(b)$$$ bucket changes per node.
However, this information is not sufficient to check if a node is part of a cycle, since we only know if the earliest/latest special nodes are in the same bucket. To fix this, we'll compute the exact earliest/latest special nodes once we notice that the earliest/latest buckets coincide (we'll say this node falls into this bucket). This computation is efficient because, once this node falls into a bucket, all successor vertices on the path from this node to the bucket also fall into the bucket (since we provide a path from the bucket), and likewise for predecessors. Thus, each node will be updated with exact special nodes only $$$O(k/b)$$$ times. By setting $$$b = \sqrt{k}$$$, we can get an $$$O(\sqrt{k} (n+m))$$$ solution.
However, we can take this one step further. Instead of using just 2 levels of precision, we can use $$$\log(n)$$$ levels, each with $$$2$$$ buckets (this is similar to the segment tree in the above solution). The ideas are quite similar, and the implementation ends up quite simple: each node stores which level/bucket it's currently part of, and when we push a node a level deeper, we just check the predecessor/successor nodes and push them deeper too if necessary.
For the sqrt solution, can you elaborate on how you would update the vertices that have the same bucket value for L and R?
A (100 points)
When the grid has size $$$5 \times 5$$$, we can store the entire grid directly. Let $$$h = \lfloor \frac{n}{2} \rfloor$$$.
We store these rows $$$[0,h),[h, n), [n,n+h),[n+h,2n),[2n,2n]$$$. We can see that $$$h \leq 10$$$ when $$$n \leq 20$$$, so are able to directly store the entire grid in this fashion.
Now, we want to transfer the $$$5 \times 5$$$ grid into $$$3 \times 3$$$ grid (Actually I only used $$$4$$$ tiles of the $$$9$$$ tiles).
We want to store each $$$(n+1) \times (n+1)$$$ square in a compact way such that we are able to get all the information we need. Let us focus on the top-left region (the one with the red square).
We only care about the cells in this yellow band and the connectivity between them. There might be islands that are already formed that do no touch the yellow band. We will count them separately.
Now, when $$$n=20$$$, we need to use $$$41$$$ bits to store the entire state of the yellow band. and there can be up to $$$100$$$ islands in the white region that is not connected to the yellow band. So we have already used about $$$48$$$ bits.
Now, we need to store the connectivity of those lands in the yellow band using the other bits. We can actually do this in $$$42$$$ bits only. Firstly, let us focus on the yellow band only. There are at most $$$21$$$ connected components. If $$$2$$$ lands are adjacent in the yellow region, they belong to the same connected component.
The worst case where the number for connected components for $$$n=3$$$ is shown here.
Now, here is the crucial observation. Let us label the connected components in some order of walking along the line.
Suppose $$$a<b<c<d$$$. If $$$(a,c)$$$ is connected and $$$(b,d)$$$ is connected. Then the entire $$$(a,b,c,d)$$$ must necessarily be all connected.
There is no way you can not make the red and blue lines intersect because $$$b$$$ is inside the red shape, while $$$d$$$ is outside it.
This means that we can view this as a bracket sequence. That is, if $$$(a,c)$$$ are connected and there is no $$$a < b <c$$$ such that $$$(a,b)$$$ is connected, then we add an edge between $$$a$$$ and $$$c$$$. This can be viewed as adding a $$$\texttt{(}$$$ to $$$a$$$ and $$$\texttt{)}$$$ to $$$c$$$.
So if the connectivity looks like this, we will store $$$\texttt{(}_a \texttt{)}_c \texttt{(}_c \texttt{(}_d \texttt{)}_e \texttt{)}_f$$$. Notice that for each index, there is at most a single copy of $$$\texttt{(}$$$ or $$$\texttt{)}$$$. Since we have shown that there are at most $$$21$$$ connected components on the yellow band, we only have to use $$$42$$$ additional bits to store the connectivity. Therefore, we can store the important things we need from a corner of the grid in $$$41+21+21+7=90$$$ bits.
For what do you use arrays imp, arr, brr?
C:
Since $$$k \le 90$$$, a simple construction is $$$k - 2, k - 3, \dots, 1, 0$$$.
Observation 1: A permutation $$$0, 1, \dots, n - 1$$$, has $$$2^n$$$ increasing subsequences.
After making this observation, it is reasonable now to think about $$$k$$$ in terms of powers of $$$2$$$.
We now know how to obtain $$$k$$$ increasing subsequences in our permutation if $$$k$$$ is a power of $$$2$$$, so let's start with the permutation $$$0, 1, \dots, \lfloor log_2k \rfloor$$$, and see how the number of increasing subsequences changes when adding new elements.
Assume for now that the length of our current permutation is $$$n$$$.
Observation 2: Inserting $$$n$$$ at index $$$i$$$ adds $$$2^i$$$ new increasing subsequences to our current permutation.
Now it is easy to find a construction after making the second observation. You can see the implementation below for more details.
How to improve this to 100? Or is it a different approach for 100?
NVM, my dumb solution attempt clearly fails
It seems like you're missing an obvious flaw in your solution. That's OK, things like this can happen to less experienced contestants.
If $$$k$$$ is a prime, your permutation will have the same length as $$$k$$$.
For example, let $$$k=1000000007$$$. Since $$$1000000007$$$ is a prime, its factorization is just $$$(1000000007)$$$. Thus your solution will generate the permutation $$$[1000000006,1000000005,...,1,0]$$$, with length $$$1000000007$$$.
For the sake of simplicity, I will loosely define a permutation as any sequence of pairwise distinct numbers. We can always transform any permutation defined this way into a valid permutation, by replacing each element with the number of elements smaller than it.
The bound of $$$n=90$$$ suggests that we need to encode each bit of $$$k$$$ in $$$1.5$$$ elements on average, or $$$2$$$ bits in $$$3$$$ elements. So naturally we write $$$k$$$ in base $$$4$$$ instead (since $$$4=2^2$$$), and we will represent each digit using at most $$$3$$$ elements.
To acheive this, suppose we have a permutation $$$P$$$ consisting of elements $$$0,1,...,n-1$$$ that has $$$x$$$ increasing subsequences. If we can construct permutations with $$$4x$$$, $$$4x+1$$$, $$$4x+2$$$ and $$$4x+3$$$ increasing subsequences from $$$P$$$ using at most $$$3$$$ additonal elements, we will have acheived our goal. To assist us in doing so, we will use the following observations:
Observation 1: Adding $$$n$$$ (in other words, an element larger than any element in $$$P$$$) to the right of $$$P$$$ creates a permutation with $$$2x$$$ increasing subsequences, since there is a one-to-one mapping (bijection) between additional subsequences containing $$$n$$$ and already-existing subsequences in $$$P$$$.
Observation 2: Adding $$$-1$$$ (in other words, an element smaller than any element in $$$P$$$) to the right of $$$P$$$ creates a permutation with $$$x+1$$$ increasing subsequences, since the only additional subsequence created this way is $$$[-1]$$$.
With these observations, the cases $$$4x$$$, $$$4x+1$$$ and $$$4x+2$$$ are solved by adding $$$[n,n+1]$$$, $$$[n,n+1,-1]$$$ and $$$[n,-1,n+1]$$$ to the right of $$$P$$$ respectively. For the case $$$4x+3$$$, we use the following observation:
Observation 3: If the element $$$1$$$ is positioned to the left of $$$0$$$ in $$$P$$$, adding $$$1.5$$$ to the right of $$$P$$$ creates a permutation with $$$x+3$$$ increasing subsequences. The additional subsequences created this way are $$$[1.5]$$$, $$$[1,1.5]$$$ and $$$[0,1.5]$$$.
Thus, if $$$P$$$ contains $$$1$$$ and $$$0$$$ in this order, we can solve $$$4x+3$$$ by adding $$$[n,n+1,1.5]$$$ to the back of $$$P$$$. Otherwise, we add $$$[n,-1,n+1,-2]$$$ to $$$P$$$. This we will call the fallback method (and yes, I know it uses $$$4$$$ elements, I will get back to it later).
Thus, our solution is as follows: The first digit of $$$x$$$ is constructed using the base cases $$$x=1$$$, $$$x=2$$$ and $$$x=3$$$, which we will cover with the permutations $$$P=[]$$$, $$$P=[0]$$$ and $$$P=[1,0]$$$. Then, we use one of the four cases ($$$4x$$$, $$$4x+1$$$, $$$4x+2$$$, $$$4x+3$$$) to push one of the four digits $$$0,1,2,3$$$ to the back of $$$x$$$'s base-$$$4$$$ representation. Thus we can make $$$x$$$'s base-$$$4$$$ representation the same as $$$k$$$'s representation, meaning $$$x=k$$$ and the problem is solved.
At this point, one question remains: What about the fallback method? If we use the fallback method every iteration, we will end up using 4 elements per digit on average. Fortunately, we can prove that we use the fallback method at most once: the first time we use it, it establishes that $$$1$$$ (the second smallest element) is to the left of $$$0$$$ (the smallest element) in $$$P$$$, and all the other operations we use during the process maintains this fact, thus we never need to use the fallback method again.
This, combined with the fact that the first digit is always constructed using $$$\le 2$$$ elements, leaving us with $$$1$$$ to spare, means that we end up using at most $$$3$$$ elements per digit on average. Since $$$log_4(1e18) \le 30$$$, the solution uses at most $$$3*30=90$$$ elements, scoring the full $$$100$$$ points.
I hope I didn't make any mistakes describing the solution, but if there are any, you're always welcome to point it out so I can fix it promptly.
Lots of thanks to errorgorn for sharing me this solution and providing the code. I didn't have a solution that provably worked and instead came up with some other heuristics that I didn't implement in time, causing me to lose gold by <2 points. Feel free to thank him and call me noob in the replies below.
what a noob
It's nice to see a top gold here!
I'm very glad to see two top golds here!!!
This is how I got 100 points in contest:
I thought of the problem in terms of reducing $$$k$$$ as fast as possible. Dividing by $$$2$$$ is always optimal when $$$k$$$ is even; otherwise, in the 91 points solution, we subtract $$$1$$$ then divide by $$$2$$$. This is suboptimal; we can instead divide by 3, 5, etc. if possible.
Trying this with some small primes gives 100.
I may find a hack ....
For a sequence $$$X$$$ let $$$f(X)$$$ denote the number of increasing subsequences that it has. We must construct a sequence small enough $$$X$$$ with distinct elements (these can be converted into a permutation at the end) such that $$$f(X) = k$$$ where $$$k$$$ is the given value. Let's make some observations:
One of the $$$91.36$$$ solutions is to use steps $$$1, 3$$$ to reduce the number (the binary solution). Anyone who has gotten the $$$91.36$$$ solution like this will know that the issue were odd numbers, they required $$$2$$$ steps to reduce. This is precisely what we fix.
Say we have to find $$$list(k)$$$ for some $$$k$$$. If $$$k = 2$$$ we return $$$(0)$$$. If $$$k = 3$$$ we return $$$(1, 0)$$$. If $$$k$$$ is even, we find $$$list(k)$$$ recursively from $$$list(k/2)$$$ by using observation $$$3$$$. If $$$k$$$ is divisibly by $$$3$$$ we find $$$list(k)$$$ recursively from $$$list(k/3)$$$ by using observation $$$4$$$. Otherwise we find $$$list(k)$$$ recursively from $$$list(k-k \bmod 3)$$$ by using observation 1 or observation 2 (depending on whether $$$k \bmod 3 = 1$$$ or $$$2$$$).
Implementing this in the straightforward way will give $$$94.96$$$ points.
i now know a crazy randomised solution that passes for $$$100$$$ points but not going to share bcuz am evil
Where can i submit apio 2022 questions
It is available to upsolve here https://tlx.toki.id/problems/apio-2022
Very nice contest! Problem C was one of the coolest problems I've seen in a long time.
When will the results/editorial be published?
in my opinion C is trash
B was the coolest to me, C was trash
A was coolest imo.
not imo, it is apio.
Will we be able to upsolve the problems ?
When will the final results be released?
My simple solution for problem C (99.64 points):
Greedily maintain the permutation and add one element to the right each time, until we have the needed number of increasing subsequences. The value added to the permutation will be the largest possible value such that we do not pass the needed number of increasing subsequences.
Note that if we add x to the right, we increase all other values in the permutation that are at least x by 1. For example, adding 3 to the permutation (5, 2, 0, 1, 3, 4) would result in: (6, 2, 0, 1, 4, 5 ,3).
This alone gives 91.36. To improve to 99.64, we simply try to extend all initial permutations of length 3 (length 2 gives about 97).
Unfortunately, my solution during the contest didn’t count the number of increasing subsequences efficiently (didn't have time to remove an O(permutation-length) factor from the complexity), so I could only fix the first 3 values to fit the time limits. Had I maintained the number of increasing subsequences efficiently, my code would have run about 100 times faster, and I would have been able to fix more initial permutations, which I’m convinced would have given a 100.
Even not improving the efficiency of the code, but stopping to check all initial permutations if the best permutation so far is already small enough, could be fast enough.
Unfortunately, I did none of these improvements during the contest, and so I got 173.64. The cutoff for silver medal was 174. Just sad.
UPD: Applied the minor improvement of stopping when reaching a length that is small enough, and increased initial permutation size to 5. Got a 100. Devastated that this costed me a medal.
where can i find the problems?
APIO final ranking released. The cutoffs are:
Bronze: 153.66
Silver: 174.00
Gold: 207.70
Congrats to all the winners!
btw does the unofficial ranking swap the scores of problem mars and perm?
they fixed it yesterday, but yeah it was swapped.
The test cases have been published on the APIO 2022 website.
You can upsolve the problems at https://tlx.toki.id/problems/apio-2022
You can solve all problems here; https://oj.uz/problems/source/600
Is there any official editorial for APIO 2022?
For the previous years I found:
APIO 2007-2011 and 2016-2019 Official Editorial
APIO 2020 Unnofficial Editorial
APIO 2021 Official Editorial
But what about 2022? Is there any official or unnoficial editorial with more detailed solutions?