Currently all countries registered in APIO have already finished their contest:

1. Armenia
2. Australia
3. Bangladesh
4. China
5. Hong Kong
6. India
7. Indonesia
8. Iran
9. Israel
10. Japan
11. Kazakhstan
12. Kyrgyzstan
13. Macao
14. Malaysia
15. Mongolia
16. New Zealand
17. Philippines
18. Singapore
19. South Korea
20. Sri Lanka
21. Syria
22. Taiwan
23. Tajikistan
24. Thailand
25. Turkey
26. Turkmenistan
27. Vietnam

Grader is up again, sorry for the inconvenience.

Will the results be ready today?

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

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:

• kien_coi_1997 300
• toilanvd_HSGS 300
• minh141198 300
• dnk 263
• I_love_tigersugar 234

Armenia top 6:

edogrigqv2 136

KARM 120

MyLeg 99

_LeMur_ 83

albertg 83

Martin97 82

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).

Either 104 or 66 for bronze, because life is full of cruel jokes :P

Wow, how much did they score?

I obviously have the same question! :) Can anyone answer please?

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)).

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.

C: (assuming you know how to solve K=1)

Suppose our pair of bridges is (B₁, B₂), B₁ < B₂.

A certain trip x -> y uses B₁ if and only if B₁ + B₂ > 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 B₁, corresponding suffixes use B₂.

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

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)²).

Here is the solution for more details : link

Lol, I feel sorry for the organizers compiling the results is impossible

Actually,there are about ten.

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.

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).

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.

Official results have been announced to country leaders. We will be posting it on the website soon. Thanks!