Problem A statement

[string]

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

Solution

Just compare symbol by symbol.

Complexity

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

Code

import sys
input = sys.stdin.readline

a = input()
b = input()
m, n = len(a), len(b)
if m < n:
    a = "0"*(n - m) + a
else:
    b = "0"*(m - n) + b

equal = True
for x, y in zip(a, b):
    if x < y:
        print("<")
        equal = False
        break
    if x > y:
        print(">")
        equal = False
        break

if equal: print("=")

Problem B statement

[2d-array]

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

Solution

We need fo find minimax in this problem.

Complexity

It is O(nm) for time and O(m) for space.

Code

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

n, m = I()
ans = 0
for _ in range(n):
    row = I()
    x = min(row)
    ans = max(ans, x)

print(ans)

Problem C statement

[dfs, bfs, graph, connected components]

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

Solution

Nothing difficult here, but in python it is difficult to avoid TLE.

  1. We need to traverse our grid with dfs with stack and find connected components. For faster access we create vis = [-1] * (n * m) list. Then we start traversing from every empty sell. In vis we will have the number of connected component. In cnt[i] we will keep size of connected component i.
  2. After we traverse, do one more traverse, where for every * element we look at four neighbours and create set of connected components that can be reached from it. Then we sum all sizes of these components.

Complexity

It is O(mn) for time and space.

Code

import sys
input = sys.stdin.readline

valid = lambda x, y: -1 < x < n and -1 < y < m and grid[x][y] == '.'
dr = [0, 1, 0, -1, 0]

n, m = map(int, input().split())
grid = [input() for i in range(n)]
vis, cnt, cur = [-1] * (n * m), [], 0

for i in range(n):
    for j in range(m):
        if grid[i][j] == '.' and vis[i * m + j] == -1:
            stk, vis[i * m + j] = [(i, j)], cur
            cnt.append(1)

            while stk:
                x, y = stk.pop()
                for k in range(4):
                    nx, ny = x + dr[k], y + dr[k+1]
                    if valid(nx, ny) and vis[nx * m + ny] == -1:
                        stk.append((nx, ny))
                        vis[nx * m + ny] = cur
                        cnt[-1] += 1
            cur += 1

for i in range(n):
    tem = []
    for j in range(m):
        if grid[i][j] == '.':
            tem.append('.')
        else:
            dis = set()
            for k in range(4):
                nx, ny = i + dr[k], j + dr[k+1]
                if valid(nx, ny) and vis[nx * m + ny] != -1:
                    dis.add(vis[nx * m + ny])

            tem.append(str((sum([cnt[x] for x in dis]) + 1) % 10))

    print(''.join(tem))

Problem D statement

[sliding window, two pointers]

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

Solution

Equal to Leetcode 0340, just use sliding window here.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(x) for x in input().split()]
n, k = I()
s = I()

from collections import Counter

window = Counter()
beg, end, n, dist = 0, 0, len(s), 0
ans = (0, 0)

while beg < n and end < n:
    if (dist == k and window[s[end]] > 0) or dist < k:
        if end + 1 < n: window[s[end]] += 1
        if window[s[end]] == 1: dist += 1
        end += 1
        ans = max(ans, (end - beg, beg))
    else:
        window[s[beg]] -= 1
        if window[s[beg]] == 0: dist -= 1
        beg += 1

print(ans[1] + 1, ans[0] + ans[1])

Problem E statement

[sqrt decomposition, math]

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

Solution

Let us look for the case n = 1000. Then if we look at n//1, n//2, n//3, ..., n//n then we can group elements starging from sqrt(n) with groups with equal values. If in some group n//x, ... n//y all elements are equal, then we can calculate n%x + ... + n%y in O(1) time. So, we use sqrt decomposition, where we evaluate n%1, n%2, ... n%x, wheren x = int(sqrt(n)) and then evaluate sum in each group. We need to be careful with some edge cases.

Complexity

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

Code

from math import sqrt
 
I = lambda: [int(x) for x in input().split()]
ans = 0
n, m = I()
if m > n:
    ans += (m - n)*n
    m = n
n2 = int(sqrt(n))
vals = [n//k for k in range(n2, 0, -1)]
 
ans += sum(n%i for i in range(1, min(m, vals[0]) + 1))
 
for x, y in zip(vals, vals[1:]):
    if x > m: break
    y = min(y, m)
    ans += (y - x) * n - (y - x) * (x + y + 1)//2 * (n//y)
 
print(ans % (10**9 + 7))

Problem F statement

[string, suffix array, bst, intervals, union find, graph]

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

Solution

If you see problem about substring, there is a probability that it can be solved with suffix array or suffix tree. Let us concatenate all strings, adding different separators after each string. Then let us create suffix array as well as LCP for this string. We can do it in O(n), using template. Also we need to create the list of the same length B, which for each element of string have cost of this string. No, let us have an example 0, 1, 2, 3, 3, 1, 3, 2, 3 of LCP and think what we can do with it. Imagine also that B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Notice that in B we have one more element, because LCP elements correspond to gaps between B elements. We need to take some substring of this sequence, for example 3, 2, 3, which can correspond to abcd, abce, abdx, abde case, so we have ab four times here. Notice, that we can not choose 3, 2 and stop here, because in this case we will not count all occurences of ab. Also what matters is not four times but actually values from array B, that is their sum.

Finally, we have the following logic. In the beginning we have n separate segments with one element. Then we start with the biggest element in LCP and on each step for all elements with such value we merge groups. That is after first step we have groups: [1], [2], [3], [4, 5, 6], [7, 8], [9, 10]. After next operation we have [1], [2], [3, 4, 5, 6], [7, 8, 9, 10] and so on. We need to keep:

  1. Set of intervals, for this we will keep for each start end in dict f1 and for each end start in f2. (see CF 1618F problem which use similar idea, it also can be done with union find).
  2. We also keep in sorted list tuples (cost if interval, start, end). So, when we merget two intervals, we can quickly update it.

Finally, important think is when we do this process we did not think about unique words. I do not know the elegant way to deal with them, so what we can do is to use our LCP array. For every place, corresponding to the start of the new string, we can evaluate LCP[rank[i] - 1] and LCP[rank[i]]. If both of these values not equal to the length of current string, it means that it is unique. Also it is enough to consider only full strings: if some part of string is unique, then all string is unique as well. We can have negative and positive costs, and if cost is negative it is always optimal to consider zero-length substring for this string.

Complexity

It is O(N log N) for time and O(N) for space, where N is the total length of all strings.

Code

from collections import defaultdict
### IMPORT SortedList and SuffixArray FROM TEMPLATES.
 
n = int(input())
arr, A, B = [], [], []
for _ in range(n):
    arr += [input().rstrip()]
 
CC = [int(i) for i in input().split()]
for i in range(n):
    A += [ord(j) - 96 for j in arr[i]]
    B += [CC[i]] * len(arr[i])
    A += [i + 27]
    B += [0]  # it should not matter?
 
 
sa = suffixArray(A)
cnts = [B[i] for i in sa]
LCP, rank = lcp(A, sa)
N = len(sa)
f1 = list(range(N))
f2 = list(range(N))
 
d_lcp = defaultdict(list)
for i, x in enumerate(LCP[:-1]):
    d_lcp[x] += [i]
 
keys_lcp = sorted(d_lcp.keys())[::-1]
ans = 0
 
for i in range(N):
    if i == 0 or A[i-1] >= 27:
        q1 = LCP[rank[i] - 1]
        q2 = LCP[rank[i]]
        idx = 0 if i == 0 else A[i-1] - 26
        if q1 != len(arr[idx]) and q2 != len(arr[idx]):
            ans = max(ans, len(arr[idx]) * CC[idx])
 
costs = SortedList()
 
for key in keys_lcp:
    for u in d_lcp[key]:
        v1 = f1[u + 1]
        u1 = f2[u]
        cu, cv = cnts[u1], cnts[u + 1]
        if u1 != u: costs.remove((cu, u1, u))
        if u + 1 != v1: costs.remove((cv, u + 1, v1))
        cnts[u1] += cv
        costs.add((cu + cv, u1, v1))
        f1[u1] = v1
        f2[v1] = u1
    ans = max(ans, costs[-1][0] * key)
 
print(ans)