BERNARB.01's blog

By BERNARB.01, 6 weeks 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

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

So excited for the contest!

Good luck everyone :)

»
6 weeks ago, # |
  Vote: I like it -45 Vote: I do not like it

Does anyine know whether there ll be a mirror ?

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

Going to be interesting
Good luck ^_^

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

Good luck to all players

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

proud to compete in the name of Botswana i will bring great pride to my nation!

»
5 weeks 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!

»
5 weeks 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)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    doesn’t really matter but
»
5 weeks 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.​

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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$$$.

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

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

»
5 weeks 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?

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

Bronze medal : hom much score?

»
5 weeks ago, # |
  Vote: I like it +64 Vote: I do not like it

B (not implemented)

Spoiler
  • »
    »
    5 weeks 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
    • »
      »
      »
      3 weeks 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?

»
5 weeks 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)
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks 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?

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

    NVM, my dumb solution attempt clearly fails

    • »
      »
      »
      5 weeks 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$$$.

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

        Yeah, I get it now, thanks for explaining!

        And to think I wasted the last 30 minutes of the contest trying to make Pollard rho and Miller Rabin work... :/

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +69 Vote: I do not like it
    Meme 100 points
    Code (Big Meme)
»
5 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it
how to get 94.96 on C
haha
»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can i submit apio 2022 questions

»
5 weeks 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?

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

Will we be able to upsolve the problems ?

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

When will the final results be released?

»
5 weeks 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.

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

where can i find the problems?

»
5 weeks 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?

»
5 weeks 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

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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