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

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

1397A - Juggling Letters

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

Code (Python 3)

from sys import stdin, stdout


def read_int():
    return int(stdin.readline().strip())


t = read_int()
for case_num in range(t):
    n = read_int()
    counter = [0 for _ in range(26)]

    for i in range(n):
        s = stdin.readline().strip()
        for c in s:
            counter[ord(c) - ord('a')] += 1
    ok = True
    for count in counter:
        if count % n != 0:
            ok = False
            break
    stdout.write('YES\n' if ok else 'NO\n')

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)

from sys import stdin, stdout


def read_int():
    return int(stdin.readline().strip())


def read_ints():
    return map(int, stdin.readline().strip().split(' '))


n = read_int()
a = list(read_ints())
a.sort()
s = sum(a)
cost = s - n
j = 2
while pow(j, n - 1) <= s * 2:
    b = [1]
    for k in range(n - 1):
        b.append(b[-1] * j)
    tot = sum([abs(a[i] - b[i]) for i in range(n)])
    cost = min(cost, tot)
    j += 1
print(cost)

1396A - Multiples of Length

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++)

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve() {
    int n;
    read(n);
    vector<ll> a(n);
    for (int i = 0; i < n; ++i)
      read(a[i]);
    if (n == 1) {
      printf("1 1\n%lld\n1 1\n1\n1 1\n-1\n", -a[0]);
      return;
    }
    printf("1 %d\n", n - 1);
    for (int i = 0; i < n - 1; ++i) {
      ll r = (a[i] % n + n) % n;
      a[i] += r * (n - 1);
      printf("%lld ", r * (n - 1));
    }
    printf("\n2 %d\n", n);
    for (int i = 1; i < n; ++i) {
      ll r = (a[i] % n + n) % n;
      a[i] += r * (n - 1);
      printf("%lld ", r * (n - 1));
    }
    printf("\n1 %d\n", n);
    for (ll num : a)
      printf("%lld ", -num);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  Solution solution = Solution();
  solution.solve();
}

1396B - Stoned Game

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++)

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve() {
    int n;
    read(n);
    vector<int> a(n);
    int sum = 0, hi = 0;
    for (int i = 0; i < n; ++i) {
      read(a[i]);
      sum += a[i];
      hi = max(hi, a[i]);
    }
    if (hi > sum - hi) {
      printf("T\n");
      return;
    }
    printf(sum % 2 == 0 ? "HL\n" : "T\n");
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}

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.

Not going back. We go from level $$$i-1$$$ to level $$$i$$$ then kill all monsters, using $$$L[i-1]+d+p[i]$$$.
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 - Rainbow Rectangles

Not yet.

1396E - Distance Matching

Not yet.

Rev.	By	When	Δ	Comment
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)

1397A - Juggling Letters

1397B - Power Sequence

1396A - Multiples of Length

1396B - Stoned Game

1396C - Monster Invaders

include

include

include

1396D - Rainbow Rectangles

1396E - Distance Matching

History