Codeforces Round #666 — Editorial

Revision en18, by DatVu, 2020-09-01 21:04:41

We hoped you find our problems interesting. 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 - Juggling Letters

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 - Power Sequence

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 - Multiples of Length

In this problem, the answer is rather simple. Here is one possible solution to this task.

Solution for n = 1
Solution for n != 1
C++ solution
Python solution

1396B - Stoned Game

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
Tutorial is loading...
C++ solution
Tutorial is loading...
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)