Noam527's blog

APIO 2019 Discussion?
By Noam527, history, 5 years ago, In English

Is it allowed now to discuss the APIO? According to the schedule, the official competition is done by now... but also according to the schedule, the open contest is in about a week.

Edit: It seems like discussions should be kept until after the open contest ends. So, don't scroll down if you want to avoid any kind of spoiler to the open contest (and yes, let's stop discussing until then).

Edit2: Should be good now.

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

Comments Comments (71)
| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I was told that "we should not discuss openly about results and problems of APIO 2019, until 9:00 AM (UTC+9) of May 20th." from a responsible of APIO 2019 Tokyo venue.

So I think we can discuss (at least about results), but not confident.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Seoul site result is almost a meme. Best score is 253(GyojunYoun), and 4th ~13th are all tied to score 203. I expect 0G/13S/0B.

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

    Seems like 203 is pretty common result. Here we had two people with 203, and I've also heard of another 8 people with 203.

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

      Yeah, it's common, very very common. :)

      Congratulation for the perfect score, by the way!

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

        How did you know?

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

          I can see unofficial results :)

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

            So... you know the unofficial results, and you said that both 253-point scorer and 203-point scorer in Seoul is expected to get silver medal. So, it means, I got two informations, right?

            • $$$G_{border} \geq 254$$$
            • $$$203 \leq S_{border} \leq 253$$$
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Maybe it's even wrong, because it's unofficial anyway, and I didn't check it rigorously. I hope Korea can get gold.

              → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      what is the distribution of 203 points btw?

      → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Result of Vietnam: user202729_ scored 243, minhtung04042001 scored 233, and 5 others got 203.

I guest all people with 203 will get silver medals. (Actually no medal, but certificates saying that they are silver medalists).

→ Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it +11 Vote: I do not like it

Okay, so here is the known result of Japan:

Results in Japan

My first guess of medal borderline was 243/203/something, but since there could many participants than usual because of ties, it is possible that even I may get gold medal :)

P.S. I solved two problems (A and C) in 66 minutes :)

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it
Spoiler
→ Reply
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

This thread will spoil the contest for participants of APIO Open, it's better not to discuss, or to hide solutions and warn not to read the future participants.

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

    Sure, thanks for the information.

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

      Could you, please, update your post with it to make sure everyone sees the answer and avoids discussions.

      → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Top 3 in Kazakhstan:
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Noam527 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Problems were pretty standard, almost trivial ideawise. Quite sad cause APIO had high problem quality. (I wanted to do call for tasks, but was too busy :( )

Can anyone solve B in $$$O(m^{1+\epsilon})$$$ time for $$$\epsilon > 0$$$, possibly using very complicated data structures?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    As far as I know, zero problems was received from call for tasks :)

    I'm not problem setter, so this information may be outdated, totally wrong, or something else.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The ideas were not difficult to figure, and I also think the solutions relied heavily on constant factor... overall, didn't really like the problems.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I also think problems are pretty standard and boring. Maybe somehow they only received some data structure problems.

    some narcissism
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Wow, I admire your skill in constant time optimizations!

      Actually, I've solved problem A and C in 66 minutes total. And I spent only another 9 minutes to get solution of problem B. And rested 25 minutes. Then, for another 100 minutes, I considered about existence of solution of which faster than $$$O(n^{1.5} \times \alpha(n))$$$ because I thought it is risky to implement, but my thinking failed. After that, I implemented + debugged my code and it took 40 minutes. I used remaining 60 minutes completely on constant optimization of it.

      However, I only got 27 points on problem B. I'm really bad at constant optimization...

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

        Is there anyone who spent 1hr for squeezing segment-tree based approach on A? Funny that I did, and succeeded XD

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

          Why did you need a segment tree on A? I think the common solution is finding period and sweepline.

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

            I plotted (x mod T, y) in a plane and calculated the area of union of rectangles. After contest I found out I was stupid, as usual.

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

          I tried, but after several hours I only got to 30 points :/

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

        I've met the same problem: solving A and C, spending loads of time on the O(n sqrt(n) alpha(n)) algorithm of B and getting only 27 points eventually.

        By the way, will the contestants' source codes be made public?

        → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Some whining about results
Asking for help to find a problem in the solution
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think std::set is a bad idea.. I know it's linear time, but still. I implemented everything on array, maintaining it sorted by merging original edge set with an updated edge set ($$$O(B\log B + M)$$$). I didn't saw anyone who skipped this optimization and pass.

    Also for me, optimal bucket size was 800.

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

    I think you can change your 'microdsu' to a dfs.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      dfs and bfs are not working good because of the vectors that i need to use to create graph

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it -8 Vote: I do not like it

        You can use linked list to store edges. That worked fine for me.

        Also, you can just open a array of n*sqrt(n) and use it as 'vector's to store edges.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Thank you, now it works faster, but i can't get 100 :( (check reply to the koo_saga comment)

          → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can i see standings?

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I'm too old to take part in APIO now but I'm really curious as to what's the solution for B... no one I know managed to solve it. Can someone who has solved it give me a rough outline of the solution? Thanks :)

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

    It is a standard square root decomposition problem.

    Brief Outline: Divide the queries into $$$\sqrt{Q}$$$ buckets. For each bucket, note that at most $$$\sqrt{Q}$$$ edges have weights unchanged within the bucket. Sort all the queries by decreasing weight in the bucket, and maintain a DSU while adding edges that are not modified within the bucket one by one. For edges with weight modified in the bucket, we iterate through all of them and then add them to the DSU if they are usable, then remove them after we are done with a query (so $$$\sqrt{Q}$$$ additions and removals per query). This can be implemented with DSU with rollbacks.

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

      "DSU with rollbacks" — How is this implemented, with still $$$O(\alpha(n))$$$? (Providing some vague idea is fine)

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

        Use dfs instead of dsu here.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Create a stack to record what you merged, then for every "undo" operation you can just look at the top of the stack and undo the changes (by reassigning values in the dsu array) and then pop from the stack. It's at most $$$O(\log n)$$$ since you still merge small to large (but don't do path compression).

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

          I understand — I guess this would not fit in the time constraint for this specific problem though.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            My solution using this method passed, though with some slight optimizations (I kept getting 71 at the beginning).

            → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You don't need to use "dsu with rollback". In each block, you can add edges that covers the whole block from big to small using dsu. And to answer each query, just simply connect the extra edges on this query and run dfs. (When connect these edges you can just regard a connected component as a single vertex with weight.)

        Using "dsu with rollback" will bring a log.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          The same as TLE.

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

          Ya I didn't realize this before TLE pointed it out, since that was the first thing that came to mind. Thanks.

          → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

when will they be available for practice?

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

How many points have gold medals?

→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

https://apio2019.ru/results/official-contest/ shows 104 medalists with 201 official contestants. Either I am not good at math or the APIO 2019 committee has clearly violated the regulations they provided themselves.

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

    I believe this is the solution for cut-off the team leaders selected:

    Get temporary standings according to top 6 people for each country, get medal cutoffs, include all participants that are tied, and give medals according to cutoffs calculated before, standings will contain more than 6 people for some countries

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! any news for testdatas? niyaznigmatul PavelKunyavskiy

→ Reply
»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

In Gym: 2019 Asia-Pacific Informatics Olympiad (APIO 19)

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

    My code works on oj.uz here, but not on CF 146879237. Which of these is to be believed (i.e. which is closer to APIO runtime)?

    → Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In problem B, both setter's and checker's solution got TLE on oj.uz (I downloaded them here)

    setter: weight_restriction_nb.cpp
    checher:sol_hanh.cpp

    Also, their description files are quite funny.

    File name: weight_restriction_nb.cpp
Tag: TIME_LIMIT_EXCEEDED_OR_ACCEPTED
Author: BudAlNik
Change time: Sat May 18 02:22:51 MSK 2019

    File name: sol_hanh.cpp
Tag: TIME_LIMIT_EXCEEDED_OR_ACCEPTED
Author: BudAlNik
Change time: Sat May 18 02:16:26 MSK 2019
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A In this solution it says that

Let f(x) = {(x + x / b) % a, x % b}

It's possible to prove that f(x) is periodic with smallest period = ab / gcd(a, b + 1)

How do I prove this?

please note that I have no experience in finding periods of periodic functions. If you can direct me to some resources that'll be great too.

thanks

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

    can someone help us, please ?

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

      Regarding what?

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

        For problem A In this solution it says that

        Let f(x) = {(x + x / b) % a, x % b}

        It's possible to prove that f(x) is periodic with smallest period = ab / gcd(a, b + 1)

        How do I prove this?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

          I'll try to answer your question, if you haven't answered it by now.

          Suppose we are examining times $$$t_0$$$ and $$$t_1$$$. We know that our tuples are:

          $$$\left( \left( t_0 + \Bigl\lfloor \frac{t_0}{B} \Bigr\rfloor \right) \pmod{A}, t_0 \pmod{B} \right)$$$

          $$$\left( \left( t_1 + \Bigl\lfloor \frac{t_1}{B} \Bigr\rfloor \right) \pmod{A}, t_1 \pmod{B} \right)$$$

          We want to know when the two tuples are equal to each other. We know that $$$t_0 \equiv t_1 \pmod{B} \Longrightarrow t_0 = t_1 + KB$$$ for some $$$K \in \mathbb{Z}$$$. So now we want to know when

          $$$\left( t_0 + \Bigl\lfloor \frac{t_0}{B} \Bigr\rfloor \right) \equiv \left( t_1 + \Bigl\lfloor \frac{t_1}{B} \Bigr\rfloor \right) \pmod{A}.$$$

          Replacing $$$t_0 = t_1 + KB$$$, we have that:

          $$$\left( t_1 + KB + \Bigl\lfloor \frac{t_1 + KB}{B} \Bigr\rfloor \right) \equiv \left( t_1 + \Bigl\lfloor \frac{t_1}{B} \Bigr\rfloor \right) \pmod{A}.$$$

          A nice property of the floor function is that $$$\lfloor A/B \rfloor = \lfloor (A + KB)/B \rfloor$$$ for $$$K \in \mathbb{Z}$$$. Using this, we see that:

          $$$\left( t_1 + KB + K+ \Bigl\lfloor \frac{t_1}{B} \Bigr\rfloor \right) \equiv \left( t_1 + \Bigl\lfloor \frac{t_1}{B} \Bigr\rfloor \right) \pmod{A}.$$$

          Using some grade school level arithmetic, we have that:

          $$$KB + K \equiv 0\pmod{A}.$$$

          From here we see that $$$K$$$ has period $$$\frac{A}{\text{gcd} (A, B + 1)}$$$. So $$$KB$$$ has period $$$\frac{A \cdot B}{\text{gcd} (A, B + 1)}$$$.

          → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

→ Reply