Codeforces Round #666 — Editorial

Revision en9, by DatVu, 2020-09-01 17:04:27

We hoped you enjoyed the problems. We apologize for the late editorial. Hopefully you were still able to enjoy our contest.

Anyway, here are the tutorials for each of the problems:

1397A - Жонглирование буквами

If the total number of occurrences of some character $$$c$$$ is not a multiple of $$$n$$$, then it is impossible to make all $$$n$$$ strings equal — because then it is impossible for all $$$n$$$ strings to have the same number of $$$c$$$.

On the other hand, if the total number of occurrences of every character $$$c$$$ is a multiple of $$$n$$$, then it is always possible to make all $$$n$$$ strings equal. To achieve this, for every character $$$c$$$ we move exactly ((the total number of occurrences of $$$c$$$) $$$/$$$ $$$n$$$) characters $$$c$$$ to the end of each string, and by the end we will have all $$$n$$$ strings equal each other.

We can easily check if the condition satisfies by counting the total number of occurrences of each character $$$c$$$ and check its divisibility by $$$n$$$. The final complexity is $$$O(S \cdot 26)$$$ or $$$O(S)$$$ where $$$S$$$ is the sum of lengths of all strings.

C++ solution
Python solution

1397B - Степенная последовательность

First of all, the optimal way to reorder is to sort $$$a$$$ in non-decreasing order.

Proof

From now on, we assume $$$a$$$ is sorted in non-decreasing order.

Denote $$$a_{max} = a_{n - 1}$$$ as the maximum value in $$$a$$$, $$$f(x) = \sum{\lvert a_i - x^i \rvert}$$$ as the minimum cost to transform $$$a$$$ into $$${x^0, x^1, \cdots, x^{n-1}}$$$, and $$$c$$$ as the value where $$$f(c)$$$ is minimum.

Note that $$$c^{n - 1} - a_{max} \le f(c) \le f(1)$$$, which implies $$$c^{n - 1} \le f(1) + a_{max}$$$.

We enumerate $$$x$$$ from $$$1, 2, 3, \dots$$$ until $$$x^{n - 1}$$$ exceeds $$$f(1) + a_{max}$$$, calculate $$$f(x)$$$ in $$$O(n)$$$, and the final answer is the minimum among all calculated values. The final complexity is $$$O(n \cdot max(x))$$$.

But why doesn't this get TLE? Because $$$f(1) = \sum{(a_i - 1)} < a_{max} \cdot n \le 10^9 \cdot n$$$, thus $$$x^{n - 1} \le f(1) + a_{max} \le 10^9 \cdot (n + 1)$$$. When $$$n = 3, 4, 5, 6$$$, $$$max(x)$$$ does not exceed $$$63245, 1709, 278, 93$$$ respectively; so we can see that $$$O(n \cdot max(x))$$$ comfortably fits in the time limit.

C++ solution
Python solution

1396A - Кратные длине

  • If $$$n = 1$$$
solution
  • Else
solution

1396B - Каменная игра

Let us denote $$$S$$$ as the current total number of stones.

Consider the following cases:

Case A: There is a pile that has more than $$$\lfloor \frac{S}{2} \rfloor$$$ stones.

The first player (T) can always choose from this pile, thus he (T) is the winner.

Case B: Every pile has at most $$$\lfloor \frac{S}{2} \rfloor$$$ stones, and $$$S$$$ is even.

It can be proven that the second player (HL) always wins.

Proof 1
Proof 2

Case C: Every pile has at most $$$\lfloor \frac{S}{2} \rfloor$$$ stones, and $$$S$$$ is odd.

The first player (T) can choose from any pile, and we arrive back at case B where the next player to move loses.

So the first player (T) wins if and only if there is a pile that has more than $$$\lfloor \frac{S}{2} \rfloor$$$ stones or $$$S$$$ is odd. This can be easily checked in $$$O(n)$$$.

C++ solution
Python solution

1396C - Monster Invaders

In this problem, it is useful to note that when the boss only has $$$1$$$ hp left, just use the pistol because it has the least reloading time. So there are 3 strategies we will use when playing at stage $$$i$$$ $$$(1 \le i \le n)$$$:

  • Take $$$a_i$$$ pistol shots to kill first $$$a_i$$$ monsters and shoot the boss with the AWP.
  • Take $$$a_i + 1$$$ pistol shots and move back to this stage later to take another pistol shot to finish the boss.
  • Use the laser gun and move back to this stage later to kill the boss with a pistol shot.

Observation: We will always finish the game at stage $$$n$$$ or $$$n - 1$$$. Considering we are at stage $$$i$$$ $$$(i \le n - 1)$$$ and the boss at both stage $$$i$$$ stage $$$i - 1$$$ has $$$1$$$ hp left, we can spend $$$2 * d$$$ time to finish both these stages instead of going back later, which costs us exactly the same.

Therefore, we will calculate $$$dp(i,0/1)$$$ as the minimum time to finish first $$$a_i - 1$$$ stages and 0/1 is the remaining hp of the boss at stage i. The transitions are easy to figure out by using 3 strategies as above. The only thing we should note is that we can actually finish the game at stage $$$n - 1$$$ by instantly kill the boss at stage $$$n$$$ with the AWP so we don't have to go back to this level later.

Answer to the problem is $$$dp(n, 0)$$$. Time complexity: $$$O(n)$$$.

C++ solution
Tags #codeforces, #666, #editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en22 English DatVu 2020-09-04 11:28:25 0 (published)
en21 English DatVu 2020-09-04 11:27:49 4 (saved to drafts)
en20 English atoiz 2020-09-02 09:42:21 0 (published)
en19 English atoiz 2020-09-02 09:37:28 523 Tiny change: 'y \rvert\}, we have ' -> 'y \rvert\}$, we have ' (saved to drafts)
en18 English DatVu 2020-09-01 21:04:41 0 (published)
en17 English JettyOller 2020-09-01 21:03:17 83
en16 English JettyOller 2020-09-01 21:02:08 155
en15 English JettyOller 2020-09-01 21:00:46 5279
en14 English JettyOller 2020-09-01 19:56:06 252
en13 English DatVu 2020-09-01 19:37:31 24 Tiny change: 'oiler>\n\n###[problem:1396E]\n\n[tutor' -> 'oiler>\n\n[tutor'
en12 English DatVu 2020-09-01 19:36:33 4004
en11 English DatVu 2020-09-01 17:23:07 1430
en10 English DatVu 2020-09-01 17:05:18 25
en9 English DatVu 2020-09-01 17:04:27 133 Tiny change: ' contest. Anyway, he' -> ' contest. \n\nAnyway, he'
en8 English DatVu 2020-09-01 16:59:07 2 Tiny change: 'hot.\n\n***Observation:*** We will' -> 'hot.\n\n**Observation:** We will'
en7 English atoiz 2020-09-01 08:24:15 11
en6 English atoiz 2020-09-01 08:18:54 299 Some random description
en5 English JettyOller 2020-09-01 06:46:15 32
en4 English DatVu 2020-08-31 19:12:54 11199 Not sure what happen with D1B, fix plz
en3 English JettyOller 2020-08-31 17:41:40 46
en2 English JettyOller 2020-08-31 17:37:20 412 Tiny change: 'smth here.' -> 'smth here.\n\n[problem:1396A]\n- If $N = 1$'
en1 English DatVu 2020-08-31 17:08:18 52 Initial revision (saved to drafts)