### fushar's blog

By fushar, 5 years ago, ,

Hello,

Indonesia is hosting this year's APIO 2015. The contest will take place on this weekend, May 9 2015.

We also provide a mirror contest, called Open APIO 2015, after the official contest day for everyone to participate. It will be a 5-hour virtual contest that you can start any time between Sunday, 10 May 2015, 20:00 (UTC+7) and Monday, 11 May 2015, 20:00 (UTC+7). We really encourage you to try the problems, just for fun!

Here are the details:

• Register here: https://competition.ia-toki.org/contests/18/view. Registration closes 1 hour before Open APIO 2015 ends. If you don't have account on TLX (our contest system), you will be prompted to register on TLX.
• No medals/certificates will be awarded.

The rules for Open APIO 2015 are similar to the official one:

• There will be 3 IOI-style problems.
• You can only submit at most 30 submissions for a problem.
• You will get full feedback for each submission.
• For each problem, there are several subtasks:
• For each subtask, there are points assigned to it.
• Each subtask contains several test cases.
• You get the points from that subtask if the program passes all the test cases in that subtask.
• The score of a submission is the sum of all the points that you get from completing subtasks.
• The final score for a problem is the maximum of all the submission scores for that problem.

And here are the grading environment specifications:

• OS: Ubuntu 14.04.1 LTS
• Kernel: Linux 3.13.0-36-generic #63-Ubuntu SMP Wed Sep 3 21:30:07 UTC 2014 x86_64
• CPU: Intel Xeon E5-2666 v3 2.90GHz
• Compilers:
• gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2 (flags: -O2 -lm)
• g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2 (flags: -std=c++11 -O2 -lm)
• fpc 2.6.2-8 [2014/01/22] for x86_64 (flags: -O2 -XS -Sg)
• You must print a newline ('\n') after each line in your output.

You can also discuss the problems on this thread, but please do so after Open APIO 2015 ends.

Thanks,

APIO 2015 organizers

• +68

 » 5 years ago, # |   +2 Dying of curiosity. In which countries APIO'15 have already been held?
•  » » 5 years ago, # ^ |   +23 Currently all countries registered in APIO have already finished their contest: Armenia Australia Bangladesh China Hong Kong India Indonesia Iran Israel Japan Kazakhstan Kyrgyzstan Macao Malaysia Mongolia New Zealand Philippines Singapore South Korea Sri Lanka Syria Taiwan Tajikistan Thailand Turkey Turkmenistan Vietnam
•  » » » 5 years ago, # ^ |   +5 Can we discuss problems/everything then?
•  » » » » 5 years ago, # ^ |   0 Please wait until Open APIO ends.
•  » » » » » 5 years ago, # ^ |   +43 OK, sorry. Is it possible to open access to scoreboard for official APIO participants?
•  » » » 5 years ago, # ^ |   0 Wondering why didn't Russia participate like last year..
•  » » » » 5 years ago, # ^ |   0 Maybe Russia takes part in the European Olympiad
•  » » » » » 5 years ago, # ^ |   0 They participated in APIO 2014
 » 5 years ago, # |   +4 Is there anything wrong with the grading system?After I have submitted my solution, it shows "Pending" for a long time. After that, it became "Internal Error".
•  » » 5 years ago, # ^ |   +2 Grader is up again, sorry for the inconvenience.
 » 5 years ago, # |   +24 When will you publish results?
 » 5 years ago, # |   +13 Hello everyone. I would like to ask a question. On this website (http://www.apio2015.org/schedules.html) it is written that today, there are Unofficial result — Unofficial results of this Official participants ?? Thanks in advance.
 » 5 years ago, # |   +9 Sorry for the delay of the unofficial results. We are currently in the process of compiling the results.Thanks!
•  » » 5 years ago, # ^ |   +28 Will the results be ready today?
 » 5 years ago, # |   +5 Well was i too late for the contest? (open one)
 » 5 years ago, # |   +21 Why don't we tell our own scores while waiting for the results?
•  » » 5 years ago, # ^ |   +8 Ok, I'll start. My score is 140=9+100+31
•  » » 5 years ago, # ^ |   +5 44 (0 + 36 + 8). I had correct ideas but couldn't normally implement it. In upsolving — 46 + 57 + 22 = 125
•  » » 5 years ago, # ^ |   +5 Mine is 100+100+63=263
•  » » » 5 years ago, # ^ |   +5 Highest score in Iran?
•  » » » » 5 years ago, # ^ |   0 No. Haghani, JeBeK and matrix got 300.
•  » » 5 years ago, # ^ |   0 47+56+0=103 (probably no medal)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 I got 100 + 57 + 63 = 220 points, but I didn't get to Iran's top-6, so I won't take place on official scoreboard. :(
•  » » 5 years ago, # ^ |   +5 136 = 100 + 36 + 0
•  » » 5 years ago, # ^ | ← Rev. 4 →   +8 AFAIK, top 5 of Vietnam are: kien_coi_1997 300 Alpha_purple 300 minh141198 300 dnk 263 skyvn97 234
•  » » » 5 years ago, # ^ |   +10 263 actually.
•  » » » » 5 years ago, # ^ |   0 Updated. Thanks :)
•  » » » 5 years ago, # ^ |   +5 And top 7 (we have two 6s) of Iran are: Haghani 300 JeBeK 300 matrix 300 PrinceOfPersia 263 MHR 263 AliB 231 SMAKH 231
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +8 My score is 234. And 6th pos is chipchip3412 with 220 points.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 Armenia top 6:edogrigqv2 136KARM 120Mushegh 99albertg 83Martin97 82
 » 5 years ago, # |   +48 Nice problems, I like it when the problems are more about thinking then coding.The downside is I wouldn't be surprised if there were many people tied with 300 points...
 » 5 years ago, # |   +72 I am sorry to say, but problem's quality was much lower than last 3-4 years. First of all 120 points were requiring shortest path algorithms:( and another 80 from first problem was easy dynamic programming. Also third problem had 63 points which has limits N <= 1000 or K = 1. And those 63 points was not worth it. Seriosly why just 37 points for the last subtask which is the only interesting and non-standart one?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Hint: I wrote problem B, and I forgot to increase the constraint for N to 1,000,000,000 (originally, we were planning to allow only (N+M) sqrt (N+M) solutions to pass. But, we're lenient, so we allow (N+M) sqrt (N+M) log (N+M) to pass too. But then, the constraint should have N <= 10^9).
•  » » » 5 years ago, # ^ |   0 Saddest part is, a lot of people with 100 points did not even noticed it was .
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +10 I agree! It's even sadder since some of the test cases are rather weak.(now... let's focus on the N <= 10^9 version. Can u solve it? Edit: can anyone solve it?)
•  » » » » » 23 months ago, # ^ | ← Rev. 2 →   +10 Sorry for necroposting, but can someone explain the solution for N <= 10^9 variant of the problem? I tried looking for old analysis's etc., everything gets 404. :(
•  » » » » » » 23 months ago, # ^ | ← Rev. 2 →   +3 If I recall correctly, there is nothing written about O(M1.5lg(N + M)) solution in Editorial. And now I'm also very curious about the solution too.
•  » » » 5 years ago, # ^ |   0 I think you meant , right?
•  » » » » 5 years ago, # ^ |   0 Whoops, I meant M sqrt(M) log(N+M)
 » 5 years ago, # |   +3 Really got tired of waiting for the results. Can you at least tell that will the results be up today or not ???
 » 5 years ago, # |   0 What do you think the medal ranges will be?
•  » » 5 years ago, # ^ |   +3 Either 104 or 66 for bronze, because life is full of cruel jokes :P
•  » » » 5 years ago, # ^ |   +5 Why not 79?Now guess what Alex7 's score was :D
•  » » » » 5 years ago, # ^ |   0 Because my score is the joke itself, hence my blog.
 » 5 years ago, # |   +5 AliB and SMAKH both got the 6th place in Iran, which one is gonna be in official results ?
•  » » 5 years ago, # ^ |   0 Wow, how much did they score?
•  » » » 5 years ago, # ^ |   +5 231
•  » » 5 years ago, # ^ |   0 I obviously have the same question! :) Can anyone answer please?
•  » » » 5 years ago, # ^ |   0 Oh, we both got silvers. :) Congrats AliB :)
 » 5 years ago, # | ← Rev. 3 →   0 how is the solution for the B problem?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +18 First delete doges with equal Pi in the same building, because they make no difference.For every doge with power Pi present in building Bi, add an edge from Bi to Bi + Pi with cost 1 (meaning this doge jumps 1 time to the positive direction). If there is a doge with the same power Pi in building Bi + Pi, stop adding edges for this doge (jumping further makes no sense because passing information to this new doge and having the new doge jump is the same thing). Otherwise, continue by adding edge from Bi to Bi + 2*Pi with cost 2 and check if there is a doge there with same power, and so on. Add edges similarly for jumps in the negative direction. Now just run Dijkstra's algorithm. Dijkstra's is O(E log V) and we have at most O(n sqrt(m)) edges, so complexity is O(n sqrt(m) log(n)).
•  » » » 5 years ago, # ^ |   0 thanksmy different was just the "stop adding edge" thing and it cost me TLE :/
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 Makes sense, without that the number of edges might be equal to nm (imagine a bunch of doges with power 1, for example). I assume this was the difference between the last two subtasks and the rest.
 » 5 years ago, # | ← Rev. 2 →   0 how to solve full A and C problem?
•  » » 5 years ago, # ^ |   0 C : the problem is just if K=2. if we have one fixed bridge position x, the cost for each pair bridge (x,y) with increasing y will form a curve (and my friend found that in the bottom of a curve, it is 'not a curve') so, just use ternary search for both x,y , and when left and right bound is close enough, just use brute force.
•  » » » 5 years ago, # ^ |   0 So we use ternary search for finding "fixed" bridge x first without considering second pair, then use ternary for find bridge y?How if choosing the first "fixed" is not the optimal one?
•  » » » » 5 years ago, # ^ |   +3 like this -> ternary(x){ ternary(y) }. i can't explain well, so it's my AC code http://ideone.com/UO6QOK
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 You got lucky. Your code fails, for example, on the test case in edit.I don't know if it can be fixed or not, but I'd need a proof that ternary search on x works to believe it.
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +8 Even if the dy/dx is monoton, one can create a test case where dy = 0. So ternary search is not usefull in this problem.
•  » » » » » » 5 years ago, # ^ | ← Rev. 4 →   0 i solved it in open APIO, so i am not that lucky :Xin the "real APIO", i used ternary search only for the second bridge, and i was bruteforcing the first bridge. i don't know whether it's true or not because i can't proof it, but with testcases i generated, with a same "first bridge", the cost form a curve.
•  » » » » » » » 5 years ago, # ^ |   0 Can you please share your code?
•  » » » » » » » » 5 years ago, # ^ |   0 me? i've posted the link above
•  » » » » » » » » » 5 years ago, # ^ |   0 I meant the one you used in the real contest
•  » » » » » » » » » 5 years ago, # ^ |   +6 here it is http://ideone.com/3hDpwD
•  » » » » » » 5 years ago, # ^ |   +12 In the contest, I surprised that my solution using ternary search could pass all of tests. When the score 100 was shown, I got a little shock.
•  » » » » » 2 years ago, # ^ |   0 I found a counterexample for ternary search(and sliding window solution). http://ideone.com/lF6zCS
•  » » 5 years ago, # ^ | ← Rev. 2 →   +35 C: (assuming you know how to solve K=1)Suppose our pair of bridges is (B1, B2), B1 < B2. A certain trip x -> y uses B1 if and only if B1 + B2 > x + y (proof omitted).So if you sort all trips by increasing order of x + y, the only possible ways to partition the bridges are: the prefixes of this array use B1, corresponding suffixes use B2.For each prefix, calculate optimal bridge position (using solution for K=1). For each suffix, calculate optimal bridge position. You can do it faster than calculating it from scratch for every prefix: use a data structure such as a set to be able to keep median incrementally for every prefix in logarithmic time. Then choose partition that gives you smallest total travel time and you're done. Code: link
•  » » » 5 years ago, # ^ |   0 how to get "A certain trip x -> y uses B1 if and only if B1 + B2 > x + y"?
•  » » » » 5 years ago, # ^ |   0 x,y uses B1 if and only if (x - B1) * 2 ≤ (B2 - y) * 2.which means x - B1 ≤ B2 - y, so x + y ≤ B1 + B2.(just simple math)
•  » » » 5 years ago, # ^ |   +9 That's amazing. I can't understand why you could find a such solution.
•  » » » » 5 years ago, # ^ |   +8 Of course, the solution didn't come ready -- I scribbled a bunch of bridges and homes on paint before I could see that the cost to choose a bridge for a certain trip was symmetric along the midpoint between x and y (), so I could choose which bridge to go to by taking the closest bridge to that midpoint line.From there, it's not such a big jump to sort trips by this quantity, and then you're more than halfway there.
•  » » » 5 years ago, # ^ |   0 Can you explain the idea behind your data structure?
•  » » » » 5 years ago, # ^ |   0 It's quite easy to add a number to a sequence and update the median using C++ set. Suppose that all numbers are pairwise distinct. Maintain a set, an iterator points at the current median and a variable to count the number of value smaller than the median. Whenever adding a number to the set, update the counter and move the iterator if necessary. Take into account that valid iterator remains valid after insert operations.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +14 Another solution for C.Let me denote opt(i) as best second position of bridge if first one is on i. I claim that opt(i) ≤ opt(i + 1). After then, while using divide and conquer optimization to calculate the total distances i am using 3 fenwick trees. Overall complexity is O(N(logN)2).Here is the solution for more details : link
 » 5 years ago, # | ← Rev. 2 →   0 7 contestants from China got 300 :pAlthough I got 100+100+63 which seems a good score, the competition is tooooooo tough :(((
•  » » 5 years ago, # ^ |   +5 Lol, I feel sorry for the organizers compiling the results is impossible
•  » » 5 years ago, # ^ |   -8 Actually,there are about ten.
 » 5 years ago, # |   +8 The unofficial results can be downloaded on the contest dashboard. Sorry for the delay.Also, we apologize for the weak test data. We figured it out in the middle of the contest, and it is unfair if we add new test cases.Thanks!
•  » » 5 years ago, # ^ |   +8 Thank you very much :)And thank you for not changing the test cases. I played a bit with some unproved solutions (which later, after the contest, turned out to be wrong) and ran out of time and could not implement the correct ones that were in my mind. I was afraid that I will lose those points (9 points :D) which I got using unproved solutions.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +18 Gold only for full scores... Never imagined such contest :pIf the test data were stronger there might not be so many full scores and I might get a chance to get in international ranking :p
•  » » 5 years ago, # ^ |   +5 Yeah, now I understand why it took so long to publish the (unofficial) results.
 » 5 years ago, # |   -11 What is the solution for Problem 1? It seemed like dynamic programming. Can someone share their code?
•  » » 5 years ago, # ^ |   +11 long long ans = (1LL << 62) - 1; for (int bit = 61; bit >= 0; bit--) { if (check(ans - (1LL << bit))) { ans -= (1LL << bit); } } cout << ans; check(mask) — returns true if we can divide our array into groups so that sum in each group is submask of mask. For first 3 subtasks where A >= 1 (A and B is number of groups) we can write DP[LEN][GROUPS] — can we divide first LEN elements into GROUPS groups. Total complexity will be O(N^3 * 64).For last one, where A = 1 we can write DP[LEN] — minimal number of groups so that we can divide first LEN elements. Complexity is O(N^2 * 64).
•  » » » 4 years ago, # ^ |   -13 Sorry for necroposting, but can you provide your code?
•  » » » » 4 years ago, # ^ |   0 Nope, already deleted it.
•  » » » » 4 years ago, # ^ |   0 Private message is a perfect way to do this.
 » 5 years ago, # | ← Rev. 2 →   0 What is the intended solution for problem B with extension N=$10^9$? Can't get any idea for sublinear complexity on N.
 » 5 years ago, # | ← Rev. 3 →   +11 How can I access problems and the ranking list? I've registered using the above link, but it doesn't show anything when I log in.
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 Here's the problemset in Turkish : https://competition.ia-toki.org/contests/23/announcements/download/apio2015_tr.pdf Here's the ranking list : https://competition.ia-toki.org/contests/23/announcements/download/APIO2015UnofficialResults.pdf I'm not sure about it will work.
 » 5 years ago, # |   +16 So when will official result be published? Or we will use unofficial result as official result?
•  » » 5 years ago, # ^ |   0 Official results have been announced to country leaders. We will be posting it on the website soon. Thanks!