Codeforces contest 1661

Problem A statement

[dp, array, greedy]

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

Solution

We can use greedy here, where on the each step we decide if we swich elements or not.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(x) for x in input().split()]
T = int(input())
 
for j in range(T):
    n = int(input())
    A = I()
    B = I()
    ans = 0
    for i in range(n - 1):
        c1 = abs(A[i] - B[i + 1]) + abs(B[i] - A[i + 1])
        c2 = abs(A[i] - A[i + 1]) + abs(B[i] - B[i + 1])
        ans += min(c1, c2)
 
    print(ans)

Problem B statement

[bfs, graph]

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

Solution

Let us reverse our graph, then start from zero and calculate distances to all values.

Complexity

It is O(N + R), where N = 32768 and R is number of queries.

Code

I = lambda: [int(x) for x in input().split()]
from collections import deque
 
n = int(input())
arr = I()
M = 32768
 
Q = deque([(0, 0)])
d = {0 : 0}
while Q:
    steps, x = Q.popleft()
    if (x - 1) % M not in d:
        Q.append((steps + 1, (x - 1) % M))
        d[(x-1)%M] = steps + 1
    if x % 2 == 0:
        if x//2 not in d:
            Q.append((steps + 1, x//2))
            d[x//2] = steps + 1
        if x//2 + M//2 not in d:
            Q.append((steps + 1, x//2 + M//2))
            d[x//2 + M//2] = steps + 1
 
arr = [d[x] for x in arr]
print(" ".join(str(x) for x in arr))

Problem C statement

[greedy, array]

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

Solution

First of all we can prove that we always need to increase either to max or max + 1. Then we check how many days can be made with value 2. If we have more than 2/3 of total sum we need to grow, then we have tight number of days. If we have steps1 > steps2, then we need to fill gaps.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(x) for x in input().split()]
 
def check(arr, max_val):
    B = [max_val - x for x in arr if x != max_val]
    steps2 = sum(x // 2 for x in B)
    steps1 = sum(B) - steps2 * 2
    if steps1 > steps2:
        return 2*steps1 - 1
    else:
        sm = sum(B)
        if sm % 3 == 0: return sm//3*2
        if sm % 3 == 1: return sm//3*2 + 1
        if sm % 3 == 2: return (sm+1)//3*2
 
T = int(input())
for _ in range(T):
    n = int(input())
    arr = I()
    t1 = check(arr, max(arr))
    t2 = check(arr, max(arr) + 1)
    print(min(t1, t2))

Problem D statement

[segment tree, greedy, array]

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

Solution 1

We can use segment tree with updates of arithmetic progressions. We start from the end and use greedy strategy.

Complexity

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

Code

class SegmentTree:
    def __init__(self, n):
        bc = n.bit_length()
        self.sn = 1 << bc
        self.stree = [[0, 0] for _ in range(self.sn * 2)]

    def update(self, l, r, a, d):
        def _update(ll, rr, p):
            if r <= ll or rr <= l:
                return
            if l <= ll and rr <= r:
                self.stree[p][0] += a
                self.stree[p][1] += d
            else:
                m = (ll + rr) // 2
                _update(ll, m, p * 2)
                _update(m, rr, p * 2 + 1)

        a -= d * l
        _update(0, self.sn, 1)

    def get(self, i):
        a, d = 0, 0
        p = self.sn + i
        while p >= 1:
            a += self.stree[p][0]
            d += self.stree[p][1]
            p = p // 2
        return a + d * i

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

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

n, k = I()
B = I()
B = B[::-1]
ans = 0
STree = SegmentTree(n)

for i in range(n - k):
    val_i = STree.get(i)
    if val_i < B[i]:
        x = (B[i] - val_i + k - 1)//k
        ans += x
        STree.update(i, i+k, x*k, -x)

last = 0
for i in range(n - k, n):
    x = i - n + k + 1
    Ai = STree.get(i)
    if Ai < B[i]:
        last = max(last, (B[i] - Ai + k - x)//(k + 1 - x))

print(ans + last)

Solution 2

There is better O(n) time complexity solution! We need to keep array of lazy updates d. I will add more details later.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(x) for x in input().split()]
n, k = I()
B, d = I() + [0]*k, [0] * (n + k)

s = total = 0
for i in range(n-1, -1, -1):
    B[i] -= total
    if B[i] > 0:
        dd = min(k, i + 1)
        d[i] = (B[i] + dd - 1)//dd
    s += d[i] - d[i + k]
    total += d[i] * dd - s
    
print(sum(d))

Codeforces contest 1661

Problem A statement

Solution

Complexity

Code

Problem B statement

Solution

Complexity

Code

Problem C statement

Solution

Complexity

Code

Problem D statement

Solution 1

Complexity

Code

Solution 2

Complexity

Code

Problem E statement

Solution

Complexity

Code

Problem F statement

Solution

Complexity

Code