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
Auto comment: topic has been updated by Whistle (previous revision, new revision, compare).
Can I participate ? I'm not in Informatics Olympiad
.
Really liked A :)
Liked cause you saw it before?
The problems in the practice session are from BOI2014.
http://www.boi2014.lmio.lt/
https://github.com/boi-2014/tasks
gl & hf;
30 submission max allowed on each problem, and max one submission in 5 minutes. Isn't that too much? :/
In worst case you will submit 60 codes :/ (the sum of allowed submissions is 90 !) .
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
No not for each probelm .
in practice session I tried to submit 2 codes in one minute
one for each problem , and it was worked.
Please don't share problems/codes/solutions/scores here or anywhere else until the end of the contest that will make the contest unfair.
How much points are needed to get silver?
I got 31-7-100.
I hope I get at least a bronze. :|
how did you solve the last one?
Hint : Pigeonhole Principle
can't believe that thing didn't came into my mind. btw, i got 58-26-52.
I still can't believe I missed P2 sub 2 just because I misread the constraints -_-
Me, too T_T.
I got 100 — 26 — 30,38. I can't get any points on the second subtask of the last problem.
How did you get P1? My 31 pt solution is some weird fenwick tree dp.
I used dp with combinatorics.
Solution O(N ^ 3) worked :3 .
What are the top 5 scores in China and Malaysia?
China : 300? (just a logical guess)
Malaysia : Me, 31-7-100 = 138
how do you get beyond subtask 2 of fireworks?
Let me guess you got 100+26+100 ?
Nope. 31+26+100=157. I am bad at math so I couldn't solve boat.
Can you explain your solution for the third problem ?
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.
Thanks.
My teammate got 100 — 26 — 100. minh141198
Cool
He got a perfect score last year :v .
Looks you are very curious. SO what's your score?
31+7+30.38 :/.
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.)
easy one : MY GUESS IS WRONG. countercase :
answer is 300 -> 2, while all leaf have 299 / 301 depth. It's even hard to get 255..
(Thanks gs12117 for informing this!)
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.
I still don't understand what are you storing in each dp state? How does the function look like?
Please elaborate further :)
Thanks for your reply :) I will read it after thinking more.
(seems like you participated unofficially, right?)
Cool, looks like q2 was actually the hard question. Funny that was the only question I solved.
My score: 9-100-30
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.
Can you explain what you did in bigger detail ? How did you calculate the cost function efficiently ?
How do you merge 2 cost functions?
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.
By using this algorithm to propagate the function up the tree, we can easily find the optimum at the root.
How to solve 2nd subtask?
Dp[node][l]=the minimum cost for changing lengths in the subtree of v such that the distance to all leafs is l .
How to calculate it? :)
Dp[v][l]=sigma(u) {min(k){dp[u][k]+|l-k|} } u is a child of v and k is some length .
Did anybody score 100 in fireworks?
Did anyone get more than 26?
How much did you score? :D
100+7+70
How in the world did you score 70 in problem 3 ? Did you just solve subtask 2 or what @@
Subtask 2 has a scoring formula
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
I scored 9 + 26 + 48.18 :(
What do you think will be the medals limits?
I scored 9 + 7 + 45.5 :/
I think the bronze limit will be about 94 .
100 or above — bronze 150 or above — silver 200 or above — gold throwing random guesses :P
I think it will be 68.39 for bronze.
when does apio deliver medals?
or do they give medals at all?
They usually give medal certificates to country leaders in IOI.
medals? or just certificates telling that they won bronze/silver/gold?
Just certificates.
Why don't they give medals anyway?!
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.
I was thinking of getting a nice medal and then i saw this comment :(
Примерно с 84 — бронза, с 138 — серебро, с 215 — золото
Full solution for subtask 2 P3 :
Step 1 : Find a_1 and a_n
Query(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.
Where are the unofficial results ?
Unofficial results are only passed to delegation leaders.
Unofficial Medal Cutoffs :
Bronze : 87
Silver : 138
Gold : 215.04
How do you know that ?
He hacked the APIO website and got the csv sheet with the results :D
Being 3 points off from Bronze.
WorstBest feeling in the world!Being 3 points off from Silver. Worst Best feeling in the world!
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...
Auto comment: topic has been updated by Whistle (previous revision, new revision, compare).
I scored 55 points in fireworks, but it took me too much time.
Competition data (tasks, tests, solutions) are uploaded in apio2016.org
You can also find it in Github : https://github.com/apio-2016/apio2016-tasks
Will there be editorial?
I doubt so T.T
when is the result gonna be published today...so excited
Why are the unofficial results not published yet?
it only passed to delegation leaders.
Why is it only passed to delegation leaders, then?
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).
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.
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.
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.
IMHO, list isn't secret, they just didn't think to publish unoffical one, BTW I don't know that's the reason.
yeah that makes no sense at all
in 2014 and 2015 they published the unofficial results.
So now that every delegation leader knows the results and medal cutoffs. Why the delay with posting official results?!
still waiting.......
Official Result is available: http://apio2016.org/results/
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 (ko_osaga) (100 / 26 / 100)
Dongwook Hwang (Inhibitor) (100 / 26 / 100)
Donghyun Kim (kdh9949) (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 !
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
Did teams from Russia participate in APIO 2016?
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.