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.

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

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

Are official participants allowed to participate in this ?

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

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?

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

You can submit at most 30 solutions during this contest.

Is this per problem, or whole contest?

can anyone access the contest website?

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

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

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?

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(N²) with O(KN²) 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

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(n³).
• 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(n²k) 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(n³) 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(n³log(A) + n²k), where A is the maximum efficiency possible.

Full-Solution in C++

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?

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.

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 >_<

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

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?

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?

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

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 !

Here are the official results.

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

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

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

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