Problem A statement

[greedy]

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

Solution

The idea is to have the big numbers in B and small in A. Then we can prove that it is optimal. Because one of the terms will be max(A, B) and we want to make the other as small as possible.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
 
T = int(input())
for _ in range(T):
    n = int(input())
    A = I()
    B = I()
    for i in range(n):
        if A[i] > B[i]:
            A[i], B[i] = B[i], A[i]
 
    ans = max(A) * max(B)
    print(ans)

Problem B statement

[greedy]

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

Solution

Again greedy idea: if we look at the last element, on the next step we can make 2 last elements equal, then 4 and so on. However, in the case like 1 2 3 4 4 4 we already have some elements equal, so we can double them. In general we look for the last element which is not equal to last and continue this until all elements are the same.

Complexity

It is O(n log n), because we will have no more than log n iterations.

Code

I = lambda: [int(i) for i in input().split()]
 
def first_not_x(arr, val):
    for i in range(len(arr)):
        if arr[i] != val:
            return i
    return len(arr)
 
T = int(input())
for _ in range(T):
    n = int(input())
    arr = I()
    arr = arr[::-1]
    x = arr[0]
    ans = 0
    while True:
        l = first_not_x(arr, x)
        if l == n: break
        for i in range(l, min(n, 2*l)):
            arr[i] = x
        ans += 1
 
    print(ans)

Problem C statement

[bit manipulation, constructive]

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

Solution

In this problem we need to construct answer.

  1. If n <= 4, than we can have solutions for cases 0, 1, 2 and we can consturct them and do not have solution for 3.
  2. If n > 4, then we can construct answers for all k = 0, 1, ..., n-1, however for k = n - 1 solution is a bit different: If k != n - 1, then we make pairs (k, n - 1) and (n - k - 1, 0) and all other pairs have sum of elements n-1, that is their AND will be equal to 0. If we have k = n- 1, we create pairs (n-1, n-2), (1, 3) and (n-4, 0) and all other pairs have the same logic.

Complexity

It is O(n) for time and space.

Code

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()]
 
T = int(input())
for _ in range(T):
    n, k = I()
    if k == n - 1:
        if n <= 4:
            print(-1)
        else:
            print(n-1, n-2)
            print(1, 3)
            print(n-4, 0)
            for i in range(n // 2):
                if i in [0, 1, 3, n-1, n-2, n-4]: continue
                print(i, n - 1 - i)
    else:
        if k == 0:
            print(k, n - 1)
        else:
            print(k, n - 1)
            print(n - k - 1, 0)
        for i in range(n//2):
            if i in [0, k, n-1, n - k - 1]: continue
            print(i, n - 1 - i)

Problem D statement

[greedy, two pointers]

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

Solution

Again greedy! Let us denote good is number of values in [x, y] in our array and bad is number of other values. Then we have good + bad = n and good - bad > k, because in each group number of good elements at least one bigger. Form this we have good >= (n + k)//2. What we do now is to sort all values in array and find the smallest range for good number of values. It happen than we can construct answer! We do it in greedy way: start from the first element and create groups, when number of good elements becomes bigger than number of bad elements, we finish this group. In this way in first k - 1 groups we have exactly number of good elements exactly one bigger than number of bad elements, so in the last group we will also have correct number of good and bad elements.

Complexity

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

Code

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

T = int(input())
for _ in range(T):
    n, k = I()
    arr = I()
    arr2 = sorted(arr)
    t1, t2 = min(arr), max(arr)
    t = (t2 - t1, t1, t2)
    good = (n + k + 1) // 2 - 1  # number of good values we need.
    for x in range(n - good):
        t = min(t, (arr2[x + good] - arr2[x], arr2[x], arr2[x + good]))

    ans, bal = [], 0
    for i in range(n):
        bal += 2 * int(t[1] <= arr[i] <= t[2]) - 1
        if bal == 1:
            bal = 0
            ans += [i+1]

    ans = [0] + ans[:k-1] + [n]
    print(t[1], t[2])
    for x, y in zip(ans, ans[1:]):
        print(x + 1, y)

Problem E statement

[intervals, greedy, dp, sweep line]

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

Solution

Actually, this is problem about intervals. First of all, what is matter is the first and the last occurunces for every color, all in the middle can be made 1 without any problems. Also, let us minimize number of 0 instead of maximizing number of 1. Let us look at our intervals, they can be separated into connected components.

It can be shown, that for each component the answer is the smallest number of intervals which fully cover this interval + 1, however proof is not so easy.

Complexity

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

Code

I = lambda: [int(i) for i in input().split()]
n = int(input())
arr = I()
last = {x: i for i, x in enumerate(arr)}
 
lastest, covered, ans = 0, 0, 0
for i, x in enumerate(arr):
    lastest = max(lastest, last[x])
    if covered > i:
        ans += 1
    else:
        covered = lastest
 
print(ans)

Problem F statement

[]

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

Solution

Complexity

Code