In AGC's week there's only AGC.

We will hold ABC in the next three weeks.

seriously guys? does this comment deserve so much downvote? I know people are probably annoyed with some other comments, but hating on him is not cool. I feel comments like this helpful as I tend to forget about contest and downvoting it would only make him afraid of commenting. (you don't have to reply to me as you will probably just get downvoted)

I'm stuck in queue too

Me too. I hope my submission for C will be counted.

PS: It failed T_T

if there were 2 types instead of 3 , then the solution is just sort according to A[i] — B[i] , take the max X of them as A and the rest Y of them as B
For 3 , sort According to B[i] — C[i] in descending order , now the optimal solution looks like BBABAABABABAAB|ACACACACACAACCC (a prefix consists of B and A and the suffix C and A) . Among the prefix and suffix , the problem is now for 2 coins .so this can now be done with a segtree.

Another solution. Let's choose any distribution. For each two colors, we will put in set most good move from one color to other. While there exists two colors, such that best moves are positive in sum — do this swap. Also, if there is cycle of length 3 of best moves with positive sum — so this cycle. If not — finish, we are best solution.

Correctness can be proven because it is finding MinCostMaxFlow by negative cycles cancellation. But, probably time bound is not obvious. Also, more standard MinCost algorithms can be adopted, to exploit only three colors in similar way.

PS. I think solution described by rajat1603 is much simple.

First, we think the problem that "there are X+Y+Z pairs(a[i], b[i]), we get X a[i]s and Y b[i]s, maximize sum".

There is upper bound that is "we calc c[i] = max(a[i], b[i]), sort c[i], sum X+Y c[i]s from greater".

We think "we decide offset, calc c[i] = max(a[i], b[i] + offset), sort c[i], sum X+Y c[i]s from greater — offset * (# of use b[i])", it is upper bound of Y = (# of use b[i]).

If offset = -INF, we use X+Y a[i]s. If offset = INF, we use X+Y b[i]s.

So, we can binary search with offset, and check (# of use a[i]) >= X.

Can anyone help me figure out, why this approach is wrong? Code

I sorted elements with A[i] - B[i], then in the sorted order the first X elements cannot be part of A in final solution and also last Y elements cannot be part of B in final solution.

I use similar idea for A[i] - C[i] and B[i] - C[i]. then I remove all those for whom there is single possibility left. and repeat the entire procedure till I remove all of them.

I am not sure about the exact complexity of the program but it seems to be getting finished in time for all cases.

Start with all the events and get the most popular one. Now remove that maximum and repeat until no events are left.

You can use binary search on answer as well.

It is easy to write check function for it

What did he do ?

When will be the queued submissions judged?

I felt today's problems are very easy to get wrong for whatever reason.

Jealous xD?

Editorial is available here. (There's always an editorial 1-2 minutes after contest)

I really do not understand how this solution is related with the task :D At least that you asked imam[ p[i] — k ] :D

apiad's solution is wrong as well :)

fails on

2 12

6 15

What the heck? You're checking if k=pi+pj or k=pi and k<=max(pi) o0. Why did you think it is a good idea to submit it if it can't even handle "k=1, p1=2, p2=3" xD? It would be more natural to check if k=pi-pj, I see no logic that can lead one to coming up with such a solution :P. And even more surprisingly, why did it pass xD? It is so incredibly easy to break that with small random cases.

ANIMAL, but trivial mistake your solution could be corrected with bitset Check this for further explanation http://mirror.codeforces.com/blog/entry/53168

Interesting. Two consecutive AGCs with non-original ideas.

(By saying last round, I'm referring to this task)

The idea of problem C is also used in the past more than once. https://www.hackerrank.com/contests/blackrock-codesprint/challenges/audit-sale/problem and http://mirror.codeforces.com/contest/730/problem/I (with smaller constraints but some people solved it in a faster way).

Identity we want to prove:

1D version of this identity is well known (as golf club or Christmas stocking identity) and it's combinatorial explanation is that every path going up or right (denoted as U and R) from (0,0) to (a,b) has a unique form (U + R)^*RU^* (as regular expression). I tried to generalize this idea to 2D and observed that (almost) every such path has unique form (U + R)^*RU⁺R^* (and number of such expressions is clearly our LHS). Only path that has no such form is U^bR^a what stands for this subtracted one.

Consider an eulerian cycle in the graph described in the editorial.
Each cycle consists of alternating paths in the first tree and second tree with edges joining endpoint of a path of previous tree with startpoint of path of current tree.
Now according to the method described in editorial , for each path , each of the path's nodes subtree sum either increases / decreases by 1 except the LCA of the endpoints.
Now for each node , the only time its subtree sum will change is if a path coming to this continues upward which can happen exactly once(Because each node has exactly one parent edge only)
So this prove that any node which has a path passing from it will have subtree sum as +1 or -1 and since all nodes has a degree of atleast 2 , all nodes will have atleast one path passing from it and hence we are done.