Problem A statement

[greedy, sort]

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

Solution

Just use the biggest cards.

Complexity

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

Code

n = int(input())
m = int(input())
arr = []
for _ in range(n):
    arr += [int(input())]

arr = sorted(arr)[::-1]
acc = 0
for i in range(n):
    acc += arr[i]
    if acc >= m:
        print(i+1)
        break

Problem B statement

[math, combinatorics]

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

Solution

Evaluate number of all options and then subtract number of optinos which violates condition.

Complexity

It is O(n) for time and space.

Code

from collections import Counter

I = lambda: [int(x) for x in input().split()]
n, m = I()
arr = I()
cnt = Counter(arr)
ans = n*(n-1)//2
for x in cnt:
    ans -= cnt[x]*(cnt[x] - 1)//2

print(ans)

Problem C statement

[sort, greedy]

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

Solution

First of all, we can understand what is the final position of our servers: we need to put sm//n to all of them and then add 1 to sm%n of them. Let us sort start and final position, then answer will be sum of absolute differences of elements divided by 2`. Why though it is a good mathematical problem.

Complexity

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

Code

n = int(input())
arr = [int(i) for i in input().split()]

arr = sorted(arr)[::-1]
sm = sum(arr)
final = [sm//n]*n
for i in range(sm % n):
    final[i] += 1

ans = sum(abs(x-y) for x, y in zip(arr, final))
print(ans//2)

Problem D statement

[binary search, merge sort]

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

Solution

The idea is to ask question: given that we can use only first x days, can we buy k items. To answer this question we need to find the lowerst cost of dollar and pound in the first x days. Now, using this costs, we have two sorted array of prices for two types of items (if we sort them once in the beginning), we can merget sort them and choose the smallest k. Then we use binary search to answer the question what is the minimum number of days we need. One short optimization is to use cumulative minimums to fast access for min costs of dollar and pound.

Complexity

It is O(n log n) for time and O(n) for space. It can be made to O(k log n) in fact.

Code

from itertools import accumulate
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()]

C1, C2 = [], []
n, m, k, s = I()
A = I()
B = I()
for i in range(m):
    t, c = I()
    if t == 1:
        C1 += [(c, i)]
    else:
        C2 += [(c, i)]

C1, C2 = sorted(C1), sorted(C2)
A_acc, B_acc = list(accumulate(A, min)), list(accumulate(B, min))

def check(x):   # price to buy in first x days
    min_C1 = A_acc[x-1]
    min_C2 = B_acc[x-1]
    prices = sorted([min_C1 * c for c, _ in C1] + [min_C2 * c for c, _ in C2])
    return sum(prices[:k])

if check(n) > s:
    print(-1)
else:
    beg, end = 0, n
    while beg + 1 < end:
        mid = (beg + end)//2
        price = check(mid)
        if price <= s:
            end = mid
        else:
            beg = mid

    x = beg + 1
    min_C1 = min(A[:x])
    min_C2 = min(B[:x])
    day = [A[:x].index(min_C1), B[:x].index(min_C2)]
    prices = sorted([(min_C1 * c, i, 0) for c, i in C1] + [(min_C2 * c, i, 1) for c, i in C2])
    ans = [(i, day[t]) for _, i, t in prices[:k]]
    print(x)
    for a, b in ans:
        print(str(a+1) + " " + str(b+1))

Problem E statement

[LCA, spanning tree, dsu, binary lifting]

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

Solution

This is the author’s solution of this problem, but unfortunately it gives TLE in python, and I spend some time trying to optimize it. However it is useful template for future, so here it is.

Let us construct MST of our graph, using for example Kruskal algorithm (I tried Prim as well, but still TLE). Then if node in our MST, we alredy know the answer. If it is not, we need to find loop if we add this edge to MST. For this we find LCA uv of nodes u and v and our loop is now u---uv---v-u. We need to find maximum weigth in this loop, for this we can use binary lifting. See leetcode 1724 problem for more details.

Complexity

Time comlexity is O(E log n).

Code

from collections import defaultdict, deque
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
I = lambda: [int(i) for i in input().split()]

def kruskal(E):
    total_w = 0
    for u, v, w in E:
        if dsu.find(u) == dsu.find(v): continue
        dsu.union(u, v)
        MST[u].append((v, w))
        MST[v].append((u, w))
        total_w += w
    return total_w


def LCA(u, v):
    if depths[u] > depths[v]:
        u, v = v, u

    diff = depths[v] - depths[u]

    weight = 0
    places = [i for i in range(diff.bit_length()) if diff & (1 << i) != 0]
    for index in places:
        weight = max(weight, max_path[v][index])
        v = parents[v][index]

    if u == v: return weight
    for i in range(bits - 1, -1, -1):
        if parents[u][i] != parents[v][i]:
            weight = max([weight, max_path[u][i], max_path[v][i]])
            u = parents[u][i]
            v = parents[v][i]

    return max([weight, max_path[u][0], max_path[v][0]])

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def union(self, a, b):
        self.parent[self.find(b)] = self.find(a)

n, m = I()
E = []
d_E = {}
for i in range(m):
    x, y, w = I()
    E += [(x-1, y-1, w)]
    d_E[x-1, y-1, w] = i

dsu = DSU(n)
depths = [0] * n
bits = (n+1).bit_length()
parents = [[-1] * bits for _ in range(n)]
max_path = [[0] * bits for _ in range(n)]
E = sorted(E, key=lambda x: x[2])
visited = [0] * n
MST = defaultdict(list)
total_w = kruskal(E)


q = deque([0])
depths[0] = 1
parents[0][0] = 0

while q:
    i = q.popleft()
    di = depths[i]
    for j, c in MST[i]:
        if depths[j] == 0:
            q.append(j)
            depths[j] = di + 1
            parents[j][0] = i
            max_path[j][0] = c

for i in range(1, bits):
    for j in range(n):
        pp = parents[j][i - 1]
        parents[j][i] = parents[pp][i - 1]
        max_path[j][i] = max(max_path[j][i - 1], max_path[pp][i - 1])

ans = [0]*m
for x, y, w in d_E:
    max_w = LCA(x, y)
    ans[d_E[x, y, w]] = total_w - max_w + w

sys.stdout.write(" ".join(map(str, ans)) + "\n")

Problem F statement

[segment tree, sort]

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

Solution

Unfortunately there is no way to get AC in python. I invented solution using two segment trees. In the first one we keep values for each coordinate, which frog is covering this coordinate. For example if we have frogs [0, 3] and [2, 4], then we have [0, 0, 0, 0, 1, 1, 1, inf, inf, ...]. We can notice that we can use segment tree with functionality:

  1. For all elements in range [r, l) apply ai = min(ai, v).
  2. Find element at index i.

Then when frog eat some mosquito, we need to update range which it covers. Also we need to keep the set of mosquitos, which were not eaten yet. We can keep them in sorted list for example. However we can use another segment tree, where we keep in element x weight of all mosquitos which we have in this index (there can be more than one). More detailed we will keep w1 + ... + wk + k value, because there can be zero mosquitos and it is matter how much of them we have. For this tree we need to perform the following operations:

  1. Set element i equal to v.
  2. Find first index of element starting from index l, such that it is >= x.

No, we do the following when we have new element (p, b).

  1. If we have element in index p in first tree equal to +inf, it means that no frog can eat it. In this case we update place_mosquito[p] and also update element in STree2.
  2. In the opposite case it means that some frog can eat this mosquito. We can find it as STree1.get(p). First, we modify range for our frog, that is extend it b values to the right. Also we update T[frog]: its tongue length and eaten[frog] += 1. Then we need to eat all mosquitos in new range if we have. First, we find the index of non-zero element in STree2. If this place is -1 or more than tongue length, we break. Also we find b2 is total weight of mosqitoes in this place. Then we modify responsibility of given frog, update T[frog]: tongue length, update eaten[frog] and finally set number of mosquitos in given place to zero and also place STree[place] equal to zero.

Here I used fact, that value of element with index place is STree2.T[place + N1], where N1 is the smallest power of two minus one, such that it is bigger than N.

Complexity

It is O((n + m) log N), where N = 10^9 is the size of sparse segment tree.

Code

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

# 1. For all elements in range [r, l) apply ai = min(ai, v)
# 2. Find element at index i
class SegmentTree1:
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.T = defaultdict(lambda: float("inf"))

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

    def modify(self, l, r, v):
        return self._modify(l, r, v, 0, 0, self.size)

    def _get(self, i, x, lx, rx):
        if rx - lx == 1:
            return self.T[x]
        mx = (lx + rx) // 2
        if i < mx:
            return min(self._get(i, 2 * x + 1, lx, mx), self.T[x])
        else:
            return min(self._get(i, 2 * x + 2, mx, rx), self.T[x])

    def get(self, i):
        return self._get(i, 0, 0, self.size)


# 1. Set element i equal to v.
# 2. First index element in tree starting from index l, which is >= x.
class SegmentTree2:
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.T = defaultdict(int)

    def _set(self, i, v, x, lx, rx):
        if rx - lx == 1:
            self.T[x] = v
            return
        mx = (lx + rx) // 2
        if i < mx:
            self._set(i, v, 2 * x + 1, lx, mx)
        else:
            self._set(i, v, 2 * x + 2, mx, rx)
        self.T[x] = max(self.T[2 * x + 1], self.T[2 * x + 2])

    def set(self, i, v):
        self._set(i, v, 0, 0, self.size)

    def first_above_(self, v, l, x, lx, rx):
        if self.T[x] < v or rx <= l:
            return -1
        if rx - lx == 1:
            return lx
        mx = (lx + rx) // 2
        res = self.first_above_(v, l, 2 * x + 1, lx, mx)
        if res == -1:
            res = self.first_above_(v, l, 2 * x + 2, mx, rx)
        return res

    def first_above(self, v, l):
        return self.first_above_(v, l, 0, 0, self.size)

XTi, T = [], []
n, m = I()
eaten = [0]*n
for i in range(n):
    x, t = I()
    XTi += [(x, t, i)]

XTi = sorted(XTi)
X = [x for x, _, _ in XTi]
T = [t for _, t, _ in XTi]
idx = [i for _, _, i in XTi]

N = max(max(X), max(T))
N1 = (1<<(N.bit_length())) - 1

STree1 = SegmentTree1(N)
STree2 = SegmentTree2(N)

for i, x, t in zip(range(n), X, T):
    STree1.modify(x, x+t+1, i)

place_mosquito = Counter()

for _ in range(m):
    p, b = I()
    frog = STree1.get(p)
    if frog == float("inf"):  # means mosquito can not be eaten
        place_mosquito[p] += 1
        STree2.set(p, b + STree2.T[p + N1] + 1)
    else:
        STree1.modify(X[frog] + T[frog] + 1, X[frog] + T[frog] + b + 1, frog)
        T[frog] += b
        eaten[frog] += 1
        while True:
            place = STree2.first_above(1, X[frog])
            if place == -1 or place > X[frog] + T[frog]: break
            b2 = STree2.T[place + N1] - place_mosquito[place]
            STree1.modify(X[frog] + T[frog] + 1, X[frog] + T[frog] + b2 + 1, frog)
            T[frog] += b2
            eaten[frog] += place_mosquito[place]
            place_mosquito[place] = 0
            STree2.set(place, 0)

ans = [0]*n
for i in range(n):
    ans[idx[i]] = (eaten[i], T[i])

for x, y in ans:
    gap = 0 if x == 0 else 1
    print(str(x) + " " + str(y))

Remark

I am wondering if this code will get AC in C++, it seems complexities are good enough here.