Problem A statement

[math]

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

Solution

We can just find direct formula.

Complexity

It is O(1) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
 
x1, y1 = I()
x2, y2 = I()
print(max(abs(x1-x2), abs(y1-y2)))

Problem B statement

[math, digit build]

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

Solution

Here, bruteforce solution is enough. If we have bigger numbers, digit build technique need to be used.

Complexity

It is O(b - a) for time and O(1) for space.

Code

I = lambda: [int(i) for i in input().split()]
 
a, b = I()
d = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = 0
 
for num in range(a, b+1):
    for x in str(num):
        ans += d[int(x)]
 
print(ans)

Problem C statement

[greedy, sliding window]

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

Solution

The idea is to use greedy strategy: start from the beginning and add element to set until we get 2 equal elements. Also we need to deal with case when some last elements not used, just add them to the last segment.

Complexity

It is O(n) for time and space.

Code

import sys
input = sys.stdin.readline
 
n = int(input())
I = lambda: [int(i) for i in input().split()]
arr = I()
 
active = set()
start = 1
ans = []
for i in range(n):
    if arr[i] in active:
        ans += [[start, i + 1]]
        active = set()
        start = i + 2
    else:
        active.add(arr[i])
 
if not ans:
    print(-1)
else:
    ans[-1][1] = n
    print(len(ans))
    for x, y in ans:
        print(str(x) + " " + str(y))

Problem D statement

[2sum, sort, binary search]

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

Solution

If we have two attempts, it means that we need to choose 2 numbers from the first array and 2 numbers from the second array. Let us work with pairs as with just one number, then we have O(n^2) arrays, where we choose only one element. Now we want to choose such two elements x and y, that x - y - (sum(A) - sum(B))//2 is the lowest in the sense of absolute value. For this we can use the idea similar to 2sum problem: for each value find two closest elements to x + (sum(A) - sum(B))//2. Also we need to consider options where we choose only 1 numbers or 0 numbers.

Complexity

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

Code

from itertools import combinations
from bisect import bisect

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

n = int(input())
A = I()
m = int(input())
B = I()

x, y = sum(A), sum(B)
diff = (y - x)/2

A2 = sorted([A[i] + A[j] for i, j in combinations(range(n), 2)])
B2 = sorted([B[i] + B[j] for i, j in combinations(range(m), 2)])

def closest(A, B):
    ans = (float("inf"), 0, 0)
    for a in A:
        idx = bisect(B, a + diff)
        if idx < len(B):
            ans = min(ans, (abs(B[idx] - a - diff), a, B[idx]))
        if idx > 0:
            ans = min(ans, (abs(B[idx-1] - a - diff), a, B[idx-1]))
    return ans

def find_pair(A, n, x):
    for i, j in combinations(range(n), 2):
        if A[i] + A[j] == x:
            return i + 1, j + 1

d1, x1, y1 = closest(sorted(A), sorted(B))
d2, x2, y2 = closest(A2, B2)

if d1 >= abs(diff) and d2 > abs(diff):
    print(int(abs(diff) *2))
    print("0")
elif d1 <= d2:
    print(int(d1 * 2))
    print("1\n" + str(A.index(x1) + 1) + " " + str(B.index(y1) + 1))
else:
    print(int(d2 * 2))
    print("2")
    s1, t1 = find_pair(A, n, x2)
    s2, t2 = find_pair(B, m, y2)
    print(s1, s2)
    print(t1, t2)

Problem E statement

[segment tree, intervals, dfs, euler path, bit manipulation]

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

Solution

It was quite a challenge to get AC in python, but I did it. The idea is the following.

  1. Let us use euler traverse of our graph: the order in which our nodes will be visited. Then each subtree will be sum segment in this traversal. Output of function euler_tour will be two arrays f, l stands for first and last of corresponding segment. Also because our nodes in different order than in c, we create array a of correct order of colors.
  2. Now, each query of the first type need to set values equal to v on segment and the second type need to calcualte number of different values on the segment. We can use segment tree with lazy updates here. We will use bitmask to represent if we have number in segment or not, because 60 < 64.

However it is not enough to get AC, we need to optimize this:

  1. One way is to use iterative version of segment tree, which works 1.5-2 times faster.
  2. Use build function, which will build tree not in O(n log n) but just in O(n). Final complexity still will be the same, but it can help a bit.
  3. Use fast function to find number of 1 bits in 64-bit number. I used function, which precalculate 1<<16 masks and split number into 4 parts.

For me combination of 2 + 3 optimization gives AC. If you use 1 as well you also get AC, but it much more difficult to code from scratch.

Complexity

It is O(n log n + m log n), where m is number of queries.

Code

from collections import deque
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()]

class SegmentTree:
    def __init__(self, n, arr):
        self.size = 1
        while self.size < n:
            self.size *= 2

        self.T = [0] * (2 * self.size - 1)
        self.L = [0] * (2 * self.size - 1)
        self.arr = arr

    def _build(self, x, lx, rx):
        if rx - lx == 1:
            if lx < len(self.arr):
                self.T[x] = (1 << self.arr[lx])
        else:
            mx = (lx + rx) // 2
            self._build(2 * x + 1, lx, mx)
            self._build(2 * x + 2, mx, rx)
            self.T[x] = self.T[2 * x + 1] | self.T[2 * x + 2]

    def build(self):
        self._build(0, 0, self.size)

    def op_modify(self, a, b):
        if b == 0:
            return a
        return b

    def propagate(self, x, lx, rx):
        if self.L[x] == 0 or rx - lx == 1:
            return

        mx = (lx + rx) // 2
        self.L[2 * x + 1] = self.L[x]
        self.L[2 * x + 2] = self.L[x]
        self.T[2 * x + 1] = self.L[x]
        self.T[2 * x + 2] = self.L[x]
        self.L[x] = 0

    def _update(self, l, r, v, x, lx, rx):
        self.propagate(x, lx, rx)
        if l >= rx or lx >= r:
            return
        if lx >= l and rx <= r:
            self.L[x] = 1 << v
            self.T[x] = 1 << v
            return
        mx = (lx + rx) // 2
        self._update(l, r, v, 2 * x + 1, lx, mx)
        self._update(l, r, v, 2 * x + 2, mx, rx)
        self.T[x] = self.T[2 * x + 1] | self.T[2 * x + 2]
        
    def update(self, l, r, v):
        return self._update(l, r, v, 0, 0, self.size)

    def _query(self, l, r, x, lx, rx):
        self.propagate(x, lx, rx)
        if l >= rx or lx >= r:
            return 0
        if lx >= l and rx <= r:
            return self.T[x]
        mx = (lx + rx) // 2
        return self._query(l, r, 2 * x + 1, lx, mx) | self._query(l, r, 2 * x + 2, mx, rx)

    def query(self, l, r):
        return self._query(l, r, 0, 0, self.size)


def euler_tour(s):
    st, t = [s], 1
    f, l = [0] * (n + 1), [0] * (n + 1)
    while st:
        i = st[-1]
        if not f[i]:
            f[i] = t
            t += 1
        if not G[i]:
            l[i] = t - 1
            st.pop()
        else:
            j = G[i].pop()
            if not f[j]: st.append(j)
    return f, l

n, m = I()
c = I()
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = I()
    G[x].append(y)
    G[y].append(x)

f, l = euler_tour(1)

a = [0] * n
for i in range(n):
    a[f[i + 1] - 1] = c[i]


STree = SegmentTree(n, a)
STree.build()

POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcount64_table16(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16)  & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[ v >> 48        ])

ans = []
for _ in range(m):
    t = list(map(int, input().split()))
    if t[0] == 1:
        v, ck = t[1], t[2]
        fv, lv = f[v], l[v]
        STree.update(fv - 1, lv, ck)
    else:
        v = t[1]
        tmp = STree.query(f[v] - 1, l[v])
        ans += [str(popcount64_table16(tmp))]
        

sys.stdout.write("\n".join(ans))

Problem F statement

[]

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

Solution

Complexity

Code