BledDest's blog

Educational Codeforces Round 117 — Editorial
By BledDest, 3 years ago, translation, In English

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

Idea: adedalic, preparation: adedalic

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +87
  • Vote: I do not like it

Comments Comments (28)
| Write comment?
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +61 Vote: I do not like it

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.net/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))$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can check my submission as it also uses sqrt, it passed tests. You can have rounding problems so you have check root +-1.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      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

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can pls anyone explian me A problem solution

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why wouldn't trying all points work? It takes around 3 * 10^7 operations which is perfectly fine.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Why editorial soln of E shuffles cert array ?

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
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?

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    agree.also I don't understand why do we divide by 2 here : cnt=max(1,⌊a−max(b,x)2b⌋) I solved it using this : y=max((a-x),b)/b;

    → Reply