Блог пользователя BERNARD

Автор BERNARD, 2 года назад, По-английски

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.

  • Проголосовать: нравится
  • +119
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So excited for the contest!

Good luck everyone :)

»
2 года назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

Does anyine know whether there ll be a mirror ?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

Going to be interesting
Good luck ^_^

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

Good luck to all players

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Bronze medal : hom much score?

»
2 года назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

B (not implemented)

Spoiler
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

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

    Spoiler
    Implementation
    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

      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 года назад, # |
Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

A (100 points)

idea
code (the implementation is slightly different from my explanation above, but overall idea is same)
»
2 года назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

C:

10
91.36
91.36 (Implementation)

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

  • »
    »
    2 года назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    NVM, my dumb solution attempt clearly fails

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

      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 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +56 Проголосовать: не нравится
    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 года назад, # ^ |
      Проголосовать: нравится +69 Проголосовать: не нравится
    Meme 100 points
    Code (Big Meme)
»
2 года назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится
how to get 94.96 on C
haha
»
2 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Where can i submit apio 2022 questions

»
2 года назад, # |
  Проголосовать: нравится -65 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will we be able to upsolve the problems ?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

When will the final results be released?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

where can i find the problems?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?