Unofficial Editorial for Codeforces Round 666 (Currently only Div.2 A-E)

Правка en1, от lucifer1004, 2020-08-31 13:46:20

There is also a Chinese version.

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

Just count the number of every letter, and check whether every number can be divided by $$$N$$$.

Code (Python 3)

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

First sort the array in ascending order, then enumerate $$$c$$$. We can constrain the range of $$$c$$$ by $$$c^{n-1}<=2\sum a_i$$$, otherwise, we can simply change all $$$a_i$$$ to $$$1$$$ and that will cost less.

Code (Python 3)

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

We can make use of the fact that $$$N-1$$$ and $$$N$$$ are coprime. First we operate on $$$[1,N-1]$$$ whose length is $$$N-1$$$, then we operate on $$$[2,N]$$$ whose length is also $$$N-1$$$. After two operations, we can make all numbers divided by $$$N$$$. Finally, we operate on $$$[1,N]$$$ whose length is $$$N$$$, and we can just add $$$-a_i$$$ to each $$$a_i$$$ ($$$a_i$$$ may have changed after the previous operations).

Note that $$$N=1$$$ is an edge case.

Code (C++)

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

If $$$\max a_i>\sum a_i - \max a_i$$$, then T can always win. He can just take stones from the largest pile, while HL can only take from the rest piles. Since $$$\max a_i>\sum a_i - \max a_i$$$, there is definitely a time when HL has no stone to take after T takes a stone.

Otherwise, $$$\max a_i\leq\sum a_i - \max a_i$$$, then both players can avoid $$$\max a_i>\sum a_i - \max a_i$$$ with the following strategy:

  • If the maximum pile is currently available, just take from it
  • Otherwise, it means that the maximum pile has just been taken, so we have $$$\max a_i\leq\sum a_i - \max a_i - 1$$$. No matter which pile we take a stone from, we will have $$$\max a_i\leq\sum a_i - \max a_i$$$ afterwards.

So the winner depends on the parity of stones. If the total number of stones is odd, then T wins, otherwise HL wins.

Code (C++)

1396C - Monster Invaders

First, let's consider one level. We have two ways to clear all monsters:

  • Kill the boss with one shot. We use pistol to kill all normal monsters, then use AWP to kill the boss. The total time cost is $$$p[i]=a[i]\cdot r_1+r_3$$$.
  • Kill the boss with two shots. We can use pistol to kill all normal monsters, and then attack the boss once. Or we can use the laser gun to kill all normal monsters while damaging the boss at the same time. Then we are forced to leave. The next time we reach this level, we use pistol again to kill the boss. If we only consider the time spent on reloading, the total time cost is $$$q[i]=\min((a[i]+1)\cdot r_1, r_2)+r_1$$$.

Now we can consider the general route. Let's reflect on where we shall end.

image for 1396C

Supposing we end at $$$3$$$, our best choice should be like the figure above. That is to say, we first come to $$$3$$$, then we go to the other end and go back to $$$3$$$. Otherwise we will spend extra time on teleportation.

So we can divide the total time cost into three parts. The time cost of $$$[1,2]$$$, the time cost of $$$[3,8]$$$ and the time cost of moving from $$$2$$$ to $$$3$$$ which is $$$d$$$.

Let $$$L[i]$$$ be the minimal time to clear $$$[1,i]$$$ and stop at level $$$i$$$, $$$R[i]$$$ be the minimal time to clear $$$[i,N]$$$ and stop at level $$$i$$$, our final answer would be

$$$ \min_{i=1}^NL[i]+R[i+1]+d $$$

In order to avoid edge cases, we can let $$$L[0]=R[N+1]=-d$$$.

Then we need to solve $$$L[i]$$$ and $$$R[i]$$$.

$$$R[n]$$$ is special because there are no further levels. We can choose to kill all monsters in $$$p[n]$$$, or use the teleportation twice and spend $$$q[n]+2d$$$. For rest $$$R[i]$$$, since we need to go from $$$i$$$ to $$$i+1$$$ and then go back to $$$i$$$, so we must have passed level $$$i$$$ twice. So the total time cost is

$$$ R[i]=R[i+1]+2d+\min(p[i],q[i]) $$$

Then we will consider $$$L[i]$$$. For $$$L[i]$$$, we have two strategies.

  1. Not going back. We go from level $$$i-1$$$ to level $$$i$$$ then kill all monsters, using $$$L[i-1]+d+p[i]$$$.
  2. Going back. We take the route $$$i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i$$$. Since we have passed level $$$i-1$$$ and $$$i$$$ twice, we can use both $$$p[i-1]$$$ and $$$q[i-1]$$$, and $$$p[i]$$$ and $$$q[i]$$$.

Comparing the two strategies, we will have

$$$ L[i]=\min(L[i-1]+d+p[i],L[i-2]+4d+\min(p[i-1],q[i-1])+\min(p[i],q[i])) $$$
Why don't we consider going back further?

We can then use the formula we come to earlier to calculate the final answer.

Code (C++)

1396D - Радужные прямоугольники

Not yet.

1396E - Паросочетание с расстояниями

Not yet.

Теги cf1396, unofficial editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский lucifer1004 2020-09-05 03:07:54 7 Tiny change: 'ercel.app/editorial/cod' -> 'ercel.app/tutorial/cod'
en4 Английский lucifer1004 2020-09-01 17:08:51 7514 Add Div.1E
en3 Английский lucifer1004 2020-08-31 13:49:40 48
en2 Английский lucifer1004 2020-08-31 13:48:27 14
en1 Английский lucifer1004 2020-08-31 13:46:20 9992 Initial revision (published)