NeroZein's blog

By NeroZein, history, 8 days ago, In English

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!

  • Vote: I like it
  • +126
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it +52 Vote: I do not like it

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 ?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

          Hopefully the queue isn't that bad.

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I hope you know that you can change it.

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

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

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is it faster?

      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
8 days ago, # |
  Vote: I like it +16 Vote: I do not like it

GLHF

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

good luck for all participants

»
8 days ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Ann will win APIO 2024!

»
7 days ago, # |
  Vote: I like it +18 Vote: I do not like it

evenvalue will win APIO 2024!

»
7 days ago, # |
  Vote: I like it +4 Vote: I do not like it

NeroZein will win APIO 2024!

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Everyone who gives APIO 2024 is a winner!

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

FerjaniSassi will win APIO 2024!

»
6 days ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is because of different timezones.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 days ago, # ^ |
        Rev. 2   Vote: I like it +25 Vote: I do not like it

        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.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

»
6 days ago, # |
  Vote: I like it +85 Vote: I do not like it

owoovo_shih will win APIO 2024!

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve practice session A problem?

  • »
    »
    5 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think we should wait until the contest is over before discussing problems publicly.

  • »
    »
    4 days ago, # ^ |
    Rev. 4   Vote: I like it +14 Vote: I do not like it

    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.

    Implementation
  • »
    »
    4 days ago, # ^ |
    Rev. 3   Vote: I like it +32 Vote: I do not like it

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

    init
    calc_f

    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.

»
5 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +25 submission limit

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

»
4 days ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Practice is over. Is there any standings?

»
3 days ago, # |
  Vote: I like it +16 Vote: I do not like it

Is there going to be a mirror?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sadly no :(

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

»
2 days ago, # |
  Vote: I like it +8 Vote: I do not like it

When will every country participated and I can discuss problems?

»
2 days ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
43 hours ago, # |
  Vote: I like it +16 Vote: I do not like it

When will ranking come out

»
37 hours ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

Asia-Pacific Informatics Olympiad

Asia-Pacific Graphs Olympiad

Anyway, I think problems were cool

  • »
    »
    35 hours ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    But this year the problems were easy, especially problem A

»
34 hours ago, # |
  Vote: I like it +51 Vote: I do not like it

[Unofficial rankings]

Please add your scores in this spreadsheet

»
25 hours ago, # |
  Vote: I like it +25 Vote: I do not like it

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

»
24 hours ago, # |
  Vote: I like it +121 Vote: I do not like it

China

56 300s.

  • »
    »
    23 hours ago, # ^ |
      Vote: I like it +72 Vote: I do not like it

    This is in meme territory.

  • »
    »
    20 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    💀

  • »
    »
    20 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    China's that one country where the first rank page is just filled with red users who are prob younger than 16....

  • »
    »
    10 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

»
16 hours ago, # |
  Vote: I like it +29 Vote: I do not like it

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 !!!

»
12 hours ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

  • »
    »
    12 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 hours ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    12 hours ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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

    • »
      »
      »
      9 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        8 hours ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I had a solution for p2 subtask 3 but I failed

  • »
    »
    12 hours ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    • »
      »
      »
      10 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

    • »
      »
      »
      10 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 hours ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
86 minutes ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    55 minutes ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.