junkbot's blog

Invitation to APIO 2017 Open Contest
By junkbot, history, 8 years ago, In English

Hi Everyone!

This year Australia is hosting the Asia-Pacific Informatics Olympiad (APIO). Since the official contest window is about to end for contestants, the APIO 2017 Open contest will begin soon! Everyone is invited to participate, and would be good practice for IOI-eligible students.

The contest has a similar format to the IOI, having 3 tasks over 5 hours and will be hosted on the CMS Contest Management System at contest.apio17.org. The contest will be run in two separate windows, each having the same set of problems as the official contest.

  1. Window 1 begins UTC+0 15.00, Monday, May 15
  2. Window 2 begins UTC+0 11.00, Tuesday, May 16

Please note that these times have been pushed back by 24 hours from what was originally advertised on our website.

The supported languages are C11, C++11 and Pascal only. Task statements will be available in English, Chinese (Simplified), Chinese (Traditional), Hebrew, Bahasa Indonesia, Japanese, Korean, Mongolian, Persian, Russian, Thai, Turkish and Vietnamese, with many thanks to the leaders of the respective delegations for providing task translations. Detailed rules for the contest can be found on the contest website http://apio17.org/competition/rules/. Unfortunately, clarifications will not be available during the open contests.

If you would like to participate, please register using the Registration Form. Registration for each contest will close two hours prior to the start of the contest. Update: Once registrations close, you will be emailed a username and password to use to log in to the contest site. Please check your email before the contest begins!

To ensure that each contest is fair, we kindly ask all participants to refrain from discussing the problems until the end of the second open contest window. Update: As a result, please do not participate if you have already competed in the official contest. If you did compete and have already registered, please don't login and compete on the contest system. If you are still competing in the open contest, please only participate and register for one of the two contest windows. Thank you for your co-operation.

Looking forward to your participation!

APIO 2017 Organising Committee

Update: Window 1 registration has closed. Please check your email for login details. The contest site is up and the contest will begin in under two hours' time! Best of luck for the contest.

Update: Window 2 registration has closed. Please check your email for login details. The contest site is up and the contest will begin in under an hour's time! Best of luck for the contest.

Update: The official English problem statements, testdata, contest materials (checkers, graders etc.) and solutions have finally been posted on the official website and also on the APIO website. We apologise for the long delay.

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

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

Are we supposed to receive an email with information regarding our accounts immediately after registering? Or about an hour before the contest or something like that? I'm asking because I've just registered and I haven't received anything.

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

    I've updated the post to say that you will receive login details via email before the contest starts, and after registration closes.

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

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

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

Link to contest.apio17.org is broken, it redirects to codeforces.com/blog/entry/...

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

    The contest website will become active at that URL before the start of each contest day.

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

Are official participants allowed to participate in this ?

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

    No, official contestants are not. I've updated the post to reflect this.

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

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

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

I think I accidentally registered for the wrong window. If I don't participate/log in, am I allowed to register for the second window?

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

    Yes, this is no problem. Just fill out the form again with the correct window =).

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

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

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

You can submit at most 30 solutions during this contest.

Is this per problem, or whole contest?

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

    Ooooh shit, I didn't think about this because it looks pretty stupid but now I'm out of submission so, I'm leaving the contest :( Thnx world.

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

      https://www.youtube.com/watch?v=tPgc7Y5u6EU

      "Who's idea was this?!"

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

        How did you manage to send 30 submissions?

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

          If you aim for 100 in one problem in full feedback contest 10-15 submissions are not too much I think.

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

            What's more surprising is that you made 30 submissions within 90 minutes into the contest (that's when you wrote that comment). That's an average of 1 submission / 3 minutes. Plus, there was a mandatory gap of two minutes between successive submissions...

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

              Actually I waited till the end of contest but like 5 more submissions.

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

                Ahh, okay.

                Somehow I got login credentials for the second window, albeit I didn't register for it...

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

    The rules state "You can only submit at most 30 submissions for a problem, unless otherwise stated." To clarify, this means 30 submissions for each problem. The number of submissions you have left for each problem is always visible on the "Submissions" tab inside the contest management system.

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

      Following up on this, this was incorrectly set during last night's contest and you were only able to submit 30 submissions total. Very many apologies for this — this was not the case in the official contest and won't be the case in Window 2.

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

can anyone access the contest website?

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

Can we ask questions??? As there are some unclear things in the problem statements.

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

    Unfortunately we are unable to provide clarifications during the Open contest due to the difference in timezone in Australia. Many apologies for any inconvenience caused.

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

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

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

Why, when submitting a solution, it only displays the result of a test. The id is changing, so I assume that there is more than one test per subtask but only one is shown? Is that right?

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

I don't have much time to code, but here are my ideas for the two regular problems:

  • rainbow: number of connected components in a submatrix; place "external" river cells around that submatrix, then the answer is v + e + 1 by Euler's theorem, where v is the number of river cells (vertices) and e the number of pairs of adjacent river cells (edges) — v is just submatrix sum, doable using compressed segment trees (IOI 2013 Game) or more simply in time, e is the same for summing up degrees of vertices, then we need to subtract edges going out of the submatrix and add the number of vertices on its border (adjacent to the external vertices)

  • merchant: binsearch the optimal ratio — for ratio r, compute in O(N2) with O(KN2) precomputation the maximum value of (profit by possibly buying at i and selling at j minus r * distance from i to j) for all i, j, then exponentiate that matrix until a non-trivial cycle gives a diagonal value  ≥ 0; time complexity: , where T is the min. number of trades necessary to get the optimal ratio

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

    I confirm that on second problem, this idea passes.

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

    we can just use floyd warshall instead of matrix expo so the complexity becomes

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

    For Problem A(rainbow),why is the answer v+e+1? Could you please explain it in detail?Thanks!

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

      You can view the figure as a planar graph, components are faces. Look up Euler's theorem for more.

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

This is how I solved Merchant (P2).

Let's look at the optimal solution. It starts at some city R, visits several cities, possibly buying and selling at intermediate cities, and returns to R. There are a few observations to make before we proceed:

  • If we buy an item at node B and sell it at node S, then we must take the shortest path from B to S to maximize efficiency. This will be useful later on, so we can precompute dist where dist[i][j] denotes the shortest path from i to j in our original graph. This precomputation takes O(n3).
  • If we buy an item at node B and sell it at node S, we will buy the item which maximizes profit to maximize efficiency. This will also be useful later on, so we can precompute profit where profit[i][j] denotes the maximum profit we can achieve if we buy an item at node i and sell it at node j. If no profit is achievable, profit[i][j] = 0. This precomputation can be done trivially in O(n2k) by iterating over all k items for each (i, j) pair.

Now, let us fix the efficiency we want to achieve. Suppose x is our desired efficiency. We can check if x is feasible using the following procedure:

  • Construct a new adjacency matrix adj, where adj[i][j] = profit[i][j] - dist[i][j] * x. Additionally, define adj[i][i] =  - ∞.

  • Our answer is YES iff there exists a closed walk with a nonnegative sum in adj. We can check this in O(n3) using Floyd-Warshall. Note that you should deal with the case where a positive cycle occurs in adj explicitly, as well as handle annoying overflow issues.

Intuitively, the check() function is looking at our optimal solution in chunks. We are essentially decomposing our optimal walk into individual transactions. One edge in adj corresponds to one transaction. This is useful because when we fix the start and end points of one transaction, we automatically fix the path and item that we need to buy, and are able to reduce the problem to a tractable one.

Finally, it is clear that we can binary search on x, to end with a solution of complexity O(n3log(A) + n2k), where A is the maximum efficiency possible.

Full-Solution in C++

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

    Can you please explain what last Floyd-Warshall in check function does?

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

For P3 (Koala):

Subtasks 1 and 2 were pretty simple. The definition of subtask 3 sort of puzzled me. It essentially asked for a comparator between any two indices. If one could do that, one could also do subtask 5 for a reasonable number of points by just implementing merge-sort. This turned out to be the case: I got 19 points for subtask 3 and 30/53 in subtask 5. So, subtask 3 ended up being really valuable. (67/100 Solution in C++)

Anyway, I wanted to discuss subtask 3. My idea was to assign some price x to items i and j that are being compared, and price 0 to everything else. Based on what the reply is, we can modify x until we get a reply in which items i and j aren't treated the same way. I used a range of [1, 9] for the prices and did binary search, and it worked. All of this was very hand-wavy and based on intuition, so I want to know what others did for this.

Also, can anyone explain the solution for subtask 4 i.e. implementing allValues() with N = 100, W = 200?

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

    Can you explain your solution of subtask 2(Max) please ?

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

      You can read my solution, linked above. It's self-explanatory.

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

        I've got 50 points, but 0 for subtask 2, can you please find my mistake?

        This is my solution.

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

          It is better to assign a cost of instead of k. I think that should fix it.

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

            I've tested it with graders and it printed the correct answer for 1,2,...,100. I think that changing positions would not change the answer and solution of my code, and it need to be correct if at any case it was correct. Am I wrong ?

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

              I don't understand what you're asking. It should make fewer calls if you assign the cost I mentioned above instead of k.

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

          I think this is wrong.

          if(r[v[i]]==0){
     l=v[i];
     v.erase(v.begin()+i);
     i--;
}

          Shouldn't the condition be r[v[i]] ≤ b[v[i]], not r[v[i]] = 0?

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

            I think, if he is not able to put more rocks than you did, he is not gonna put any rocks, isnt it correct ?

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

              Koala always distributes her stones so that she maximises the sum of the values of the items that she wins. If there are are multiple ways to do this, she picks a way which maximises the total number of items that she wins. If there are still multiple ways to do this, she picks any of these ways.

              Putting leftover rocks into some piles is also another optimal way, so I don't think what you understand is correct.

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

    By the way, you only need to search on interval [1;8], because say you put 9s on both P1 and P2 (1-indexation), and they are highest values in array, like 100 and 99, then it means if koala buys both she will need to cutoff 20 (10 + 10) minimal values from array, but these are at least 1 + 2 + ... + 20 = 210 which is greater than 100 + 99 = 199.

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

    For subtask 4, we require less than nlogn queries.So we can use sort to do it if we can compare two elements in only 1 query. We can assign 100 stones for A and B and 0 stone for the other places.In this way,Koala has to choose exactly one of A and B to maximize the final profit and the place Koala chooses has more stones than the other one.Then use this method as the comparator and implement an O(nlogn) sort (I used std::stable_sort).This solution got passed(10/10).

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

      Crap this is so trivial :(

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

        OMG, really :P

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

          I wonder what the official solution to the 53 point subtask is, hopefully it's not recursing and doing brute sort as described below. That doesn't seem very elegant :c

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

my P3 solution for 90 pts
Subtask1. Just place a 1 somewhere and 0 everywhere else , the index not picked is the answer
Subtask2.(Explained in subtask 4 and 5)
Subtask3. find smallest 'i' such that if b[0] = i and b[1] = i and everything else 0 then one of them has a positive r[0/1] and other one has zero. Use binary search
Subtask4 and 5. First theres a shitty solution that use Subtask3 for comparing in inbuilt sort but this wont give much pts. So instead let solve(array[]) return array in sorted order , then i assign W/size(array) to each b[i] which is in array and 0 everywhere , not i put zero r[x]'s in a seperate array and nonzero r[y]'s in a seperate array(solution for subtask 2) , and call for those , if at any time , theres a self loop in recursion , i call the classical shitty sort again.

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

    Can you elaborate more on subtask 5 (53/53 sol)? I can't quite understand what you wrote.

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

      i expected subtask3 solution to fail on a case like p[0] = n , p[1] = n — 1 , p[2..n-1] = anything but it magically passes
      so if you put b[0] , b[1] = 1,1 and everything else as 0 , if r[0] is 1 and r[1] is 0 or reverse , then you found the answer , otherwise continue with b[0],b[1] = 2 and so on , to make it faster , use binary search.

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

      I think I get what you're saying now, for subtask 5. But why does it work within 100 calls?

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

        idk , it just worked so i moved on to the next subtask

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

          I'm talking about the 5th (and last) subtask.

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

            for 5th you can use the subtask 3 solution as a compare function and then use it to sort.
            For more points , i first do something similar to subtask 2 solution to get 2 more arrays "Small" and "Large" and recursively solve for them , if one of them is empty i go back to the brute sort again

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

              Okay that seems like a decent optimization but I was wondering if there were some "nice" solutions.

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

I solved the first problem (rainbow) during the contest with the idea similar to Xellos'. Remember that v - e + f = 1 + C where v denotes the number of vertices, e denotes the number of edges, f denotes the number of faces (including the infinitely wide background face), and C denotes the number of components.

The key idea is this: Let's draw a rectangle of each query and consider the graph only inside it. The graph includes the boundary rectangle, but it should contain nothing outside it. Apply the formula v - e + f = 1 + C to count the number of regions.

Let's see how we can count these.

  • For vertices, we can mark each four points of each cell in a 2D segment tree, with each point counted only once.
  • For edges, there are a few ways to implement. I marked each edge with its midpoint. Again, use an appropriate 2D segment tree.
  • The number of faces includes each river cell, so we have to count those cells. Be careful, it includes the big background. We need another 2D segment tree.

Let's talk about the components. The whole river blob is a single component. Even when it is cut, the query rectangle will keep it connected. Thus, when the river cells touch the outer query rectangle, the whole things compose single component(C = 1). When there is at least one river cell in the query rectangle but no river cells touch the outer query rectangle, C = 2. Finding out whether the river touch the outer query rectangle can be done by comparing max. and min. coordinate range of river cells.

I had to take a cell as a square with four vertices and four edges. When I took each river cell as a vertex, it was hard for me to solve this case:

.ooo
.o.o
..oo
....

The snake went through o cells, and the query is asking the inner 2x2 region. I found this in the last 30 minutes, and fortunately I solved it >_<

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

    Happily, I found the test just 3 hours after the contest. Unhappily, I had no quick fix and abandoned the whole last 3 subtasks...

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

Is there an online judge on which we can find this problems (or we will be able to)?

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

    I think we will open the problems like this.

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

      Ok. Do you know when because I really want to upsolve?

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

        I really cannot tell because we don't know when will the test data be revealed. We will upload the problem as soon as possible after we get the materials.

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

Is there a serious issue with appeal process? Or is something wrong with the web server? Whatever the problem is, could you please announce it?

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

As 2 days passed after the expected date for the results, does anyone have the results for the online mirror or can other people post how many points did they score?

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

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

    I really want to know the result and also whether there is a medal or results, so I e-mailed like this:

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

I am starting to think that the IOI results will be announced before the APIO results at this rate.

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

    Maybe someone will post the unofficial results (f*ck the rules)?

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

    You mean IOI 2018 right?

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

I think the sever was hacked by wannacry virus and they thought they could decode the files without paying for the hackers. So all the databases were lost ! We will never see the "Official result" !. Poor Australia !

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

Here are the official results.

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

I hope to see the tasks and test data, too (within this year). Thank you!

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

Can you guys post the test data and other materials for the problems?

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

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

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

    I like how it took longer for APIO 2017 to publish their test data than APIO 2018.

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

Finally! You can submit all the problems right here: https://oj.uz/problems/source/331

However, we don't know the exact time and memory limit, so we set arbitrarily. If you know the exact time and memory limit, please let us know. Also, we have changed the official grader to encrypt the test input, so if you find a bug please tell us. Thanks :D

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

    It turned out that interactor of problem Koala was incorrect, so we rejudged all submissions, sorry for that :p

    Now, the problem doesn't use an interactor.

    → Reply