Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Whistle's blog

By Whistle, history, 4 years ago, ,

APIO 2016 (Asia-Pacific Informatics Olympiad) will take place in 7-9 may 2016 hosted by Republic of Korea .
official site . competition rules .

Practice session will start at 3 May and end in 5 May .
wish good luck for all participants .
UPD : practice session has been started , Link.
UPD2 : contest has been started and it will end at 8 May 11 GMT. UPD3 : open contest day has been ended

Problems : problem 1 , problem 2, problem 3
UPD4 :Official results
congratulation for all medals winners
first place : yokozuna57 and namonakiaccount
second place : yutaka1999

• +53

 » 4 years ago, # |   0 Auto comment: topic has been updated by Whistle (previous revision, new revision, compare).
 » 4 years ago, # |   -6 Can I participate ? I'm not in Informatics Olympiad
•  » » 4 years ago, # ^ | ← Rev. 2 →   -6 .
 » 4 years ago, # |   +17 Really liked A :)
•  » » 4 years ago, # ^ |   +5 Liked cause you saw it before?
 » 4 years ago, # |   +4 The problems in the practice session are from BOI2014.http://www.boi2014.lmio.lt/https://github.com/boi-2014/tasksgl & hf;
 » 4 years ago, # |   0 30 submission max allowed on each problem, and max one submission in 5 minutes. Isn't that too much? :/
•  » » 4 years ago, # ^ |   +3 In worst case you will submit 60 codes :/ (the sum of allowed submissions is 90 !) .
•  » » » 4 years ago, # ^ |   0 in 5 minutes you can submit 3 submissions ,one for each problem so in worst case you will submit 60 codes for every problem and it's allowed only for 30
•  » » » » 4 years ago, # ^ |   0 No not for each probelm .
•  » » » » » 4 years ago, # ^ |   0 in practice session I tried to submit 2 codes in one minute one for each problem , and it was worked.
 » 4 years ago, # |   +10 Please don't share problems/codes/solutions/scores here or anywhere else until the end of the contest that will make the contest unfair.
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   0 how many perfect scores?
 » 4 years ago, # |   0 how to solve A, B, & C?
 » 4 years ago, # |   0 How much points are needed to get silver?
•  » » 4 years ago, # ^ |   0 I got 31-7-100.I hope I get at least a bronze. :|
•  » » » 4 years ago, # ^ |   0 how did you solve the last one?
•  » » » » 4 years ago, # ^ |   0 Hint : Pigeonhole Principle
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 can't believe that thing didn't came into my mind. btw, i got 58-26-52.
•  » » » » » » 4 years ago, # ^ |   0 I still can't believe I missed P2 sub 2 just because I misread the constraints -_-
•  » » » » » » » 4 years ago, # ^ |   0 Me, too T_T.
•  » » » 4 years ago, # ^ |   0 I got 100 — 26 — 30,38. I can't get any points on the second subtask of the last problem.
•  » » » » 4 years ago, # ^ |   0 How did you get P1? My 31 pt solution is some weird fenwick tree dp.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I used dp with combinatorics.
•  » » » » » 4 years ago, # ^ |   0 Solution O(N ^ 3) worked :3 .
•  » » 4 years ago, # ^ | ← Rev. 4 →   +2 What are the top 5 scores in China and Malaysia?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 China : 300? (just a logical guess)Malaysia : Me, 31-7-100 = 138
 » 4 years ago, # |   0 how do you get beyond subtask 2 of fireworks?
•  » » 4 years ago, # ^ |   0 Let me guess you got 100+26+100 ?
•  » » » 4 years ago, # ^ |   0 Nope. 31+26+100=157. I am bad at math so I couldn't solve boat.
•  » » » » 4 years ago, # ^ |   +3 Can you explain your solution for the third problem ?
•  » » » » » 4 years ago, # ^ |   +22 So we first do one query from 0...INF to "bound" the range, i.e. know the smallest and largest number. This costs N+1.Let's say the smallest number is X and the largest number is Y. Note that there are N-2 numbers from [X+1, Y-1]. So we split this segment into approximately equal (can be off by 1) N-1 pieces, each of about length (Y-X-1)/(N-1).By pigeonhole principle, one of these segments must be empty right? So the largest gap will not be any smaller than a single segment size, so that rules out any gaps within a segment to be the largest.So we can just compare gaps in between segments and find the largest among them.As an example, if the query results are: (1, 5) (-1) (-1) (17, 20) (23, 23)We will just compare the gaps of 5-17 and 20-23. This will give you the largest gap no matter what.Since there are N-1 segments, and the total number of elements queried is N-1, the total points used is (N+1) for initial query + (N-1) queries + (N-1) total elements = 3N-1 < 3N.
•  » » » » » » 4 years ago, # ^ |   0 Thanks.
•  » » » 4 years ago, # ^ |   +3 My teammate got 100 — 26 — 100. minh141198
•  » » » » 4 years ago, # ^ |   +3 Cool
•  » » » » 4 years ago, # ^ |   +3 He got a perfect score last year :v .
•  » » » 4 years ago, # ^ |   +3 Looks you are very curious. SO what's your score?
•  » » » » 4 years ago, # ^ |   0 31+7+30.38 :/.
•  » » 4 years ago, # ^ |   +11 Subtask 3 (hard one) : the tree dp in ST2 can be expressed in a combination of linear function (like CHT). you should modify it while moving up to parent, and "add" two function in merging step. Details omitted (cause I don't know it too.) for ST4 I think merging from small -> large idea will help. Subtask 3 (easy one) : I "guess" (I have no proof) that, in one of the optimal way, the explosion time is one of the depth of leaf node. Now, we can modify the tree dp in ST2. (I need sliding window for this)I come up with that "easy one" in last 10 minutes, so I couldn't even submit it. Use this solution at your own risk. My score : 100-26-100. (Top in Korea, Dongwook Hwang (Inhibitor) have same score with me too.)
•  » » » 4 years ago, # ^ |   +3 easy one : MY GUESS IS WRONG. countercase : 2 5 1 1 1 299 1 299 2 300 2 300 2 300 answer is 300 -> 2, while all leaf have 299 / 301 depth. It's even hard to get 255..(Thanks gs12117 for informing this!)
•  » » » 4 years ago, # ^ |   +18 The dp procedure is something like Minkowski sums. And after some observation it's possible to maintain all the points where slope of the function changes, simply using std::set (handwrite BST is not necessary), merging from small to large, which gives an O(nlog^2 n) solution. (I wrote this and got 100pts) And it's easy to find that there are only "extract max" operation needed, so if you replace std::set by leftist trees you will get an O(nlogn) solution.
•  » » » » 4 years ago, # ^ |   0 I still don't understand what are you storing in each dp state? How does the function look like? Please elaborate further :)
•  » » » » 4 years ago, # ^ |   0 Thanks for your reply :) I will read it after thinking more.(seems like you participated unofficially, right?)
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +50 Cool, looks like q2 was actually the hard question. Funny that was the only question I solved.My score: 9-100-30
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 You think in terms of a cost function for each subtree. Then you realize it is always a convex function (have a region of global minimum in the middle, and gradient >= 1 everywhere else). You just propagate this up the tree, and done.
•  » » » 4 years ago, # ^ |   +1 Can you explain what you did in bigger detail ? How did you calculate the cost function efficiently ? How do you merge 2 cost functions?
•  » » » » 4 years ago, # ^ |   +10 The cost function is the cost of adjusting the subtree such that the path to each leaf is equal.We need to support 2 important operations: Send a cost function up a tree Merge cost functions of subtrees (that have already been sent up their edge) For 2. we can store our cost function as points where the gradient changes (a point for each +1), in a sbbst, along with the initial (at 0) gradient and intercept. Merging them is simply adding the initial gradient and intercept, and merging the bsts, which could be done efficiently using the small merge principle. involves choosing how much to change the edge we are going up. Notice that as long as we can't change the subtree for free (i.e. move around at the optimum), it is more optimal to change the single edge as much as possible. Let len be the length of the edge, not changing the edge at all would result in the function shifted right by len. However, for everywhere left of the optimum, we will try to use the edge as much as possible, thus it is shifted left and up by len. Everywhere right of the optimum we can increase the edge by however much we want, thus it's always gradient 1. Therefore, the net result is that the optimum is shifted right by len, everything left of the optimum is shifted up by len, and they are connected with gradient 1. In our representation, the net result is simpler: intercept+=len, the two points at the ends of the optimum shifts right by len, and all points after the optimum are deleted. By using this algorithm to propagate the function up the tree, we can easily find the optimum at the root.
•  » » 4 years ago, # ^ |   0 How to solve 2nd subtask?
•  » » » 4 years ago, # ^ |   0 Dp[node][l]=the minimum cost for changing lengths in the subtree of v such that the distance to all leafs is l .
•  » » » » 4 years ago, # ^ |   0 How to calculate it? :)
•  » » » » » 4 years ago, # ^ |   0 Dp[v][l]=sigma(u) {min(k){dp[u][k]+|l-k|} } u is a child of v and k is some length .
 » 4 years ago, # |   0 Did anybody score 100 in fireworks?
•  » » 4 years ago, # ^ |   +28 Did anyone get more than 26?
•  » » » 4 years ago, # ^ |   0 How much did you score? :D
•  » » » » 4 years ago, # ^ |   +3 100+7+70
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +6 How in the world did you score 70 in problem 3 ? Did you just solve subtask 2 or what @@
•  » » » » » » 4 years ago, # ^ |   +3 Subtask 2 has a scoring formula
•  » » 4 years ago, # ^ |   +4 I did, being the only question I solved ... Wasn't a super complicated algorithm, but I spent all my time sorting out the details ...9-100-30
 » 4 years ago, # |   0 I scored 9 + 26 + 48.18 :( What do you think will be the medals limits?
•  » » 4 years ago, # ^ |   0 I scored 9 + 7 + 45.5 :/ I think the bronze limit will be about 94 .
•  » » 4 years ago, # ^ |   0 100 or above — bronze 150 or above — silver 200 or above — gold throwing random guesses :P
•  » » 4 years ago, # ^ |   +1 I think it will be 68.39 for bronze.
 » 4 years ago, # |   +5 when does apio deliver medals?or do they give medals at all?
•  » » 4 years ago, # ^ |   0 They usually give medal certificates to country leaders in IOI.
•  » » » 4 years ago, # ^ |   0 medals? or just certificates telling that they won bronze/silver/gold?
•  » » » » 4 years ago, # ^ |   0 Just certificates.
•  » » 4 years ago, # ^ |   0 Why don't they give medals anyway?!
•  » » » 4 years ago, # ^ |   0 They don't have a ceremony or anything like that, simply the deputy leader of team of the host country carries all certificates with him and gives them to other deputy leaders and that's it basically.
•  » » 4 years ago, # ^ |   +3 I was thinking of getting a nice medal and then i saw this comment :(
 » 4 years ago, # |   +10 Full solution for subtask 2 P3 :Step 1 : Find a_1 and a_nQuery(0, 10^{18}) to get the values of a_1 and a_n. This increases M to N + 1.Now, divide the range [a_1 + 1, a_n — 1] into n — 1 equal blocks. Since there are n — 2 elements in the range but there are n — 1 blocks, at least one block is empty. So, if we let D be the distance for one block, then the answer is > D. So, we know that the answer will not be the difference of two elements in the same block.Now, we just go from the start (a_1), and query each of the blocks to get its min and max element (if they exist) and update the maximum difference accordingly. Since we do N — 1 queries and there're N — 2 numbers involved in the queries, the total value of M is N + 1 + N — 1 + N — 2 = 3N — 2 < 3N.
 » 4 years ago, # |   +9 Where are the unofficial results ?
•  » » 4 years ago, # ^ |   +8 Unofficial results are only passed to delegation leaders.
 » 4 years ago, # |   +23 Unofficial Medal Cutoffs :Bronze : 87Silver : 138Gold : 215.04
•  » » 4 years ago, # ^ |   0 How do you know that ?
•  » » » 4 years ago, # ^ |   +11 He hacked the APIO website and got the csv sheet with the results :D
•  » » 4 years ago, # ^ | ← Rev. 2 →   +4 Being 3 points off from Bronze. Worst Best feeling in the world!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +11 Being 3 points off from Silver. Worst Best feeling in the world!
 » 4 years ago, # |   0 Help debug — https://ideone.com/oOKjFC. For "gap"It says that it terminated with a nonzero exist code, which means that in one of my inputs, my s is larger than my t, but I don't see this happening...
 » 4 years ago, # |   0 Auto comment: topic has been updated by Whistle (previous revision, new revision, compare).
 » 4 years ago, # |   +8 I scored 55 points in fireworks, but it took me too much time.
 » 4 years ago, # |   +13 Competition data (tasks, tests, solutions) are uploaded in apio2016.orgYou can also find it in Github : https://github.com/apio-2016/apio2016-tasks
•  » » 4 years ago, # ^ |   +4 Will there be editorial?
•  » » » 4 years ago, # ^ |   0 I doubt so T.T
•  » » » » 4 years ago, # ^ |   0 when is the result gonna be published today...so excited
 » 4 years ago, # |   0 Why are the unofficial results not published yet?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 it only passed to delegation leaders.
•  » » » 4 years ago, # ^ |   0 Why is it only passed to delegation leaders, then?
•  » » » » 4 years ago, # ^ |   +5 It's the unofficial results, just for teams to check if there were any mistakes in their scores (compared to the score they received in contest).
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   -21 I just don't equate "unofficial" with "hidden", especially when part of it (cutoffs) is published/leaked and when it's even listed in the schedule.If it's supposed to be secret, this discussion wasn't supposed to exist at all. If it's not, why not publish it with a note saying "unofficial results"?UPD: Wow, all those downvotes — logic must make some people really butthurt.
•  » » » » » » 4 years ago, # ^ |   -10 I guess, delegation leaders get a list with points of their state participants only. There should be no other information regarding others' scores or medal distribution. This procedure is needed for the appeal, if the scores turn out to be somehow wrong. Personally, i think leak of medal cutoffs is not due to the unofficial results, there might as well be other sources.
•  » » » » » » » 4 years ago, # ^ |   0 Actually our delegation leader sent a list that contain all participants. If our leader have a permission to see list, it should what planned to do. So we know cutoffs due to unoffical results, BTW cutoffs aren't "leak", we can just see it.
•  » » » » » » 4 years ago, # ^ |   0 IMHO, list isn't secret, they just didn't think to publish unoffical one, BTW I don't know that's the reason.
•  » » » » » » » 4 years ago, # ^ |   +10 yeah that makes no sense at all
•  » » » » » » » 4 years ago, # ^ |   0 in 2014 and 2015 they published the unofficial results.
•  » » 4 years ago, # ^ |   0 So now that every delegation leader knows the results and medal cutoffs. Why the delay with posting official results?!
•  » » » 4 years ago, # ^ |   0 still waiting.......
 » 4 years ago, # |   +5 Official Result is available: http://apio2016.org/results/
 » 4 years ago, # | ← Rev. 3 →   +6 Results are finally out. Yay! http://apio2016.org/results/ Boat has 31 full scorers, Fireworks has 4 full scorers, Gap has 40 full scorers. (Correct me if I counted wrong)Korean top6 :Jaehyun Koo (koosaga) (100 / 26 / 100)Dongwook Hwang (Inhibitor) (100 / 26 / 100)Donghyun Kim (dh_k_9949) (100 / 26 / 49.72)Hyunsoo Kim (khsoo01) (31 / 26 / 100)Sunjay Oh (ggoh) (31 / 26 / 100)Junseo Koo (31 / 7 / 100)Also congratulations to Ultimate tonyjjw !
 » 4 years ago, # | ← Rev. 2 →   -18 I know I'm going to get downvoted to oblivion, but I really think this is unfair. Scoring 80-86.5 is much harder than scoring 87. :( I know both are bad anyway
 » 4 years ago, # |   +17 Did teams from Russia participate in APIO 2016?
•  » » 4 years ago, # ^ |   +11 By APIO rules, all contestants should participate onsite. We were not able to satisfy this condition, so participated only unofficially. Our top results are 226 from SpyCheese and josdas.