BERNARD's blog

By BERNARD, 2 years ago, In English

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.

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

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So excited for the contest!

Good luck everyone :)

»
2 years ago, # |
  Vote: I like it -45 Vote: I do not like it

Does anyine know whether there ll be a mirror ?

»
2 years ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

Going to be interesting
Good luck ^_^

»
2 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

Good luck to all players

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

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

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)

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

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

      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.

      Sample for n=3
      My code in the contest

      The count of max string length is $$$n^2$$$, so it can pass tests with $$$n\le 10$$$.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can't open official ranking website,anyone saved that?

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

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?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bronze medal : hom much score?

»
2 years ago, # |
  Vote: I like it +64 Vote: I do not like it

B (not implemented)

Spoiler
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Here's a different point of view which gives an equivalent solution, but may be simpler to implement.

    Spoiler
    Implementation
    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +20 Vote: I do not like it

      For the sqrt solution, can you elaborate on how you would update the vertices that have the same bucket value for L and R?

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

A (100 points)

idea
code (the implementation is slightly different from my explanation above, but overall idea is same)
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For what do you use arrays imp, arr, brr?

»
2 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

C:

10
91.36
91.36 (Implementation)

How to improve this to 100? Or is it a different approach for 100?

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

    NVM, my dumb solution attempt clearly fails

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

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

  • »
    »
    2 years ago, # ^ |
    Rev. 5   Vote: I like it +56 Vote: I do not like it
    100 pts
    Code (implemented differently, but follows the solution above)

    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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +69 Vote: I do not like it
    Meme 100 points
    Code (Big Meme)
    • »
      »
      »
      2 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I may find a hack ....

      Spoiler
»
2 years ago, # |
  Vote: I like it -21 Vote: I do not like it
how to get 94.96 on C
haha
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can i submit apio 2022 questions

»
2 years ago, # |
  Vote: I like it -65 Vote: I do not like it

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?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will we be able to upsolve the problems ?

»
2 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

When will the final results be released?

»
2 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

My simple solution for problem C (99.64 points):

Solution
Minor improvements to get a 100
My score

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.

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

where can i find the problems?

»
2 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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?

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

    they fixed it yesterday, but yeah it was swapped.

»
2 years ago, # |
  Vote: I like it +23 Vote: I do not like it

The test cases have been published on the APIO 2022 website.

You can upsolve the problems at https://tlx.toki.id/problems/apio-2022

»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

You can solve all problems here; https://oj.uz/problems/source/600

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?