Блог пользователя DatVu

Автор DatVu, история, 4 года назад, По-английски

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 $$$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 Round 666 (Div. 1)
Разбор задач Codeforces Round 666 (Div. 2)
  • Проголосовать: нравится
  • +112
  • Проголосовать: не нравится