Problem A statement

[geometry, math]

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

Solution

We can see, that every side can be reached only if it is not horizontal and we have another point below it, like in the image in problem statement.

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):
    x1, y1 = I()
    x2, y2 = I()
    x3, y3 = I()
    P = [(x1, y1), (x2, y2), (x3, y3)]
    ans = 0
    for i in range(3):
        x1, y1 = P[i]
        x2, y2 = P[(i + 1) % 3]
        x3, y3 = P[(i + 2) % 3]
        if y1 == y2 and y3 < y1:
            ans += ((x1 - x2)**2 + (y1 - y2)**2)**0.5
 
    print(ans)

Problem B statement

[greedy, counter]

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

Solution

Use counter to see what frequencies we have. Imagine, that we have (1, 2, 2, 3, 3, 3, 4, 4, 4). Then for k = 1, answer is 4. Then we can keep this answer 3 more steps: to make it (1), (2, 2), (3, 3, 3), (4, 4, 4). Then we need to split equal numbers and answer will increas by one.

Complexity

It is O(n) for time and space.

Code


I = lambda: [int(i) for i in input().split()]
from collections import Counter, deque
 
t = int(input())
for _ in range(t):
    n = int(input())
    arr = I()
    cnt = Counter(arr)
    F = cnt.values()
    ans = list(range(1, n + 1))
    for i in range(len(F)):
        ans[i] = len(F)
 
    print(" ".join(str(x) for x in ans))

Problem C statement

[greedy, sort]

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

Solution

The idea if we have smallest number t, then the only option for pair is t * x, so we check if we have it: if not, add 1 to answer, if we have, remove it. This is similar to Leetcode 0954. Array of Doubled Pairs

Complexity

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

Code

I = lambda: [int(i) for i in input().split()]
from collections import Counter, deque
 
t = int(input())
for _ in range(t):
    n, x = I()
    arr = I()
    arr = sorted(arr)
    cnt = Counter(arr)
    ans = 0
    for num in arr:
        if cnt[num] == 0: continue
        if cnt[x * num] == 0:
            ans += 1
        else:
            cnt[x * num] -= 1
        cnt[num] -= 1
 
    print(ans)

Problem D statement

[constructive, array]

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

Solution

The idea is the following, imagine that we have [1, 2, 3, 1, ... ] array, then we can make it [2, 3, ... ] in not more than n steps. How we do it: [1, 2, 3, 1, 2, 2, ... ] -> [1, 2, 3, 1, 2, 3, 3, 2, ... ], and now we have repeating [1, 2, 3] in the beginning and [3, 2, ... ] after it. So, the stragety is the following: find element equal to x[0] and remove pair. Notice that if frequency of some element is odd, we remove -1.

Complexity

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

Code

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

t = int(input())
for _ in range(t):
    n = int(input())
    arr = I()
    x = Counter(arr).values()
    if any(i % 2 == 1 for i in x):
        print("-1")
    else:
        start = 0
        q = 0
        inserts = []
        lens = []
        for i in range(n//2):
            x = arr[0]
            for j in range(1, len(arr)):
                if arr[j] == x:
                    idx = j
                    break
            for j in range(1, idx):
                inserts += [[start + idx + j, arr[j]]]
            lens += [idx * 2]
            q += idx - 1
            start += 2 * idx
            arr = arr[1:idx][::-1] + arr[idx + 1:]

        print(q)
        for p, c in inserts:
            print(p, c)
        print(len(lens))
        print(" ".join(str(x) for x in lens))

Problem E statement

[union find, segment tree, intervals]

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

Solution

The idea is to keep set of people we for sure know they are not ill in DSU. Imagine, that n = 10 and we know that persons 1, 2, 3, 6, 7 are not ill. Then we keep them as [1, 2, 3, 4], [5], [6, 7, 8] sets. Here sets with size >1 are not ill persons and sets with size 1 are people that can be ill. We will keep the following information for every set:

  1. lft is the leftest element in set. Notice that we always will have continous subarray as our sets.
  2. rgh is the rightest element.
  3. lst[set] is the smallest right side such that range [i, lst[i]], where i in lst[set]` was in queries and about which we now they have at least one ill person.

Then:

  1. When we see new query range with ill persons, update dsu.lst.
  2. If we have query that all persons are not ill, we need to update some ranges. We only going to update elements which we did not update before. Imagine, that we have [1, 2, 3], [4], [5], [6, 7] and we have new query [2, 9]. Then we need to update 3 -> 4, 4 -> 5, 5 -> 6, 7 -> 8, 8 -> 9. To efficiently union only these pairs, each time we have set of size more than one, we jump directly to its end.
  3. If find(j - 1) == find(j), then this person is not ill.
  4. If find_lft(find_lst(j - 1)) == j, than this person is ill. We look at set(j - 1): elements before j for which we know that person is not ill, so we have ...00...00?00...00... Then find_lst(j - 1) is the smallest index of the right end, where left end is from left zeroes. If it lies in the right group of zeroes, we are happy. It means that find_lft(find_lst(j - 1)) = j.

Complexity

It is $O(n \cdot \alpha(n))$ for time and $O(n)$ for space.

Code

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

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.rnk = [0] * n
        self.lft = list(range(n))
        self.rgh = list(range(n))
        self.lst = [n - 1] * 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):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if self.rnk[x] > self.rnk[y]:
            x, y = y, x
        self.p[x] = self.p[y]
        if self.rnk[x] == self.rnk[y]:
            self.rnk[y] += 1
        self.lft[y] = min(self.lft[x], self.lft[y])
        self.rgh[y] = max(self.rgh[x], self.rgh[y])
        self.lst[y] = min(self.lst[x], self.lst[y])
        return True

    def find_lft(self, x):
        return self.lft[dsu.find(x)]

    def find_rgh(self, x):
        return self.rgh[dsu.find(x)]

    def find_lst(self, x):
        return self.lst[dsu.find(x)]

n, q = I()
dsu, ans = DSU(n + 2), []
for _ in range(q):
    args = I()
    if args[0] == 0:
        l, r, x = args[1:]
        idx_l = dsu.find(l - 1)
        idx_r = dsu.find(r)
        if x:
            dsu.lst[idx_l] = min(dsu.lst[idx_l], r)
        else:
            beg, end = dsu.rgh[idx_l], dsu.lft[idx_r]
            while beg < end:
                dsu.union(beg, beg + 1)
                beg = dsu.find_rgh(beg)
    else:
        j = args[1]
        if dsu.find(j - 1) == dsu.find(j):
            ans += ["NO"]
        elif dsu.find_lft(dsu.find_lst(j - 1)) == j:
            ans += ["YES"]
        else:
            ans += ["N/A"]

print("\n".join(ans))

Problem F statement

[]

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

Solution

Complexity

Code