fushar's blog

Asia-Pacific Informatics Olympiad (APIO) 2015 (online mirror available!)
By fushar, 9 years ago, In English

Hello,

Indonesia is hosting this year's APIO 2015. The contest will take place on this weekend, May 9 2015.

We also provide a mirror contest, called Open APIO 2015, after the official contest day for everyone to participate. It will be a 5-hour virtual contest that you can start any time between Sunday, 10 May 2015, 20:00 (UTC+7) and Monday, 11 May 2015, 20:00 (UTC+7). We really encourage you to try the problems, just for fun!

Here are the details:

  • Register here: https://competition.ia-toki.org/contests/18/view. Registration closes 1 hour before Open APIO 2015 ends. If you don't have account on TLX (our contest system), you will be prompted to register on TLX.
  • No medals/certificates will be awarded.

The rules for Open APIO 2015 are similar to the official one:

  • There will be 3 IOI-style problems.
  • You can only submit at most 30 submissions for a problem.
  • You will get full feedback for each submission.
  • For each problem, there are several subtasks:
    • For each subtask, there are points assigned to it.
    • Each subtask contains several test cases.
    • You get the points from that subtask if the program passes all the test cases in that subtask.
  • The score of a submission is the sum of all the points that you get from completing subtasks.
  • The final score for a problem is the maximum of all the submission scores for that problem.

And here are the grading environment specifications:

  • OS: Ubuntu 14.04.1 LTS
  • Kernel: Linux 3.13.0-36-generic #63-Ubuntu SMP Wed Sep 3 21:30:07 UTC 2014 x86_64
  • CPU: Intel Xeon E5-2666 v3 2.90GHz
  • Compilers:
    • gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2 (flags: -O2 -lm)
    • g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2 (flags: -std=c++11 -O2 -lm)
    • fpc 2.6.2-8 [2014/01/22] for x86_64 (flags: -O2 -XS -Sg)
  • You must print a newline ('\n') after each line in your output.

You can also discuss the problems on this thread, but please do so after Open APIO 2015 ends.

Thanks,

APIO 2015 organizers

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

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Dying of curiosity. In which countries APIO'15 have already been held?

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

    Currently all countries registered in APIO have already finished their contest:

    1. Armenia
    2. Australia
    3. Bangladesh
    4. China
    5. Hong Kong
    6. India
    7. Indonesia
    8. Iran
    9. Israel
    10. Japan
    11. Kazakhstan
    12. Kyrgyzstan
    13. Macao
    14. Malaysia
    15. Mongolia
    16. New Zealand
    17. Philippines
    18. Singapore
    19. South Korea
    20. Sri Lanka
    21. Syria
    22. Taiwan
    23. Tajikistan
    24. Thailand
    25. Turkey
    26. Turkmenistan
    27. Vietnam
    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Is there anything wrong with the grading system?

After I have submitted my solution, it shows "Pending" for a long time. After that, it became "Internal Error".

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

    Grader is up again, sorry for the inconvenience.

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

When will you publish results?

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

Hello everyone. I would like to ask a question. On this website (http://www.apio2015.org/schedules.html) it is written that today, there are Unofficial result — Unofficial results of this Official participants ?? Thanks in advance.

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

Sorry for the delay of the unofficial results. We are currently in the process of compiling the results.

Thanks!

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

Well was i too late for the contest? (open one)

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

Why don't we tell our own scores while waiting for the results?

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

Nice problems, I like it when the problems are more about thinking then coding.

The downside is I wouldn't be surprised if there were many people tied with 300 points...

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

I am sorry to say, but problem's quality was much lower than last 3-4 years.

First of all 120 points were requiring shortest path algorithms:( and another 80 from first problem was easy dynamic programming.

Also third problem had 63 points which has limits N <= 1000 or K = 1. And those 63 points was not worth it.

Seriosly why just 37 points for the last subtask which is the only interesting and non-standart one?

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

    Hint: I wrote problem B, and I forgot to increase the constraint for N to 1,000,000,000 (originally, we were planning to allow only (N+M) sqrt (N+M) solutions to pass. But, we're lenient, so we allow (N+M) sqrt (N+M) log (N+M) to pass too. But then, the constraint should have N <= 10^9).

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

      Saddest part is, a lot of people with 100 points did not even noticed it was .

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

        I agree! It's even sadder since some of the test cases are rather weak.

        (now... let's focus on the N <= 10^9 version. Can u solve it? Edit: can anyone solve it?)

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

          Sorry for necroposting, but can someone explain the solution for N <= 10^9 variant of the problem?

          I tried looking for old analysis's etc., everything gets 404. :(

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

            If I recall correctly, there is nothing written about O(M1.5lg(N + M)) solution in Editorial.

            And now I'm also very curious about the solution too.

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

      I think you meant , right?

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

Really got tired of waiting for the results.
Can you at least tell that will the results be up today or not ???

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

What do you think the medal ranges will be?

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

    Either 104 or 66 for bronze, because life is full of cruel jokes :P

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

LiTi and SMAKH both got the 6th place in Iran, which one is gonna be in official results ?

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

how is the solution for the B problem?

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

    First delete doges with equal Pi in the same building, because they make no difference.

    For every doge with power Pi present in building Bi, add an edge from Bi to Bi + Pi with cost 1 (meaning this doge jumps 1 time to the positive direction).

    If there is a doge with the same power Pi in building Bi + Pi, stop adding edges for this doge (jumping further makes no sense because passing information to this new doge and having the new doge jump is the same thing). Otherwise, continue by adding edge from Bi to Bi + 2*Pi with cost 2 and check if there is a doge there with same power, and so on. Add edges similarly for jumps in the negative direction.

    Now just run Dijkstra's algorithm. Dijkstra's is O(E log V) and we have at most O(n sqrt(m)) edges, so complexity is O(n sqrt(m) log(n)).

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

      thanks

      my different was just the "stop adding edge" thing and it cost me TLE :/

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

        Makes sense, without that the number of edges might be equal to nm (imagine a bunch of doges with power 1, for example). I assume this was the difference between the last two subtasks and the rest.

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

      where does the upper limit n sqrt(m) come from? can you explain it a bit more?

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

        I'm not sure I remember the problem correctly, but consider all doges with power P. Each building only gets at most two edges from each direction (since the others would stop before getting there), so the total number of edges is O(N).

        An individual doge with power P also contributes at most O(N/Pi) edges.

        So for doges with power < sqrt(N), there are sqrt(N) different powers so they contribute at most O(N sqrt N), and for doges with power > sqrt(N), each of them contributes at most sqrt(N) so they contribute at most O(M sqrt N) in total.

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

how to solve full A and C problem?

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

    C : the problem is just if K=2. if we have one fixed bridge position x, the cost for each pair bridge (x,y) with increasing y will form a curve (and my friend found that in the bottom of a curve, it is 'not a curve') so, just use ternary search for both x,y , and when left and right bound is close enough, just use brute force.

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

      So we use ternary search for finding "fixed" bridge x first without considering second pair, then use ternary for find bridge y?

      How if choosing the first "fixed" is not the optimal one?

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

        like this -> ternary(x){ ternary(y) }. i can't explain well, so it's my AC code http://ideone.com/UO6QOK

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

          You got lucky. Your code fails, for example, on the test case in edit.

          I don't know if it can be fixed or not, but I'd need a proof that ternary search on x works to believe it.

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

            Even if the dy/dx is monoton, one can create a test case where dy = 0. So ternary search is not usefull in this problem.

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

            i solved it in open APIO, so i am not that lucky :X

            in the "real APIO", i used ternary search only for the second bridge, and i was bruteforcing the first bridge. i don't know whether it's true or not because i can't proof it, but with testcases i generated, with a same "first bridge", the cost form a curve.

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

            In the contest, I surprised that my solution using ternary search could pass all of tests. When the score 100 was shown, I got a little shock.

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

          I found a counterexample for ternary search(and sliding window solution). http://ideone.com/lF6zCS

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

    C: (assuming you know how to solve K=1)

    Suppose our pair of bridges is (B1, B2), B1 < B2.

    A certain trip x -> y uses B1 if and only if B1 + B2 > x + y (proof omitted).

    So if you sort all trips by increasing order of x + y, the only possible ways to partition the bridges are: the prefixes of this array use B1, corresponding suffixes use B2.

    For each prefix, calculate optimal bridge position (using solution for K=1). For each suffix, calculate optimal bridge position. You can do it faster than calculating it from scratch for every prefix: use a data structure such as a set to be able to keep median incrementally for every prefix in logarithmic time.

    Then choose partition that gives you smallest total travel time and you're done. Code: link

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

      how to get "A certain trip x -> y uses B1 if and only if B1 + B2 > x + y"?

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

        x,y uses B1 if and only if (x - B1) * 2 ≤ (B2 - y) * 2.

        which means x - B1 ≤ B2 - y, so x + y ≤ B1 + B2.(just simple math)

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

      That's amazing. I can't understand why you could find a such solution.

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

        Of course, the solution didn't come ready -- I scribbled a bunch of bridges and homes on paint before I could see that the cost to choose a bridge for a certain trip was symmetric along the midpoint between x and y (), so I could choose which bridge to go to by taking the closest bridge to that midpoint line.

        From there, it's not such a big jump to sort trips by this quantity, and then you're more than halfway there.

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

      Can you explain the idea behind your data structure?

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

        It's quite easy to add a number to a sequence and update the median using C++ set. Suppose that all numbers are pairwise distinct. Maintain a set, an iterator points at the current median and a variable to count the number of value smaller than the median. Whenever adding a number to the set, update the counter and move the iterator if necessary. Take into account that valid iterator remains valid after insert operations.

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

    Another solution for C.

    Let me denote opt(i) as best second position of bridge if first one is on i.

    I claim that opt(i) ≤ opt(i + 1). After then, while using divide and conquer optimization to calculate the total distances i am using 3 fenwick trees.

    Overall complexity is O(N(logN)2).

    Here is the solution for more details : link

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

7 contestants from China got 300 :p

Although I got 100+100+63 which seems a good score, the competition is tooooooo tough :(((

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

    Lol, I feel sorry for the organizers compiling the results is impossible

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

    Actually,there are about ten.

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

The unofficial results can be downloaded on the contest dashboard. Sorry for the delay.

Also, we apologize for the weak test data. We figured it out in the middle of the contest, and it is unfair if we add new test cases.

Thanks!

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

    Thank you very much :)

    And thank you for not changing the test cases. I played a bit with some unproved solutions (which later, after the contest, turned out to be wrong) and ran out of time and could not implement the correct ones that were in my mind. I was afraid that I will lose those points (9 points :D) which I got using unproved solutions.

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

    Gold only for full scores...

    Never imagined such contest :p

    If the test data were stronger there might not be so many full scores and I might get a chance to get in international ranking :p

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

    Yeah, now I understand why it took so long to publish the (unofficial) results.

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

What is the solution for Problem 1? It seemed like dynamic programming. Can someone share their code?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it 
    long long ans = (1LL << 62) - 1;
for (int bit = 61; bit >= 0; bit--) {
  if (check(ans - (1LL << bit))) {
    ans -= (1LL << bit);
  }
}
cout << ans;

    check(mask) — returns true if we can divide our array into groups so that sum in each group is submask of mask.

    For first 3 subtasks where A >= 1 (A and B is number of groups) we can write DP[LEN][GROUPS] — can we divide first LEN elements into GROUPS groups. Total complexity will be O(N^3 * 64).

    For last one, where A = 1 we can write DP[LEN] — minimal number of groups so that we can divide first LEN elements. Complexity is O(N^2 * 64).

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

      Sorry for necroposting, but can you provide your code?

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

        Nope, already deleted it.

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

        Private message is a perfect way to do this.

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

What is the intended solution for problem B with extension N=$10^9$? Can't get any idea for sublinear complexity on N.

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

How can I access problems and the ranking list? I've registered using the above link, but it doesn't show anything when I log in.

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

So when will official result be published? Or we will use unofficial result as official result?

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

    Official results have been announced to country leaders. We will be posting it on the website soon. Thanks!

    → Reply