Problem A statement

[simulate]

https://codeforces.com/contest/632/problem/A

Solution

Simulate process from the end.

Complexity

Time and space complexity is O(n).

Code

n, p = [int(i) for i in input().split()]
ans = 0
free = 0
arr = [input().rstrip()[-1] == "s" for _ in range(n)]

for x in arr[::-1]:
    if x:
        ans = ans * 2 + 1
        free += 1
    else:
        ans *= 2

print(ans*p - p//2*free)

Problem B statement

[accumulate, greedy]

https://codeforces.com/contest/632/problem/B

Solution

We need to find prefix or suffix, where diff between A and B elements are the biggest. So, create sm array, where all elements of A with plus sign and B with minus sign.

Complexity

It is O(n) for time and space.

Code

from itertools import accumulate
n = int(input())
arr = [int(i) for i in input().split()]
s = input().rstrip()
 
sm = [i*(1 - 2*(x == "B")) for i, x in zip(arr, s)]
 
acc1 = [0] + list(accumulate(sm))
acc2 = [0] + list(accumulate(sm[::-1]))
t = max(max(acc1), max(acc2))
 
print(sum(i* (x=="B") for i, x in zip(arr, s)) + t)

Problem C statement

[sort, greedy]

https://codeforces.com/contest/632/problem/C

Solution

Here we need to use custom sort: it is equal to Leetcode 0179

Complexity

It is O(n log n * x), where n is the length of strings.

Code

from functools import cmp_to_key
n = int(input())
strs = [input().rstrip() for _ in range(n)]

compare = lambda a, b: -1 if a+b < b+a else 1 if a+b > b+a else 0
print("".join(sorted(strs, key = cmp_to_key(compare))))

Problem D statement

[math]

https://codeforces.com/contest/632/problem/D

Solution

The idea is for each number x find all numbers which are divisible by x, that is x, 2x, 3x, .... When we iterate over x = 1, 2, ..., m we will do at most O(m log m) operations. To make it faster in the beginning we can evaluate counter of our numbers and then when we iterate we do divs[j] += cnt[i]. Then we find the maximum from divs array and take the first value with this value. It is important to take the first one, because for example for array [2, 2, 2, 2, 3, 3, 3], divs[6] = divs[12] = 7. Then after we found this value, iterate over numbers once again and add only elements which divide this lcm.

Complexity

It is O(m log m + n) for time and O(m) for space.

Code

from collections import Counter
import io, os, sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
I = lambda: [int(i) for i in input().split()]
 
n, m = I()
arr = I()
cnt = Counter(arr)
divs = [0] * (m + 1)
 
for i in range(1, m + 1):
    for j in range(i, m + 1, i):
        divs[j] += cnt[i]
 
lcm = max(range(1, m+1), key = divs.__getitem__)
out = []
 
for i, a in enumerate(arr):
    if lcm % a == 0: out += [i]
        
print(str(lcm) + " " + str(len(out)))
print(" ".join(str(x+1) for x in out))

Problem E statement

[nnt, generating functions, divide and conquer]

https://codeforces.com/contest/632/problem/E

Solution

Imagine, that we have costs 3, 5, 11. Then, let us create polynom x^3 + x^5 + x^11. Then what we need to do is take it to the power k and take only those elements which are not equal to 0. We can do it with nnt (or here with fft, because coefficients are small enough),

Complexity

It is O(N*log^2N), where N = max(a) * k < 1000000

Code

MOD, ROOT = 998244353, 3
I = lambda: [int(i) for i in input().split()]
# IMPORT NNT FROM TEMPLATES
 
n, k = I()
A = I()
N = max(A) + 1
 
pol = [0]*N
for x in A: pol[x] = 1
arr = [pol[:] for _ in range(k)]
 
def prod(l):
    n = len(l)
    if n == 1: return l[0]
    lft = prod(l[:n//2])
    rgh = prod(l[n//2:])
    ntt_conv(lft, rgh)
    return [int(i != 0) for i in lft]
 
pol = prod(arr)
ans = [i for i, x in enumerate(pol) if x == 1]
print(" ".join(str(x) for x in ans))

Solution 2

In fact, complexity can be improved: we can do it in O(N log N), because previously we had T(n) = 2*T(n/2) + n log n complexity and in fact we can do it just in T(n) = T(n/2) + n log n, because we have two subproblems which are the same. In practice it will give only twice speed gain.

Code 2

MOD, ROOT = 998244353, 3
I = lambda: [int(i) for i in input().split()]
# IMPORT NNT FROM TEMPLATES
 

n, k = I()
A = I()
N = max(A) + 1
 
pol = [0]*N
for x in A: pol[x] = 1
 
def power(pol, n):
    result = [1]
    while n > 0:
        if n % 2: ntt_conv(result, pol[:])
        result = [int(i != 0) for i in result]
        x, y = pol[:], pol[:]
        ntt_conv(x, y)
        n //= 2
        pol = [int(i != 0) for i in x]
    return result
 
pol = power(pol, k)
ans = [i for i, x in enumerate(pol) if x == 1]
print(" ".join(str(x) for x in ans))

Problem F statement

[graph, divide and conquer, MST]

https://codeforces.com/contest/632/problem/F

Solution

First of all notice that we can look at this problem as at graph. Also inequalities in the problem statement means that for every 3 nodes a, b, c: d(a, b) <= max(d(a, c), d(b, c)). If we write down these conditions for (a, b, c), (b, c, a) and (c, a, b) then we see that we can have only triples of distances of the form x, y, y, where x <= y. That is we can not have say 1, 2, 3 or 1, 1, 3, but we can have 1, 3, 3.

Next step is for fixed node look at all edges going from this node and split elements into groups with equal edge weight. That is if we have in the first row [0, 4, 4, 4, 5, 4, 3, 3, 5, 4], then we split into groups 3: (6, 7), 4: (1, 2, 3, 5, 9), 5: (4, 8) and . Now we want to understand which edges we can have between and inside groups. In fact two conditions need to be hold:

  1. Between groups with edges values x and y, where x < y we must have edge with weight y. Indeed, we have triangle, where we already have (x, y) and the remaining side can be only y.
  2. Inside each group we must have values, which is smaller or equal than value of edge going to this group. Again, we have triangle with edges (x, x) and the reset value should be <= x.
  3. In fact these two conditions are sufficient and enough! It can be proven, considering different type of triangles.

So, we can use divide and conquer idea, where `check(arr, LIM):

  1. arr is array if indexes we consider.
  2. LIM is maximum limit of value of edge we allowed.
  3. first output is True/False: is our matrix magic/not magic

  4. second output is maximum value of edge for given arr of indexes.

  5. First, we check if len(arr) == 1, then we return (True, 0).
  6. Then we choose pivot as first element of arr and separate into groups.
  7. Then we go through sorted keys and check condition 1, if it is broken, return False and not matter what as second value.
  8. Then we go through subproblems and again if we have False somewhere, return False and anything.
  9. Also we update max_val: maximum value of edge for given set of indexes.
  10. If max_val > LIM, condition 2 is broken and we return False, in the opposite case return True and maximum weight.

Complexity

It is O(n^2 log n) for time and O(n^2) for space.

Code

from collections import defaultdict
from itertools import combinations, product
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.setrecursionlimit(3000)
 
I = lambda: [int(i) for i in input().split()]
n = int(input())
A = [I() for _ in range(n)]
 
 
def check(arr, LIM):
    if len(arr) == 1:
        return (True, 0)
 
    d = defaultdict(list)
    pivot = arr[0]
    for x in arr[1:]:
        d[A[pivot][x]] += [x]
 
    vals = sorted(d.keys())
    for x, y in combinations(vals, 2):
        for i1, i2 in product(d[x], d[y]):
            if A[i1][i2] != y: return (False, 0)
    
    max_val = vals[-1]
    for x in vals:
        res, vl = check(d[x], x)
        if not res: return (False, 0)
        max_val = max(max_val, vl)
    
    return (False, 0) if max_val > LIM else (True, max_val)
 
 
def solve():
    for i in range(n):
        for j in range(i + 1, n):
            if A[i][j] != A[j][i]: return False
        if A[i][i] != 0: return False
    return check(list(range(n)), float("inf"))[0]
 
 
print("MAGIC" if solve() else "NOT MAGIC")

Remark

Authors solution of this problem use MST.