Invitation to APIO 2017 Open Contest

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

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.

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.

Comments (94)

Write comment?

geniucos

7 years ago, # |

+10

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

junkbot

7 years ago, # ^ |

+18

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

VladaMG98

+11

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.

abcdef6199

+15

Are official participants allowed to participate in this ?

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

-is-this-fft-

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

animeshf

You can submit at most 30 solutions during this contest.

Is this per problem, or whole contest?

kalimm

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

← Rev. 2 →

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.

rajat1603

+13

can anyone access the contest website?

Check your email.

radoslav11

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.

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.

Xellos

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 $\text{[math]}$ 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: $\text{[math]}$ , where T is the min. number of trades necessary to get the optimal ratio

I confirm that on second problem, this idea passes.

+20

we can just use floyd warshall instead of matrix expo so the complexity becomes $\text{[math]}$

Marco_L_T

← Rev. 3 →

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.

+30

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

zadrga

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

Khazhak

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.

← Rev. 7 →

It is better to assign a cost of $\text{[math]}$ 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.

zoomswk

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?

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

Azret

By the way, you only need to search on interval [1;8], because say you put 9s on both P₁ and P₂ (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.

Namnamseo

+25

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

natsukagami

+28

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)?

ojuz

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.

+36

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?

+39

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

+23

And junkbot may really be just a bot...

+26

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

i4018

+89

square1001

+69

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

redocyz

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

goodthingstaketime_._

Have they replied you ?

E869120

If they haven't replied, I think it is too late.
Now, the time became June!

UPD: The APIO committee opened the result on Monday, June 5th.

Finally, the APIO committee opened the result!
http://apio17.org/results/

+53

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

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

+85

You mean IOI 2018 right?

+34

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!

sampriti

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

6 years ago, # |

kaldiuo

6 years ago, # ^ |

+24

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

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

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.

junkbot's blog