How drastically does problem F change if the game allows Monocarp to buy armor with a level greater than $$$n$$$ and weapons with a level greater than $$$m$$$? While it reduces the maximum number of hours needed to the ballpark of $$$O(\log(nm)),$$$ it also eliminates the clause that a point $$$(x,y)$$$ is always better than a point $$$(x', y')$$$ if $$$x' \leq x$$$ and $$$y' \leq y,$$$ requiring some degree of strategic planning.

Here is a slightly different approach for problem G which I think is easier. (Sorry if my explanation is not good.) It would seem that many other people have this approach too.

First, let's ask ourselves, given an array, how can we find the total sum of distances between all pairs of equal elements? For each element, we will need to add to the answer the sum of absolute values between each pair of indexes where it exists. This is a very well known problem, and can be easily understood by looking at an example.

Let's say an element exists at the indices $$$[1, 4, 5, 6, 8]$$$. Then, we will need to add $$$(4-1)+(5-1)+(6-1)+(8-1)+(5-4)+(6-4)+(8-4)+(6-5)+(8-5)+(8-6)$$$ to the answer. Overall, 1 has been subtracted 4 times, 4 has been subtracted twice, 5 does not contribute towards the sum, 6 is added twice, and 8 is added 4 times. So we will add to the sum $$$(-4)*1+(-2)*4+(0)*5+(2)*6+(4)*8$$$. In general, for a sorted array $$$[p_1, p_2, \dots, p_x]$$$, we will add to the answer $$$p_1*(1-x)+p_2*(3-x)+p_3*(5-x)+...+p_x*(x-1)$$$. We can think of this as assigning multiplying each index by a coefficient and finding the total sum of indexes, such that the coefficients assigned to indexes with the same element are a $$$[1-x, 3-x, \dots, x-1]$$$ in ascending order.

We can now move on to maximising the answer. We will generate a coefficient array. For each $$$c_i$$$, we will add the elements $$$[1-c_i, 3-c_i, \dots, c_i-1]$$$ to the coefficient array. Then, we want to obtain a permutation of this coefficient array $$$[p_1, p_2, \dots, p_n]$$$ such that $$$\sum_{i=1}^{n} ip_i$$$ is maximised. By the rearrangement inequality, this sum is maximised when $$$p$$$ is sorted, and it is easy to see that such a permutation is possible.

For more clarity, consider the case where $$$c = [3, 3, 2]$$$. We will generate the coefficient array $$$[-2, 0, 2]+[-2, 0, 2]+[-1, 1]=[-2, -2, -1, 0, 0, 1, 2, 2]$$$. Then the maximum answer will be $$$(-2)*0+(-2)*1+(-1)*2+(0)*3+(0)*4+(1)*5+(2)*6+(2)*7=27$$$, and this is achievable for example by choosing $$$a=[1, 2, 3, 1, 2, 3, 1, 2]$$$.

Now, how do we do this fast? Instead of actually generating the coefficient array, we will simply create a frequency map storing how many times each element exists in the coefficient array. We can create this map quickly using a difference array (or you can visualise this as a sweepline). We will then iterate through this map in ascending order. For each element $$$e$$$ which occurs $$$num$$$ times in the coefficient array, we will assign $$$e$$$ as the coefficient of the $$$num$$$ lowest indexes which we haven't assigned yet, and increment our answer by ($$$e *$$$ sum of chosen indexes). Remember that of the distinct elements in $$$a$$$, exactly $$$num$$$ of these elements will have contributed $$$e$$$ to the coefficient array, so these indexes will correspond to some permutation of these $$$num$$$ elements in $$$a$$$. We will therefore multiply the number of possible arrays by $$$num!$$$, as this is the number of permutation of these $$$num$$$ elements in $$$a$$$.

See https://codeforces.me/contest/1612/submission/136599117 for implementation details. If an array is used instead of a map, the overall complexity of this algorithm is $$$O(m+max(c_i))$$$.

can't understand solution of E since "iterate the number of message".

C can also be solved by calculating root of the quadratic equation x(x+1)/2 — c = 0. Not sure if this solution is more optimal though

can pls anyone explian me A problem solution

For problem E, I did the ternary search and got AC. But I have no idea if it can be proved XD. I just assumed that the expectation of number of messages that Monocarp should pin has a maximum, and then checked the expectation in ternary search. somehow it worked (I failed at test 167. turns out it could be optimum when you just only pin one message, and then I fixed it) my code: 136675859

For those who are struggling like me in problem E, why don't we need for t > 20, here is why
For simplicity assume that k[i] <= 2, and the sorted list for each message is something like this a > b > c
All we have to prove that (a / 2 + b / 2) > (a / 3 + b / 3 + c / 3)
We know that a > b > c, so the average of a and b = (a + b) / 2
and ((a + b) / 2) > b as a > b
so ((a + b) / 2) > c as b > c
=> 3 * ((a + b) / 2) — 2 * ((a + b) / 2) > c
=> 3 * ((a + b) / 2) > 2 * ((a + b) 2 ) + c
=> 3 * ((a + b) / 2) > a + b + c
=> ((a + b) / 2) > (a + b + c) / 3
=> (a / 2 + b / 2) > (a / 3 + b / 3 + c / 3)
So many might ask so why is it not the case when t <= 20, because it contains non-linearity as well as sorted messages list might change as the t increases but its not the case when t > 20, all the value decreases when t > 20

in C you can find answer in O(1) by finding the smallest integer number exceeding sum of emojes: we know that sum from 1 to n is equal to n(n+1)/2, so if k(k+1)/2 > x: we just solve this quadradic equation, if k(k+1)/2 + (k-1)k/2 > x we need to use backwards sum formula: n(k+1) - n(n+1)/2. for n=1, 2, 3, ... it gives k, k+(k-1), k+(k-1)+(k-2), ... and here we need to solve this quadric equation: n(k+1) - n(n+1)/2 >= x-k. But in large numbers we get big error, more than 0.5, so we need to check a few surrounding numbers

For Problem D:

No, you don't have to bother:

long long cnt = max(1ll, (a - max(x, b)) / (2 * b));

Remember how GCD works?

int64 gcd(int64 a, int64 b){
    return b == 1? a : gcd (b, a%b);
}

We use a%b to speed up a-b-b-b.....

So we can do the same thing here!

Assume a >= b, and let's call a%b the left-over part,

If x can be represented by using a and b

Since we can only get a, a-b, a-b-b, all the way down to the left-over part (a%b)

Then x- the left-over part should be able to divided up by b,

In other word, (x - a % b) % b == 0.

So we can judge if we can get x by modding GCD:

If (x - a % b) % b == 0 then that's a big YES, otherwise continue doing GCD.

And here's my code 136836057

Hello,

I did not participate in the contest, but i have some solution implemented for D, an observation is that you always pick max(a,b) then subtract max(a,b) — min(a,b) * K where K is max(a,b)/min(a,b), solution exists if (max(a,b)-x)%min(a,b)==0. Note that if you got min(a,b) as zero or max(a,b) < x then you can't find the solution.

shuffle(cert.begin(), cert.end(), mt19937(time(NULL)));

Why does the editorial soln of Question E shuffles array cert?

shuffle(cert.begin(), cert.end(), mt19937(time(NULL)));

Why editorial soln of E shuffles cert array ?

It can be proven that this algorithm yields all possible integers that are obtainable by any sequence of the operations from the problem statement (either in a or in b).

Proof?

For the D problem, if someone is confused with the conditions, only these conditions were sufficient for an AC solution.

bool get(long long a, long long b, long long x)
{
    if (a == x || b == x)
        return true;
    if (a < b)
        swap(a, b);
    if (x > max(a, b) || a == 0 || b == 0)
        return false;
    long long cnt = max(1ll, (a - max(x, b)) / (b));
    return get(a - b * cnt, b, x);
}

This version skips redundant operations and efficiently finds whether x is reachable.