### junkbot's blog

By junkbot, history, 13 months ago, ,

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.

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.

•
• +63
•

 » 13 months 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.
•  » » 13 months 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.
 » 13 months ago, # |   0 Auto comment: topic has been updated by junkbot (previous revision, new revision, compare).
 » 13 months ago, # |   +11 Link to contest.apio17.org is broken, it redirects to codeforces.com/blog/entry/...
•  » » 13 months ago, # ^ |   +10 The contest website will become active at that URL before the start of each contest day.
 » 13 months ago, # |   +15 Are official participants allowed to participate in this ?
•  » » 13 months ago, # ^ |   +10 No, official contestants are not. I've updated the post to reflect this.
 » 13 months ago, # |   0 Auto comment: topic has been updated by junkbot (previous revision, new revision, compare).
 » 13 months ago, # |   +10 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?
•  » » 13 months ago, # ^ |   +10 Yes, this is no problem. Just fill out the form again with the correct window =).
 » 13 months ago, # |   0 Auto comment: topic has been updated by junkbot (previous revision, new revision, compare).
 » 13 months ago, # |   +10 You can submit at most 30 solutions during this contest.Is this per problem, or whole contest?
•  » » 13 months ago, # ^ |   0 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.
•  » » » » 13 months ago, # ^ |   0 How did you manage to send 30 submissions?
•  » » » » » 13 months ago, # ^ |   0 If you aim for 100 in one problem in full feedback contest 10-15 submissions are not too much I think.
•  » » » » » » 13 months ago, # ^ |   +3 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...
•  » » » » » » » 13 months ago, # ^ |   0 Actually I waited till the end of contest but like 5 more submissions.
•  » » » » » » » » 13 months ago, # ^ |   0 Ahh, okay. Somehow I got login credentials for the second window, albeit I didn't register for it...
•  » » » » » » » » » 13 months ago, # ^ |   0 Exactly...
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +15 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.
 » 13 months ago, # |   +13 can anyone access the contest website?
•  » » 13 months ago, # ^ |   +10 Check your email.
 » 13 months ago, # |   +5 Can we ask questions??? As there are some unclear things in the problem statements.
•  » » 13 months ago, # ^ |   +10 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.
 » 13 months ago, # |   0 Auto comment: topic has been updated by junkbot (previous revision, new revision, compare).
 » 13 months ago, # |   0 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?
•  » » 13 months ago, # ^ |   +18 Please see the rules http://apio17.org/competition/rules/ under "Grading" for information on this.
•  » » » 13 months ago, # ^ |   +10 Thanks a lot! Sorry for asking about something stated in the rules. I should've read them.
 » 13 months ago, # |   +18 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
•  » » 13 months ago, # ^ |   +10 I confirm that on second problem, this idea passes.
•  » » 13 months ago, # ^ |   +20 we can just use floyd warshall instead of matrix expo so the complexity becomes
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 For Problem A(rainbow),why is the answer v+e+1? Could you please explain it in detail?Thanks!
•  » » » 13 months ago, # ^ |   +10 You can view the figure as a planar graph, components are faces. Look up Euler's theorem for more.
•  » » 13 months ago, # ^ |   0 Can you please explain what last Floyd-Warshall in check function does?
•  » » » 13 months ago, # ^ |   +13 It checks if a positive cycle occurs in adj.
•  » » » » 13 months ago, # ^ |   0 Thank you.
•  » » 13 months ago, # ^ |   0 Can you explain your solution of subtask 2(Max) please ?
•  » » » 13 months ago, # ^ |   0 You can read my solution, linked above. It's self-explanatory.
•  » » » » 13 months ago, # ^ | ← Rev. 3 →   0 I've got 50 points, but 0 for subtask 2, can you please find my mistake?This is my solution.
•  » » » » » 13 months ago, # ^ | ← Rev. 7 →   +5 It is better to assign a cost of instead of k. I think that should fix it.
•  » » » » » » 13 months ago, # ^ |   0 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 ?
•  » » » » » » » 13 months ago, # ^ |   0 I don't understand what you're asking. It should make fewer calls if you assign the cost I mentioned above instead of k.
•  » » » » » » » » 13 months ago, # ^ |   0 Never mind.
•  » » » » » 13 months ago, # ^ |   +5 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?
•  » » » » » » 13 months ago, # ^ |   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 ?
•  » » » » » » » 13 months ago, # ^ |   0 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.
•  » » » » » » » » 13 months ago, # ^ |   0 Youre right, thanks
•  » » 13 months ago, # ^ |   0 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.
•  » » 13 months ago, # ^ |   +18 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).
•  » » » 13 months ago, # ^ |   0 Crap this is so trivial :(
•  » » » » 13 months ago, # ^ |   0 OMG, really :P
•  » » » » » 13 months ago, # ^ |   0 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
•  » » » » » » 13 months ago, # ^ |   +3 +
 » 13 months ago, # | ← Rev. 2 →   +10 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.
•  » » 13 months ago, # ^ |   0 Can you elaborate more on subtask 5 (53/53 sol)? I can't quite understand what you wrote.
•  » » » 13 months ago, # ^ |   0 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.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 I think I get what you're saying now, for subtask 5. But why does it work within 100 calls?
•  » » » » 13 months ago, # ^ |   +5 idk , it just worked so i moved on to the next subtask
•  » » » » » 13 months ago, # ^ |   0 I'm talking about the 5th (and last) subtask.
•  » » » » » » 13 months ago, # ^ |   0 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
•  » » » » » » » 13 months ago, # ^ |   0 Okay that seems like a decent optimization but I was wondering if there were some "nice" solutions.
 » 13 months ago, # |   +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 >_<
•  » » 13 months ago, # ^ |   +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...
 » 13 months ago, # |   0 Is there an online judge on which we can find this problems (or we will be able to)?
•  » » 13 months ago, # ^ |   +30 I think we will open the problems like this.
•  » » » 13 months ago, # ^ |   0 Ok. Do you know when because I really want to upsolve?
•  » » » » 13 months ago, # ^ |   +30 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.
•  » » » » » 13 months ago, # ^ |   0 Ok. Thank you.
 » 13 months ago, # |   +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?
•  » » 13 months ago, # ^ |   +39 At last I started to believe the inexistent Australia hoax....
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +23 And junkbot may really be just a bot...
 » 13 months ago, # |   +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?
•  » » 13 months ago, # ^ |   +3 73 unofficial
 » 13 months ago, # |   +89
•  » » 13 months ago, # ^ |   +69 I really want to know the result and also whether there is a medal or results, so I e-mailed like this:
•  » » » 13 months ago, # ^ |   +23 Do you always use your CP name in your email? That's interesting.
•  » » » 13 months ago, # ^ |   +18 Have they replied you ?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » » » 13 months ago, # ^ |   +5 Finally, the APIO committee opened the result! http://apio17.org/results/
 » 13 months ago, # |   +53 I am starting to think that the IOI results will be announced before the APIO results at this rate.
•  » » 13 months ago, # ^ |   +6 Maybe someone will post the unofficial results (f*ck the rules)?
•  » » 13 months ago, # ^ |   +85 You mean IOI 2018 right?
 » 13 months ago, # |   +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 !
 » 13 months ago, # |   +8 Here are the official results.
 » 13 months ago, # |   +13 I hope to see the tasks and test data, too (within this year). Thank you!
 » 12 months ago, # |   +13 Can you guys post the test data and other materials for the problems?
 » 3 weeks ago, # |   +36 Auto comment: topic has been updated by junkbot (previous revision, new revision, compare).
•  » » 3 weeks ago, # ^ |   +24 I like how it took longer for APIO 2017 to publish their test data than APIO 2018.
 » 3 weeks ago, # |   +10 Finally! You can submit all the problems right here: https://oj.uz/problems/source/331However, 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