### BledDest's blog

By BledDest, 14 months ago, translation, 1612A - Distance

Idea: BledDest, preparation: BledDest

Tutorial
Solution (BledDest)

1612B - Special Permutation

Idea: MikeMirzayanov, preparation: MikeMirzayanov

Tutorial
Solution (BledDest)

1612C - Chat Ban

Idea: vovuh, preparation: vovuh

Tutorial
Solution (vovuh)

1612D - X-Magic Pair

Idea: vovuh, preparation: vovuh

Tutorial
Solution (vovuh)

1612E - Messages

Idea: BledDest, preparation: BledDest

Tutorial
Solution (BledDest)

1612F - Armor and Weapons

Idea: BledDest, preparation: BledDest

Tutorial
Solution (BledDest)

1612G - Max Sum Array

Tutorial  Comments (24)
| Write comment?
 » •  » » The root of cf is math.
 » 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.
•  » » i misread the problem and tried to solve this version for an hour lmao
 » 14 months ago, # | ← Rev. 3 →   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.com/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))$.
•  » » Elegant !!!
 » can't understand solution of E since "iterate the number of message".
•  » » You can check my commented solution it explains the idea as well as the code. My solution
 » 14 months ago, # | ← Rev. 5 →   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
•  » » Its giving wrong answer for my submission, maybe because I am using the sqrt() function. So without using it is there any other method to calculate square root optimally?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   You can check my submission as it also uses sqrt, it passed tests. You can have rounding problems so you have check root +-1.
•  » » » yes — use sqrtl() and ceill() instead of sqrt() and ceil() — the first two uses long double which will not lose precision for integers up to 9*10^18 while the second two uses double which loses precision for integers above 2*10^15
 » 14 months ago, # | ← Rev. 2 →   can pls anyone explian me A problem solution
•  » » 14 months ago, # ^ | ← Rev. 2 →   You can almost brute force all possible points $C$, since we know that $0 \le C_x, C_y \le 100$. However, trying all $101^2$ points won't work. We notice that $C_x + C_y = \frac{|x| + |y|}{2},$ so if we fix $C_x$ we can find $C_y$. That is, brute force all possible points $C_x \in [0, 100],$ find the corresponding $C_y = \frac{|x| + |y|}{2} - C_x$ to check if that point is valid.EDIT: Actually, trying all possible points will work; I overcomplicated
•  » » » Why wouldn't trying all points work? It takes around 3 * 10^7 operations which is perfectly fine.
 » 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
•  » » I'm an idiot XD. now I read the tutorial. Don't reply, ignore me
•  » » » reply quq
 » 14 months ago, # | ← Rev. 2 →   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
•  » » solving quadratic equation in O(sqrt(n)) i think
 » 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 bSince 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
•  » » I believe this line in the model solution is left from the previous version of the problem, where we asked for the minimum number of moves to obtain $x$.
 » shuffle(cert.begin(), cert.end(), mt19937(time(NULL)));Why editorial soln of E shuffles cert array ?