Whistle's blog

APIO 2016
By Whistle, history, 8 years ago, In English

APIO 2016 (Asia-Pacific Informatics Olympiad) will take place in 7-9 may 2016 hosted by Republic of Korea .
official site . competition rules .

Practice session will start at 3 May and end in 5 May .
wish good luck for all participants .
UPD : practice session has been started , Link.
UPD2 : contest has been started and it will end at 8 May 11 GMT. UPD3 : open contest day has been ended

Problems : problem 1 , problem 2, problem 3
UPD4 :Official results
congratulation for all medals winners
first place : yokozuna57 and namonakiaccount
second place : yutaka1999

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

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

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

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

Can I participate ? I'm not in Informatics Olympiad

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

Really liked A :)

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

The problems in the practice session are from BOI2014.

http://www.boi2014.lmio.lt/

https://github.com/boi-2014/tasks

gl & hf;

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

30 submission max allowed on each problem, and max one submission in 5 minutes. Isn't that too much? :/

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

    In worst case you will submit 60 codes :/ (the sum of allowed submissions is 90 !) .

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

      in 5 minutes you can submit 3 submissions ,one for each problem
      so in worst case you will submit 60 codes for every problem and it's allowed only for 30

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

        No not for each probelm .

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

          in practice session I tried to submit 2 codes in one minute
          one for each problem , and it was worked.

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

Please don't share problems/codes/solutions/scores here or anywhere else until the end of the contest that will make the contest unfair.

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

How much points are needed to get silver?

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

how do you get beyond subtask 2 of fireworks?

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

    Let me guess you got 100+26+100 ?

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

      Nope. 31+26+100=157. I am bad at math so I couldn't solve boat.

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

        Can you explain your solution for the third problem ?

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

          So we first do one query from 0...INF to "bound" the range, i.e. know the smallest and largest number. This costs N+1.

          Let's say the smallest number is X and the largest number is Y. Note that there are N-2 numbers from [X+1, Y-1]. So we split this segment into approximately equal (can be off by 1) N-1 pieces, each of about length (Y-X-1)/(N-1).

          By pigeonhole principle, one of these segments must be empty right? So the largest gap will not be any smaller than a single segment size, so that rules out any gaps within a segment to be the largest.

          So we can just compare gaps in between segments and find the largest among them.

          As an example, if the query results are: (1, 5) (-1) (-1) (17, 20) (23, 23)

          We will just compare the gaps of 5-17 and 20-23. This will give you the largest gap no matter what.

          Since there are N-1 segments, and the total number of elements queried is N-1, the total points used is

          (N+1) for initial query + (N-1) queries + (N-1) total elements = 3N-1 < 3N.

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

      My teammate got 100 — 26 — 100. minh141198

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

      Looks you are very curious. SO what's your score?

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

    Subtask 3 (hard one) : the tree dp in ST2 can be expressed in a combination of linear function (like CHT). you should modify it while moving up to parent, and "add" two function in merging step. Details omitted (cause I don't know it too.) for ST4 I think merging from small -> large idea will help.

    Subtask 3 (easy one) : I "guess" (I have no proof) that, in one of the optimal way, the explosion time is one of the depth of leaf node. Now, we can modify the tree dp in ST2. (I need sliding window for this)

    I come up with that "easy one" in last 10 minutes, so I couldn't even submit it. Use this solution at your own risk.

    My score : 100-26-100. (Top in Korea, Dongwook Hwang (Inhibitor) have same score with me too.)

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

      easy one : MY GUESS IS WRONG. countercase :

      2 5
1 1
1 299
1 299
2 300
2 300
2 300

      answer is 300 -> 2, while all leaf have 299 / 301 depth. It's even hard to get 255..

      (Thanks gs12117 for informing this!)

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

      The dp procedure is something like Minkowski sums. And after some observation it's possible to maintain all the points where slope of the function changes, simply using std::set (handwrite BST is not necessary), merging from small to large, which gives an O(nlog^2 n) solution. (I wrote this and got 100pts) And it's easy to find that there are only "extract max" operation needed, so if you replace std::set by leftist trees you will get an O(nlogn) solution.

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

        I still don't understand what are you storing in each dp state? How does the function look like?

        Please elaborate further :)

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

        Thanks for your reply :) I will read it after thinking more.

        (seems like you participated unofficially, right?)

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

      Cool, looks like q2 was actually the hard question. Funny that was the only question I solved.

      My score: 9-100-30

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

    You think in terms of a cost function for each subtree. Then you realize it is always a convex function (have a region of global minimum in the middle, and gradient >= 1 everywhere else). You just propagate this up the tree, and done.

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

      Can you explain what you did in bigger detail ? How did you calculate the cost function efficiently ?

      How do you merge 2 cost functions?

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

        The cost function is the cost of adjusting the subtree such that the path to each leaf is equal.

        We need to support 2 important operations:

        1. Send a cost function up a tree

        2. Merge cost functions of subtrees (that have already been sent up their edge)

        For 2. we can store our cost function as points where the gradient changes (a point for each +1), in a sbbst, along with the initial (at 0) gradient and intercept. Merging them is simply adding the initial gradient and intercept, and merging the bsts, which could be done efficiently using the small merge principle.

        1. involves choosing how much to change the edge we are going up. Notice that as long as we can't change the subtree for free (i.e. move around at the optimum), it is more optimal to change the single edge as much as possible. Let len be the length of the edge, not changing the edge at all would result in the function shifted right by len. However, for everywhere left of the optimum, we will try to use the edge as much as possible, thus it is shifted left and up by len. Everywhere right of the optimum we can increase the edge by however much we want, thus it's always gradient 1. Therefore, the net result is that the optimum is shifted right by len, everything left of the optimum is shifted up by len, and they are connected with gradient 1. In our representation, the net result is simpler: intercept+=len, the two points at the ends of the optimum shifts right by len, and all points after the optimum are deleted.

        By using this algorithm to propagate the function up the tree, we can easily find the optimum at the root.

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

    How to solve 2nd subtask?

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

      Dp[node][l]=the minimum cost for changing lengths in the subtree of v such that the distance to all leafs is l .

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

        How to calculate it? :)

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

          Dp[v][l]=sigma(u) {min(k){dp[u][k]+|l-k|} } u is a child of v and k is some length .

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

Did anybody score 100 in fireworks?

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

    Did anyone get more than 26?

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

    I did, being the only question I solved ... Wasn't a super complicated algorithm, but I spent all my time sorting out the details ...

    9-100-30

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

I scored 9 + 26 + 48.18 :(
What do you think will be the medals limits?

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

    I scored 9 + 7 + 45.5 :/
    I think the bronze limit will be about 94 .

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

    100 or above — bronze 150 or above — silver 200 or above — gold throwing random guesses :P

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

    I think it will be 68.39 for bronze.

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

when does apio deliver medals?

or do they give medals at all?

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

    They usually give medal certificates to country leaders in IOI.

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

      medals? or just certificates telling that they won bronze/silver/gold?

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

    Why don't they give medals anyway?!

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

      They don't have a ceremony or anything like that, simply the deputy leader of team of the host country carries all certificates with him and gives them to other deputy leaders and that's it basically.

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

    I was thinking of getting a nice medal and then i saw this comment :(

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

Full solution for subtask 2 P3 :

Step 1 : Find a_1 and a_n

Query(0, 10^{18}) to get the values of a_1 and a_n. This increases M to N + 1.

Now, divide the range [a_1 + 1, a_n — 1] into n — 1 equal blocks. Since there are n — 2 elements in the range but there are n — 1 blocks, at least one block is empty. So, if we let D be the distance for one block, then the answer is > D. So, we know that the answer will not be the difference of two elements in the same block.

Now, we just go from the start (a_1), and query each of the blocks to get its min and max element (if they exist) and update the maximum difference accordingly. Since we do N — 1 queries and there're N — 2 numbers involved in the queries, the total value of M is N + 1 + N — 1 + N — 2 = 3N — 2 < 3N.

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

Where are the unofficial results ?

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

    Unofficial results are only passed to delegation leaders.

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

Unofficial Medal Cutoffs :

Bronze : 87

Silver : 138

Gold : 215.04

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

Help debug — https://ideone.com/oOKjFC. For "gap"

It says that it terminated with a nonzero exist code, which means that in one of my inputs, my s is larger than my t, but I don't see this happening...

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

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

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

I scored 55 points in fireworks, but it took me too much time.

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

Competition data (tasks, tests, solutions) are uploaded in apio2016.org

You can also find it in Github : https://github.com/apio-2016/apio2016-tasks

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

Why are the unofficial results not published yet?

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

    it only passed to delegation leaders.

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

      Why is it only passed to delegation leaders, then?

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

        It's the unofficial results, just for teams to check if there were any mistakes in their scores (compared to the score they received in contest).

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

          I just don't equate "unofficial" with "hidden", especially when part of it (cutoffs) is published/leaked and when it's even listed in the schedule.

          If it's supposed to be secret, this discussion wasn't supposed to exist at all. If it's not, why not publish it with a note saying "unofficial results"?

          UPD: Wow, all those downvotes — logic must make some people really butthurt.

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

            I guess, delegation leaders get a list with points of their state participants only. There should be no other information regarding others' scores or medal distribution. This procedure is needed for the appeal, if the scores turn out to be somehow wrong. Personally, i think leak of medal cutoffs is not due to the unofficial results, there might as well be other sources.

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

              Actually our delegation leader sent a list that contain all participants. If our leader have a permission to see list, it should what planned to do. So we know cutoffs due to unoffical results, BTW cutoffs aren't "leak", we can just see it.

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

            IMHO, list isn't secret, they just didn't think to publish unoffical one, BTW I don't know that's the reason.

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

              yeah that makes no sense at all

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

              in 2014 and 2015 they published the unofficial results.

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

    So now that every delegation leader knows the results and medal cutoffs. Why the delay with posting official results?!

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

Official Result is available: http://apio2016.org/results/

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

Results are finally out. Yay! http://apio2016.org/results/

Boat has 31 full scorers, Fireworks has 4 full scorers, Gap has 40 full scorers. (Correct me if I counted wrong)

Korean top6 :

Jaehyun Koo (ko_osaga) (100 / 26 / 100)

Dongwook Hwang (Inhibitor) (100 / 26 / 100)

Donghyun Kim (kdh9949) (100 / 26 / 49.72)

Hyunsoo Kim (khsoo01) (31 / 26 / 100)

Sunjay Oh (ggoh) (31 / 26 / 100)

Junseo Koo (31 / 7 / 100)

Also congratulations to Ultimate tonyjjw !

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

I know I'm going to get downvoted to oblivion, but I really think this is unfair. Scoring 80-86.5 is much harder than scoring 87. :(

I know both are bad anyway

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

Did teams from Russia participate in APIO 2016?

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

    By APIO rules, all contestants should participate onsite. We were not able to satisfy this condition, so participated only unofficially. Our top results are 226 from SpyCheese and josdas.

    → Reply