When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

BERNARD's blog

By BERNARD, 10 months ago, In English

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.

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best to everyone, you will achieve the impossible. We trust you

»
10 months ago, # |
  Vote: I like it +50 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it -84 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +22 Vote: I do not like it

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

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

    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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    The Australian team is reporting 35-40 minute judging queues

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

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

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

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When will be cutoffs decided?

»
10 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Will you put the problems to an online judge?

»
10 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

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

Anyone knows where the scoreboard can be accessed?

»
10 months ago, # |
  Vote: I like it -16 Vote: I do not like it

How to solve B?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it -43 Vote: I do not like it

    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.

  • »
    »
    10 months ago, # ^ |
    Rev. 6   Vote: I like it +86 Vote: I do not like it

    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

    for (int i = 0; i + mid <= adj[x].size(); ++i)
        //check if there're l <= adj[x][i] and r >= adj[x][i + mid - 1] satisfying the conditions.
    

    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.

    Code
    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it +20 Vote: I do not like it

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

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

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

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

          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!

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

      How can you binary search the answer?

      Doesn't it fail on test case like:

      14
      8 8 8 8 8 5 5 5 4 4 4 3 8 8
      

      Possible answers are:

      1 2 3 4 5 7
      

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

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 6   Vote: I like it +15 Vote: I do not like it

        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

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

        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.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +18 Vote: I do not like 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.

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

    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.

»
10 months ago, # |
  Vote: I like it -216 Vote: I do not like it

Scoreboard just got released!

https://apio2023.cn/cms/ranking_unofficial

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve last subtask of C?

»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Anyone know when cutoffs will be decided?

»
10 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

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

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

»
10 months ago, # |
  Vote: I like it +86 Vote: I do not like it

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.

Egypt
»
10 months ago, # |
  Vote: I like it +57 Vote: I do not like it

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)

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

    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

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

      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)

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

        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

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 2   Vote: I like it -13 Vote: I do not like it

        //

»
10 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

»
10 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Where can we find tasks?

»
10 months ago, # |
  Vote: I like it +28 Vote: I do not like it

The rank got released: APIO 2023 rank

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

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

    nobody got points on notice? disappointed...

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

    anyone know the cutoffs?

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

      Judging from the result the gold cutoff is 263 or 266. I don't know if that makes sense, tho

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

        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.

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

          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

»
10 months ago, # |
Rev. 8   Vote: I like it +88 Vote: I do not like it

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.

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

    😭😭😭

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

    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:

    • Gold: 236
    • Silver: 191
    • Bronze: 145 (Since there will be exactly 106 participants greater or equal to 144 points, and thus the cutoff is 145)
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

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

      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.

»
10 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Where are the official cutoffs going to be posted?

»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Problems are now available on oj.uz

»
10 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

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

      They changed the cut off. Silver is 194

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

    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.

  • »
    »
    10 months ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    Btw they changed it to 194

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