Codeforces contest 1651

Problem A statement

[math]

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

Solution

We just can return answer directly.

Complexity

It is O(1) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
 
T = int(input())
for _ in range(T):
    n = int(input())
    print((1<<n) - 1)

Problem B statement

[constructive, math, greedy]

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

Solution

We can notice that for example to exist we need any two numbers be at >= 3 times different. So, if we construct [1, 3, 9, ...] and maximal number is smaller than 10**9, we can construct, and we can not in the opposite case.

Complexity

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

Code

I = lambda: [int(i) for i in input().split()]
 
T = int(input())
for _ in range(T):
    n = int(input())
    ans = [1]
    for i in range(30):
        if ans[-1] * 3 > 10**9: break
        ans += [ans[-1] * 3]
 
    if n >= 20:
        print("NO")
    else:
        print("YES")
        print(" ".join(str(x) for x in ans[:n]))

Problem C statement

[greedy, graph]

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

Solution

We need to connect the first and the last elements for both arrays. We can either connect them with each other or we can connect them with smaller element from the opposite array. If we have A and B for left ends, we can have two options: connecte with each other or connect with minimum from the opposite, the same is for the right ends. Also we have case with A and B[::-1].

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
 
def check(A, B):
    t1 = min(abs(a - B[0]) for a in A)
    t2 = min(abs(b - A[0]) for b in B)
    t3 = abs(A[0] - B[0])
    t4 = min(abs(a - B[-1]) for a in A)
    t5 = min(abs(b - A[-1]) for b in B)
    t6 = abs(A[-1] - B[-1])
    return min(t1 + t2, t3) + min(t4 + t5, t6)
 
T = int(input())
for _ in range(T):
    n = int(input())
    A = I()
    B = I()
    print(min(check(A, B), check(A, B[::-1])))

Problem D statement

[bfs, graph]

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

Solution

The idea is the following:

Put all border points to queue, that is all points, which have at least one empty neighbour.
Start multisource bfs, where we go only inside our points, that is visit only points from our set: if we found closer elements, we update our dictionary.

Complexity

It is O(n) for time and space.

Code

from collections import deque
I = lambda: [int(i) for i in input().split()]

n = int(input())
pts = [tuple(I()) for _ in range(n)]
dist = {p: (-1, -1, int(1e9)) for p in pts}
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
Q = deque()

for ix, iy in pts:
    for dx, dy in d:
        nx, ny = ix + dx, iy + dy
        if (nx, ny) not in dist: dist[(ix, iy)] = (nx, ny, 1)
    if dist[(ix, iy)][2] == 1:
        Q.append((ix, iy))

while Q:
    x, y = Q.popleft()
    cx, cy, cd = dist[(x, y)]
    for dx, dy in d:
        nx, ny = x + dx, y + dy
        if (nx, ny) in dist and cd + 1 < dist[(nx, ny)][2]:
            dist[(nx, ny)] = cx, cy, cd + 1
            Q.append((nx, ny))

for i in range(n):
    print(' '.join(map(str, dist[pts[i]][:2])))

Remark

There is also O(n sqrt(n)) time complexity solution, which can get AC in faster languages: the idea is for each point be able to find the leftest and the rightest empty place. Then for each point we can go from -sqrt(n//2) to sqrt(n//2) by y coordinate and find the closest leftest and rightest places.

Codeforces contest 1651

Problem A statement

Solution

Complexity

Code

Problem B statement

Solution

Complexity

Code

Problem C statement

Solution

Complexity

Code

Problem D statement

Solution

Complexity

Code

Remark

Problem E statement

Solution

Complexity

Code

Problem F statement

Solution

Complexity

Code