Problem A statement

[math]

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

Solution

In fact we can have direct formula: there will always be n - 1 games, no matter how we play.

Complexity

It is O(1) for time and space.

Code

n, b, p = [int(i) for i in input().split()]
print((n - 1) * (2 * b + 1), p * n)

Problem B statement

[math]

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

Solution

Use property of divisibility by 4: two last digits should be divided by 4. So, consider unique digits and also all pairs of adjacent digits.

Complexity

It is O(n) for time and space.

Code

s = input().rstrip()
ans = sum(int(i) % 4 == 0 for i in s)
n = len(s)
for i in range(n - 1):
    ans += (int(s[i:i+2]) % 4 == 0) * (i + 1)

print(ans)

Problem C statement

[string, greedy]

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

Solution

Use greedy strategy: start from the first letter and each time try to decrease k as much as possible. If we can decrease it by say 10 and we have only k = 8, then find letter which makes k = 0. Also if k == 0, from this moment use original letters. In the end check if k = 0.

Complexity

It is O(n) for time and O(n) for space.

Code

n, k = [int(i) for i in input().split()]
s = input().rstrip()
ans = []

for x in s:
    max_dist = max(ord(x) - ord("a"), ord("z") - ord(x))
    if k == 0:
        ans += [x]
    elif max_dist <= k:
        k -= max_dist
        ans += ["a"] if ord(x) - ord("a") == max_dist else ["z"]
    else:
        for l in "abcdefghijklmnopqrstuvwxyz":
            if abs(ord(l) - ord(x)) == k:
                ans += [l]
                k = 0
                break

print("".join(ans) if k == 0 else -1)

Problem D statement

[dp, digit build, math]

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

Solution

First of all, we can solve 2 problems: for [1, b] and for [1, a] and then check a itself. We will use dp to evaluate number of states: go digit by digit and in dp1 of length m we keep number of values with reminder 0, ..., m-1 such that we not in border case and dp2 for border case. Here border means for number 142857: 142??? is border and 141??? is not. For border we can take only some values and for not border we can take 0, ..., 9. However we also need to deal with condition about d. We have several cases depending of parity of i. c1 is for not border -> not border cases, c2 is for border -> not border cases and c3 is for border -> border` cases.

Complexity

Time complexity is O(m * q * d), where q = len(a) = len(b) and d = 10 is number of digits.

Code

def calc(a, d, m):
    dp1 = [0]*m
    dp2 = [1] + [0]*(m-1)
    for i in range(len(a)):
        dp11, dp21 = [0] * m, [0] * m
        ai = int(a[i])
        start = 1 if i == 0 else 0
        c1 = [d] if i % 2 == 1 else set(range(start, 10)) - set([d])
        c2 = set(range(start, ai)) - set([d]) if i % 2 == 0 else [d] if d < ai else []
        c3 = set([ai]) - set([d]) if i % 2 == 0 else [d] if ai == d else []
        for x in range(m):
            for c in c1: dp11[(x*10 + c) % m] += dp1[x]
            for c in c2: dp11[(x*10 + c) % m] += dp2[x]
            for c in c3: dp21[(x*10 + c) % m] += dp2[x]
 
        dp1, dp2 = [i%N for i in dp11], [i%N for i in dp21]
    return dp1[0] + dp2[0]
 
m, d = [int(i) for i in input().split()]
N = 10**9 + 7
a = input().rstrip()
b = input().rstrip()
 
t1 = calc(a, d, m)
t2 = calc(b, d, m)
addon = a[1::2] == str(d)*len(a[1::2]) and a[::2].count(str(d)) == 0 and int(a) % m == 0
 
print((t2 - t1 + addon) % N)

Problem E statement

[2d-array, dp, binary indexed tree]

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

Solution

First, for each cell evaluate how many cells we can go the left (array lft) and to the right (array rgh). Next step is to consider each diagonal and look at values for from lft and rgh arrays, imagine it is [2, 4, 2, 2, 3] the lft and [2, 2, 3, 3, 4] for the rgh. It will be our arguments for function solve. We start to traverse this array from start and keep in BIT indexes of active elements.

  1. At first we have [0, 0, 0, 0, 0].
  2. Then we look at first element, so have [1, 0, 0, 0, 0]. Also we look at sum at range (pos - r[pos], pos) and update our answer: we can use only active bits, that is why we need sum.
  3. On the next step we have [1, 1, 0, 0, 0].
  4. Now, when we have third element, we first need to turn of some bits, and we have [0, 1, 0, 0, 0], because the first bit is not active anymore. Also, we turn on next bit, so we have [0, 1, 1, 0, 0]. How we understand which bit we need to turn off? When we turn in on, we put delayed index in list tbr (to be removed)
  5. And so on.

Complexity

Time complexity is O(nm log m), space is O(mn).

Code

import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.sums = [0] * (n + 1)

    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] += delta
            i += i & (-i)

    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

    def sum(self, i, j):
        return self.query(j) - self.query(i - 1)


n, m = [int(i) for i in input().split()]
grid = [input() for _ in range(n)]
lft = [[0] * m for _ in range(n)]
rgh = [[0] * m for _ in range(n)]
for i in range(n):
    row = grid[i]
    lft[i][0] = 1 if row[0] == 'z' else 0
    for j in range(1, m):
        if row[j] == 'z':
            lft[i][j] = lft[i][j-1] + 1
    rgh[i][m-1] = 1 if row[m-1] == 'z' else 0
    for j in range(m-2, -1, -1):
        if row[j] == 'z':
            rgh[i][j] = rgh[i][j+1] + 1

def solve(l, r, d):
    res = 0
    tbr = [[] for _ in range(lend + 1)]
    for pos, val in enumerate(d):
        while tbr[pos]:
            bit.update(tbr[pos].pop() + 1, -1)
        c = min(val, l[pos])
        if c > 0:
            bit.update(pos + 1, 1)
            tbr[pos + c].append(pos)
        if r[pos] > 0:
            res += bit.sum(max(1, pos - r[pos] + 2), pos + 1)
    return res

res = 0
for i, j in [(0, a) for a in range(m)] + [(b, m-1) for b in range(1, n)]:
    lend = min(n-i, j+1)
    d = [grid[i+p][j-p] == "z" for p in range(lend)]
    for p in range(lend-2, -1, -1):
        d[p] = d[p+1] + 1 if d[p] else 0
    bit = BIT(lend)

    l = [lft[i+p][j-p] for p in range(lend)]
    r = [rgh[i+p][j-p] for p in range(lend)]
    res += solve(l, r, d)

print(res)

Problem F statement

[graph, maximal flow, hall’s lemma]

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

Solution

Here is the official solution with small changes.

  1. Add points (0, 0) and (b, n) to our points. Then we split everything into intervals and we know how many numbers we need to have on each interval.
  2. Create the following graph. The first group A contains 5 vertices, representing possible remainders. The second group B contains q vertices, representing intervals. Each vertex from A should be connected with the source by an edge with capacity n/5. Each vertex from B should be connected with the sink by an edge with capacity equal to the size of the interval. Between each vertex x from A and y from B should be an edge with capacity equal to the number of numbers in the interval y, giving remainder x when divided by 5.

You can also use see that it’s similar to finding matching. In fact, we can use the Hall’s marriage theorem. For each 2^5 sets of vertices from A we need to check how many edges there is from those nodes. For example for mask 10110, we need to have at least n//5*3 edges. We can have different ways to check it, the fastest is O(2^C * n), but it is not necessary for this problem, O(2^C * b) is enough: for each mask traverse all intervals and calculate number of edges.

Complexity

It is O(2^C * b) for time and O(n) for space.

Code

I = lambda: [int(i) for i in input().split()]

n, b, m = I()
a = [(0, 0)] + sorted([I() for _ in range(m)]) + [(b, n)]

def solve():
    for S in range(32):
        sm = 0
        for (l, x), (r, y) in zip(a, a[1:]):
            if y - x < 0: return 1
            sm += min(sum(S >> (i % 5) & 1 for i in range(l + 1, r + 1)), y - x)
        if sm < n / 5 * bin(S).count("1"): return 1
    return 0

print("un" * solve() + "fair")