Noam527's blog

By Noam527, history, 4 weeks 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

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

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

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

    • »
      »
      »
      4 weeks 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!

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

        How did you know?

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

          I can see unofficial results :)

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

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

      what is the distribution of 203 points btw?

»
4 weeks 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).

»
4 weeks 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 :)

»
4 weeks ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it
Spoiler
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Looks correct. I got 100 with it.

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

      Oh, Thanks !. At least my idea seems right. It's made me happy :D

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Why is q1 so mathy though :(.

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

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

    Sure, thanks for the information.

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

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it
Top 3 in Kazakhstan:
»
4 weeks 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        • »
          »
          »
          »
          »
          3 weeks 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)

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

Where can i see standings?

»
3 weeks 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 :)

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

    • »
      »
      »
      3 weeks 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)

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

        Use dfs instead of dsu here.

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

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

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

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

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

          The same as TLE.

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

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

when will they be available for practice?

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

How many points have gold medals?

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

  • »
    »
    2 weeks 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

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! any news for testdatas? niyaznigmatul PavelKunyavskiy