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.

- Window 1 begins UTC+0 15.00, Monday, May 15
- 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.

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.

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

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/...

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

Are official participants allowed to participate in this ?

No, official contestants are not. I've updated the post to reflect 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?

Yes, this is no problem. Just fill out the form again with the correct 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?

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.

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

"Who's idea was this?!"

How did you manage to send 30 submissions?

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

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

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

Ahh, okay.

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

Exactly...

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.

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.

can anyone access the contest website?

Check your email.

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

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.

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?

Please see the rules http://apio17.org/competition/rules/ under "Grading" for information on this.

Thanks a lot! Sorry for asking about something stated in the rules. I should've read them.

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, wherevis the number of river cells (vertices) andethe number of pairs of adjacent river cells (edges) —vis just submatrix sum, doable using compressed segment trees (IOI 2013 Game) or more simply in time,eis 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 inO(N^{2}) withO(KN^{2}) precomputation the maximum value of (profit by possibly buying atiand selling atjminusr* distance fromitoj) for alli,j, then exponentiate that matrix until a non-trivial cycle gives a diagonal value ≥ 0; time complexity: , whereTis the min. number of trades necessary to get the optimal ratioI confirm that on second problem, this idea passes.

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

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

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

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 toR. There are a few observations to make before we proceed:Band sell it at nodeS, then we must take the shortest path fromBtoSto maximize efficiency. This will be useful later on, so we can precomputedistwheredist[i][j] denotes the shortest path fromitojin our original graph. This precomputation takesO(n^{3}).Band sell it at nodeS, we will buy the item which maximizes profit to maximize efficiency. This will also be useful later on, so we can precomputeprofitwhereprofit[i][j] denotes the maximum profit we can achieve if we buy an item at nodeiand sell it at nodej. If no profit is achievable,profit[i][j] = 0. This precomputation can be done trivially inO(n^{2}k) by iterating over allkitems for each (i,j) pair.Now, let us fix the efficiency we want to achieve. Suppose

xis our desired efficiency. We can check ifxis feasible using the following procedure:Construct a new adjacency matrix

adj, whereadj[i][j] =profit[i][j] -dist[i][j] *x. Additionally, defineadj[i][i] = - ∞.Our answer is YES iff there exists a closed walk with a

nonnegativesum inadj. We can check this inO(n^{3}) using Floyd-Warshall. Note that you should deal with the case where a positive cycle occurs inadjexplicitly, as well as handle annoying overflow issues.Intuitively, the

check() function is looking at our optimal solution inchunks. We are essentially decomposing our optimal walk into individualtransactions. One edge inadjcorresponds 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 complexityO(n^{3}log(A) +n^{2}k), whereAis the maximum efficiency possible.Full-Solution in C++

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

It checks if a positive cycle occurs in

adj.Thank you.

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

xto itemsiandjthat are being compared, and price 0 to everything else. Based on what the reply is, we can modifyxuntil we get a reply in which itemsiandjaren'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() withN= 100,W= 200?Can you explain your solution of subtask 2(Max) please ?

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

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

This is my solution.

It is better to assign a cost of instead of

k. I think that should fix 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 ?

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

k.Never mind.

I think this is wrong.

Shouldn't the condition be

r[v[i]] ≤b[v[i]], notr[v[i]] = 0?I think, if he is not able to put more rocks than you did, he is not gonna put any rocks, isnt it correct ?

`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.

Youre right, thanks

By the way, you only need to search on interval [1;8], because say you put 9s on both

P_{1}andP_{2}(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.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).

Crap this is so trivial :(

OMG, really :P

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

+

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.

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

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.

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

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

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

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

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

I solved the first problem (rainbow) during the contest with the idea similar to Xellos'. Remember that

v-e+f= 1 +Cwherevdenotes the number of vertices,edenotes the number of edges,fdenotes the number of faces (including the infinitely wide background face), andCdenotes 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 formulav-e+f= 1 +Cto count the number of regions.Let's see how we can count these.

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:

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 >_<Happily, I found the test just 3 hours after the contest. Unhappily, I had no quick fix and abandoned the whole last 3 subtasks...

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

I think we will open the problems like this.

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

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.

Ok. Thank you.

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?

At last I started to believe the inexistent Australia hoax....

And junkbot may really be just a bot...

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?

73 unofficial

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

Do you always use your CP name in your email? That's interesting.

Have they replied you ?