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
Dying of curiosity. In which countries APIO'15 have already been held?
Currently all countries registered in APIO have already finished their contest:
Can we discuss problems/everything then?
Please wait until Open APIO ends.
OK, sorry. Is it possible to open access to scoreboard for official APIO participants?
Wondering why didn't Russia participate like last year..
Maybe Russia takes part in the European Olympiad
They participated in APIO 2014
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".
Grader is up again, sorry for the inconvenience.
When will you publish results?
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.
Sorry for the delay of the unofficial results. We are currently in the process of compiling the results.
Thanks!
Will the results be ready today?
Well was i too late for the contest? (open one)
Why don't we tell our own scores while waiting for the results?
Ok, I'll start. My score is 140=9+100+31
44 (0 + 36 + 8). I had correct ideas but couldn't normally implement it. In upsolving — 46 + 57 + 22 = 125
Mine is 100+100+63=263
Highest score in Iran?
No. Haghani, JeBeK and matrix got 300.
47+56+0=103 (probably no medal)
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. :(
136 = 100 + 36 + 0
AFAIK, top 5 of Vietnam are:
263 actually.
Updated. Thanks :)
And top 7 (we have two 6s) of Iran are:
My score is 234. And 6th pos is chipchip3412 with 220 points.
Armenia top 6:
edogrigqv2 136
KARM 120
MyLeg 99
_LeMur_ 83
albertg 83
Martin97 82
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...
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?
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).
Saddest part is, a lot of people with 100 points did not even noticed it was .
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?)
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. :(
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.
I think you meant , right?
Whoops, I meant M sqrt(M) log(N+M)
Really got tired of waiting for the results.
Can you at least tell that will the results be up today or not ???
What do you think the medal ranges will be?
Either 104 or 66 for bronze, because life is full of cruel jokes :P
Why not 79?
Now guess what Alex7 's score was :D
Because my score is the joke itself, hence my blog.
LiTi and SMAKH both got the 6th place in Iran, which one is gonna be in official results ?
Wow, how much did they score?
231
I obviously have the same question! :) Can anyone answer please?
Oh, we both got silvers. :) Congrats LiTi :)
how is the solution for the B problem?
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)).
thanks
my different was just the "stop adding edge" thing and it cost me TLE :/
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.
where does the upper limit n sqrt(m) come from? can you explain it a bit more?
I'm not sure I remember the problem correctly, but consider all doges with power P. Each building only gets at most two edges from each direction (since the others would stop before getting there), so the total number of edges is O(N).
An individual doge with power P also contributes at most O(N/Pi) edges.
So for doges with power < sqrt(N), there are sqrt(N) different powers so they contribute at most O(N sqrt N), and for doges with power > sqrt(N), each of them contributes at most sqrt(N) so they contribute at most O(M sqrt N) in total.
Thanks, it's clear now.
how to solve full A and C problem?
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.
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?
like this -> ternary(x){ ternary(y) }. i can't explain well, so it's my AC code http://ideone.com/UO6QOK
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.
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.
i solved it in open APIO, so i am not that lucky :X
in 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.
Can you please share your code?
me? i've posted the link above
I meant the one you used in the real contest
here it is http://ideone.com/3hDpwD
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.
I found a counterexample for ternary search(and sliding window solution). http://ideone.com/lF6zCS
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
how to get "A certain trip x -> y uses B1 if and only if B1 + B2 > x + y"?
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)
That's amazing. I can't understand why you could find a such solution.
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.
Can you explain the idea behind your data structure?
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.
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
7 contestants from China got 300 :p
Although I got 100+100+63 which seems a good score, the competition is tooooooo tough :(((
Lol, I feel sorry for the organizers compiling the results is impossible
Actually,there are about ten.
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!
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.
Gold only for full scores...
Never imagined such contest :p
If 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
Yeah, now I understand why it took so long to publish the (unofficial) results.
What is the solution for Problem 1? It seemed like dynamic programming. Can someone share their code?
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).
Sorry for necroposting, but can you provide your code?
Nope, already deleted it.
Private message is a perfect way to do this.
What is the intended solution for problem B with extension N=$10^9$? Can't get any idea for sublinear complexity on N.
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.
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.
So when will official result be published? Or we will use unofficial result as official result?
Official results have been announced to country leaders. We will be posting it on the website soon. Thanks!