Codeforces Round #666 — Editorial

Правка en17, от JettyOller, 2020-09-01 21:03:17

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
Теги #codeforces, #666, #editorial

История

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