Problem A statement

[math]

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

Solution

We can calculate answer in O(1), using direct formula, all we need is to find the biggest m, such that 1 + ... + m <= n.

Complexity

It is O(1) for time and space.

Code

from math import sqrt, floor
 
n = int(input())
m = floor((sqrt(8*n + 1) - 1)/2)
n -= m*(m+1)//2
if n == 0: n = m
print(n)

Problem B statement

[string, parser]

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

Solution

Just parse string to numbers and then go back.

Complexity

It is O(1) for time and space.

Code

x = input().rstrip()
a = int(input())
hh, mm = [int(i) for i in x.split(":")]
minutes = (mm + hh * 60 + a) % (24*60)
h1, m1 = divmod(minutes, 60)
zer = lambda x: "0"*(2 - len(str(x))) + str(x)
print(zer(h1) + ":" + zer(m1))

Problem C statement

[two pointers, sliding window]

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

Solution

The idea is for each index find next closest element which is not equal to given element. Then when we have query, check if first element in window is not equal to x. If it is not equal, return it, in the opposite case find next closest element not equal to x and return it if we have it inside window or -1 in the opposite case.

Complexity

It is O(n + q).

Code

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

d = [-1] * n
i, j = 0, 0
while i < n:
    while j + 1 < n and arr[j + 1] == arr[i]:
        j += 1
    for x in range(i, j + 1):
        d[x] = j + 1
    i = j + 1
    
ans = []

for _ in range(m):
    r, l, x = I()
    r, l = r - 1, l - 1
    if arr[r] != x:
        ans += [r + 1]
    else:
        t = d[r]
        if t > l:
            ans += [-1]
        else:
            ans += [t + 1]
            
sys.stdout.write(" ".join(map(str, ans)) + "\n")

Problem D statement

[math, simulate]

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

Solution

The idea is that for n >= 3 we can make cost equal to 0. The idea is that we need to have two numbers with distance 0, 1, 2, 3, ... and one pair can have any distance. For example for n = 7 we can build 53113564272467 and then replace numbers [1, 2, 3, 4, 5, 6, 7] to [6, 5, 4, 3, 2, 1, 7]

Complexity

Time complexity is O(n), space is O(n).

Code

import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n = int(input())
if n == 1:
    ans = [1, 1]
elif n == 2:
    ans = [1, 1, 2, 2]
else:
    d = {i: n-i for i in range(n)}
    d[n] = n
    p1 = list(range(1, n, 2))
    p2 = list(range(2, n, 2))
    ans = p1[::-1] + p1 + p2[::-1] + [n] + p2 + [n]

    ans = [d[i] for i in ans]

sys.stdout.write(" ".join(map(str, ans)) + "\n")

Problem E statement

[graph, tree, greedy]

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

Solution

First of all we have separate problems for all children of root. Next, for each problem let us have out is list of depths of leafs, for example [1, 1, 2, 2, 7, 10]. Leet us sort them and then we have the following idea. Each next time of arrival is at least bigger than previous, and also it is not smaller than depth. That is for given distances we have [1, 2, 3, 4, 7, 10]. Good exercise is to prove that this stategy will work, I think we can do it by induction.

Complexity

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

Code

from collections import defaultdict
import io, os, sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

#### import bootstrap for recursion

n = int(input())
G = defaultdict(list)

for _ in range(n-1):
    x, y = [int(i) for i in input().split()]
    G[x] += [y]
    G[y] += [x]

ans = 0

@bootstrap
def dfs(node, par, d, out):
    if len(G[node]) == 1: out += [d]
    for child in G[node]:
        if child == par: continue
        yield dfs(child, node, d + 1, out)
    yield

for x in G[1]:
    out = []
    dfs(x, 1, 0, out)
    out = sorted(out)
    for i in range(1, len(out)):
        out[i] = max(out[i - 1] + 1, out[i])
    ans = max(ans, out[-1])

print(ans + 1)

Problem F statement

[math, dp]

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

Solution

The idea is to calculate values in points 0, ..., k + 1 and then use Lagrange interpolation polynom: \(P(x) = \sum\limits_{i=1}^n y_i \prod\limits_{j=1, j\neq i}^n \frac{x - x_j}{x_i - x_j}\)

Because we have regular grid here, that is points 0, 1, 2, ..., k + 1, it is possible to evaluate all terms in O(n). One way to do it is to calculate next term using previous in 4 operations, using 2 multiplications and 2 divisions. However in python it is not enough to get AC. Another ways is to notice that each term can be seen as product of 4 terms: two of them are factorials (one with -1 sign possibly) and two other tiems have form (n - k - 1) * (n - k) * ... and (n) * (n-1) * .... We can calculate all these terms in O(k).

Complexity

It is O(k log k) to calculate all y and then we have O(k) to find answer. Notice that in other languages O(k log M) is enough.

Code

n, k = [int(i) for i in input().split()]
N = 10 ** 9 + 7

y = [0]
for i in range(1, k + 2):
    y.append((y[-1] + pow(i, k, N)) % N)

if n < k + 2:
    print(y[n] % N)
else:
    F = [1] * (k + 2)
    for i in range(1, k+2):
        F[i] = (F[i - 1] * i) % N

    I = [1] * (k+1) + [pow(F[k+1], N - 2, N)]
    for i in range(k, 0, -1):
        I[i] = I[i + 1] * (i + 1) % N

    xfac_down = [1]
    for j in reversed(range(n - k - 1, n + 1)):
        xfac_down.append((xfac_down[-1] * j) % N)

    xfac_up = [1]
    for j in range(n - k - 1, n + 1):
        xfac_up.append((xfac_up[-1] * j) % N)

    s = 0
    for i, pr in enumerate(y):
        pr = (pr * xfac_down[i]) % N
        pr = (pr * xfac_up[k + 1 - i]) % N
        pr = (pr * I[i]) % N
        pr = (pr * I[k - i + 1] * (1 - 2 * ((k - i + 1) & 1))) % N
        s = (s + pr) % N

    print(s)