Codeforces contest 1633

Problem A statement

[math]

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

Solution

Just check all numbers below 1000 with the same number of digits and only those numbers which are divisible by 7 and find distance.

Complexity

It is O(1000) for time and O(1) for space.

Code

import sys
input = sys.stdin.readline
I = lambda: [int(x) for x in input().split()]
 
T = int(input())
for _ in range(T):
    n = int(input())
    ans = (4, 999)
    for i in range(1000):
        if len(str(i)) != len(str(n)): continue
        if i % 7 == 0:
            diff = sum(i!=j for i, j in zip(str(i), str(n)))
            ans = min(ans, (diff, i))
 
    print(ans[1])

Problem B statement

[greedy, array]

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

Solution

If we have x zeroes and y ones, then if x != y, answer is min(x, y), because we can choose all strign. If x == y, we can remove one element from the end and get x - 1.

Complexity

It is O(n) for time and space.

Code

import sys
input = sys.stdin.readline
I = lambda: [int(x) for x in input().split()]
 
T = int(input())
for _ in range(T):
    s = input().rstrip()
    x, y = s.count("0"), s.count("1")
    if x < y:
        print(x)
    elif y < x:
        print(y)
    else:
        print(x - 1)

Problem C statement

[greedy, math, simulation]

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

Solution

In this problem it is enough to simulate process: spend t coins for armor and k - t coins for defence. Then we can find if we can win in O(1): look at ceil(hm/dc) and ceil(hc/dm).

Complexity

It is O(k) for time and O(1) for space.

Code

from math import ceil
import sys
input = sys.stdin.readline
I = lambda: [int(x) for x in input().split()]
 
def check(hc, dc, hm, dm):
    T1 = ceil(hm/dc)
    T2 = ceil(hc/dm)
    return T1 <= T2
 
T = int(input())
for _ in range(T):
    hc, dc = I()
    hm, dm = I()
    k, w, a = I()
    ans = False
    for t in range(k + 1):
        tmp = check(hc + a*t, dc + (k-t)*w, hm, dm)
        if tmp:
            ans = True
            break
 
    print("YES" if ans else "NO")

Problem D statement

[dp, knapsack]

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

Solution

First of all for each number x we need to understand, what is minimum number of steps to reach it from 1. We can use dp for this with complexity O(N^2). Notice also that values will be in range O(log N).
Now we have classical knapsack problem: we given some costs and weighs and also we can not exceed given weight m. Again use dp to solve it. Complexity of this step will be O(N*N*log(N)), because m <= N log N (if it is more, we can return sum of all costs)

Complexity

It is O(N*N*log N) for time and O(N log N) for space.

Code

import sys
input = sys.stdin.readline
I = lambda: [int(x) for x in input().split()]

N = 1000
dp = [0, 0] + [N+1]*(N-1)
for i in range(1, N+1):
    for j in range(1, i+1):
        i2 = i + i//j
        if i2 <= N:
            dp[i2] = min(dp[i2], dp[i] + 1)

T = int(input())
for _ in range(T):
    n, k = I()
    B = I()
    val = I()
    wt = [dp[x] for x in B]
    m = sum(wt)
    if k >= m:
        print(sum(val))
    else:
        m = k
        dp2 = [0] * (m + 1)
        for i in range(1, n + 1):
            cp = dp2[:]
            q, t = wt[i - 1], val[i - 1]
            for w in range(wt[i - 1], m + 1):
                dp2[w] = max(dp2[w], cp[w - q] + t)

        print(dp2[-1])

Problem E statement

[spanning tree, union find, merge sort]

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

Solution

I think it is not possible to get AC in python at the moment. Imagine, that we have weights 1, 3, 9, 10, 14, 20 and x = 8. Then they can be separated into groups 1, 3 and 9, 10, 14, 20. Now we have numbers |8-1|, |8-3| and |9 - 8|, |10 - 8|, |14 - 8|, |20 - 8| and we need to sort these new edges. The question is now if we choose different x, how different will be the resulting sorted array? There can be O(m^2) options: we need to look at all midpoints. For each of these points we construct MST, using for example Kruskal algorithm. We save points in array w and results for them in array ans: we will keep sum of edges with signs as well as coefficient before x in our sum of absolute values.

Then when we have query, we look the closest point in w and then subtract x*coefficient from this sum.

Complexity

It is O(m^3 log m + Q*log(m)). It can be optimized to O(m^3 + Q*log(m)) if we use merge sort when we sort edges. However I think bottleneck is the second term.

Code

from bisect import bisect_left, bisect
from collections import Counter
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 DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

def kruskal(n, edges, XX):
    dsu, ans, sgn = DSU(n), 0, 0
    for x, y, w in edges:
        s = -1 + 2*int(XX <= w)
        if dsu.find(x) == dsu.find(y): continue
        dsu.union(x, y)
        ans += w*s
        sgn += s
    return ans, sgn


edges = []
n, m = I()
for _ in range(m):
    x, y, w = I()
    edges += [(x-1, y-1, 2*w)]

E = sorted([w for _, _, w in edges])

w, ans, out = [], [], 0

for i in range(m):
    for j in range(i, m):
        w += [(E[i]+E[j])//2]

w = sorted(set(w))
for i in range(len(w)):
    XX = w[i]
    edges = sorted(edges, key=lambda t: abs(XX - t[2]))
    ans += [kruskal(n, edges, XX)]

p, k, a, b, c = I()
Q = I()
for _ in range(k - p):
    Q += [(Q[-1] * a + b) % c]

Q2 = []
cntQ = Counter(Q)
for val in cntQ:
    if cntQ[val] % 2 == 1:
        Q2 += [val]

for x in Q2:
    t = bisect_left(w, 2*x)
    if t >= len(w): t -= 1
    out ^= (ans[t][0]//2 - x*ans[t][1])

print(out)

Solution 2 (AC)

Finally, I found a way to get AC in python as well. So, the overall idea is the same, but instead of O(m^2) points it is enough to make smaller number of points.

Lemma: there will be at most O(n) different spanning tree, when we change x. Quote by grandmaster peti1234: For each edge there is only one interval, when it is useful.

We can try to find this breaking points using binary search. For one check we need O(m log m) time for kruskal, there will be no more than m candidates and we perform binary search from M = 10**8 candidates. So complexity of this step is O(m^2*log m*log M). Also we need to add all our weights as breaking points: although spanning tree will not change, what will be changed is the way how to calculate sum. What our kruskal funcion return is (weighs, sum of weights with coefficient +-, linear coefficient before x).

Complexity

It is O(m^2 * log m * log M + Q * log(m))

Code

from bisect import bisect_left
from collections import defaultdict
I = lambda: [int(x) for x in input().split()]

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        self.p[self.find(x)] = self.find(y)


edges = []
n, m = I()
for _ in range(m):
    x, y, w = I()
    edges += [(x - 1, y - 1, w)]

p, k, a, b, c = I()
Q = I()
for _ in range(k - p):
    Q += [(Q[-1] * a + b) % c]

def kruskal(x):
    dsu, ans, W, sgn = DSU(n), [], 0, 0
    E = sorted(edges, key=lambda q: abs(x - q[2]))
    for u, v, w in E:
        if dsu.find(u) == dsu.find(v): continue
        s = -1 + 2 * int(x <= w)
        dsu.union(u, v)
        ans += [w]
        W += w * s
        sgn += s
    return sorted(ans), W, sgn

points = defaultdict(tuple)
at, maxval = 0, 10**8

while at <= maxval:
    cur_weights = kruskal(at)[0]
    lo, hi = at, maxval
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if kruskal(mid)[0] == cur_weights:
            lo = mid
        else:
            hi = mid - 1

    points[lo] = kruskal(lo)
    at = lo + 1

for _, _, w in edges:
    points[w] = kruskal(w)

w, out = sorted(points), 0

for x in Q:
    idx = bisect_left(w, x)
    if idx >= len(w): idx -= 1
    out ^= (points[w[idx]][1] - x*points[w[idx]][2])

print(out)

Problem A statement

Solution

Complexity

Code

Problem B statement

Solution

Complexity

Code

Problem C statement

Solution

Complexity

Code

Problem D statement

Solution

Complexity

Code

Problem E statement

Solution

Complexity

Code

Solution 2 (AC)

Complexity

Code

Problem F statement

Solution

Complexity

Code