Problem A statement

[2d-array, simulation]

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

Solution

Simple problem, where we need to check cases:

  1. If given cell is black, number of steps is 0.
  2. If given cell is white, but there exists black cell in the same row or column, return 1.
  3. If all cells are white, return -1.
  4. In the last case return 2.

Complexity

It is O(mn) for time and space.

Code

T = int(input())
 
for _ in range(T):
    n, m, r, c = [int(i) for i in input().split()]
    r, c = r-1, c-1
    grid = []
    for _ in range(n):
        grid += [input().rstrip()]
 
    if grid[r][c] == "B":  #check
        print(0)
    else:
        if "B" in grid[r] or any(grid[x][c] == "B" for x in range(n)):
            print(1)
        elif sum(x.count("B") for x in grid) == 0:
            print(-1)
        else:
            print(2)

Problem B statement

[greedy, game, sort]

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

Solution

The idea is that it is always optimal for Tina to sit in the corner and for Rahul closer in center. So, for every cell evaluate the biggest distance from it to all 4 corners, then sort them.

Complexity

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

Code

T = int(input())
 
for _ in range(T):
    m, n = [int(i) for i in input().split()]
    corners = [(1, n), (m, n), (m, 1), (1, 1)]
    cands = []
    for x in range(1, m+1):
        for y in range(1, n+1):
            t = 0
            for x1, y1 in corners:
                t = max(t, abs(x - x1) + abs(y - y1))
            cands += [t]
 
    cands = sorted(cands)
    print(" ".join(str(x) for x in cands))

Problem C statement

[graph, dfs, math]

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

Solution

If we have some node with degree 3, we can not consturct answer, because there is not exist 3 numbers a, b, c, such that a, b, c, a+b, b+c and c+a are prime (because of parity). In the opposite case all graph can be seen as one simple path, and we can use numbers 2 and 3 to construct it.

Complexity

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

Code

from collections import defaultdict
T = int(input())
 
for _ in range(T):
    n = int(input())
    d_arr = {}
    arr = []
    G = defaultdict(list)
    for j in range(n - 1):
        x, y = [int(i) for i in input().split()]
        arr += [[x, y]]
        d_arr[x, y] = j
        d_arr[y, x] = j
        G[x] += [y]
        G[y] += [x]
 
    max_d = 0
    ans = [0]*(n-1)
    for node in G:
        if len(G[node]) == 1:
            root = node
        max_d = max(max_d, len(G[node]))
 
    if max_d > 2:
        print(-1)
    else:
        path = [root, G[root][0]]
        for _ in range(n - 2):
            node = path[-1]
            node_next = G[node][0] if G[node][0] != path[-2] else G[node][1]
            path += [node_next]
 
        for i, x, y in zip(range(n-1), path, path[1:]):
            if i % 2 == 0:
                ans[d_arr[x, y]] = 2
            else:
                ans[d_arr[x, y]] = 3
 
        print(" ".join(str(x) for x in ans))

Problem D statement

[math]

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

Solution

Let us for each number i find all numbers which divisible by i. Then if gcd of all these numbers are equal to i (it can also be equal to i*k), then we can add i. It is enough to check this condition for all i = 1, 2, ..., N.

Complexity

Time complexity is O(N log N * log N), because we have N + N/2 + N/3 + ... sum and also we evalute gcd in O(log N).

Code

from math import gcd
from functools import reduce
import io, os, sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
 
n = int(input())
arr = [int(i) for i in input().split()]
N = max(arr) + 2
 
gcdm = lambda args: reduce(gcd, args, 0)
ans = 0
 
arr_set = [0]*N
for x in arr: arr_set[x] = 1
 
for i in range(1, N // 2 + 1):
    cands = set()
    if arr_set[i] == 1: continue
    for j in range(i, N, i):
        if arr_set[j] == 1:
            cands.add(j)
    if gcdm(list(cands)) == i:
        ans += 1
 
print(ans)

Problem E statement

[dp]

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

Solution

The idea is to use dp, but we can not allow to consider all m*n states, because it is too much. So, instead, for each floor we will consider only states where we have start or end of ladder, we will have 2k such states, call them interesting positions. Now, let us go floor by floor and do the following:

  1. First, consider all interesting positions on this floor and sort them. What we currently have in this positions is the minimum HP we need when we reach these positions from above. However we also can move in horizontal directions, so we will use the following trick: we go from left to right and update minimum costs, then we move from right to left and again update costs.
  2. After we finished with this level, we look at all ladders going from this ladder to other levels and update elements in those levels.

Complexity

Time complexity is O(k log k + n), because we consider only interesting states.

Code

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

T, INF = int(input()), float("inf")
for _ in range(T):
    n, m, k = I()
    x = I()

    dic = [{} for i in range(n+1)]
    a_bcdh = [[] for i in range(n+1)]

    for i in range(k):
        a, b, c, d, h = I()
        a_bcdh[a] += [(b, c, d, h)]
        dic[a][b] = dic[c][d] = INF

    dic[1][1] = 0
    dic[n][m] = INF

    for a in range(1, n + 1):
        level = sorted(dic[a])
        for u, v in zip(level, level[1:]):
            dic[a][v] = min(dic[a][v], dic[a][u] + abs(u - v) * x[a - 1])

        level = level[::-1]
        for u, v in zip(level, level[1:]):
            dic[a][v] = min(dic[a][v], dic[a][u] + abs(u - v) * x[a - 1])

        for b, c, d, h in a_bcdh[a]:
            dic[c][d] = min(dic[c][d], dic[a][b] - h)

    print("NO ESCAPE" if dic[n][m] == INF else dic[n][m])

Problem F statement

[]

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

Solution

TBD

Complexity

Code