Problem A statement

[greedy, string]

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

Solution

For every 00 we need to insert two 11 in betwen. For every 010, we need to insert one more 1 inside.

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())
    ans = 0
    s = input().rstrip()
    for i in range(n - 1):
        if s[i:i+2] == "00":
            ans += 2
    for i in range(n - 2):
        if s[i:i+3] == "010":
            ans += 1
    print(ans)

Problem B statement

[math, combinatorics]

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

Solution

It can be shown that number of solutions is (n//2)!^2.

Complexity

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

Code

I = lambda: [int(i) for i in input().split()]
 
from math import factorial
M = 998244353
 
T = int(input())
for _ in range(T):
    n = int(input())
    if n % 2 == 1:
        print(0)
    else:
        print((factorial(n//2)**2) % M)

Problem C statement

[permutation, greedy, string]

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

Solution

The idea is that:

  1. First, we must have exactly one 1, rotate permutation to this place, it corresponds to the biggest element.
  2. Each next element must be not more than i + 1 and not more than previous element plus one.

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())
    arr = I()
    if arr.count(1) != 1:
        print("NO")
    else:
        idx = arr.index(1)
        arr = arr[idx:] + arr[:idx]
        good = all(arr[i] <= min(i + 1, arr[i - 1] + 1) for i in range(1, n))
        print("YES") if good else print("NO")

Problem D statement

[divide and conquer, recursion, bit manipulation, XOR]

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

Solution

Notice, that if number of values is odd, we can directly find x: evaluate xor(l, ..., r) ^ xor(A). If it is odd, we can have two cases:

  1. 3, [4, 5], [6, 7], 8, here we can split all values into pairs, but two of them will not have pair. Notice, that if we have a^b = 1 then (a^x)^(b^x) = 1 and to the opposite. So, we can find all pairs with a^b = 1 and then if we did not find pair, it will be our candidates. Also we have border case when we have two elements.
  2. [4, 5], [6, 7], [8, 9], then it this case we can divide everything by 2 and do recursively.

Complexity

It is O(n) for time, because we have equation T(n) = O(n) + T(n//2). Space is also O(n).

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
 
def check(A, l, r):   # length of A is r - l + 1
    if (r - l) % 2 == 0:
        ans = 0
        for i in range(l, r + 1): ans ^= i
        for x in A: ans ^= x
        return ans
    else:
        A_set = set(A)
        borders = []
        for x in A_set:
            if (x ^ 1) not in A_set:
                borders += [x^l]
 
        if r == l + 1:
            borders = [A[0]^l, A[1]^l]
 
        if len(borders) == 2:
            for cand in borders:
                if set([cand^i for i in range(l, r + 1)]) == A_set: return cand
        else:
            A2 = list(set([x//2 for x in A]))
            return check(A2, l//2, (r-1)//2)*2
 
T = int(input())
for _ in range(T):
    l, r = I()
    arr = I()
    print(check(arr, l, r))

Problem E statement

[game, segment tree, binary indexed tree, greedy]

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

Solution

High level idea is to use the idea of winning and loosing positions, here you need to use a bit of game theory. Also we use the idea of rotation of grid by 45 degrees. The position with the biggest value is winning. Let us maintain a set $S$ that stores the pairs $(i′,j′)$ of winning positions, then our operations are:

  1. Adding point $(i, j)$ to $S$
  2. Given $(i, j)$, check if for all $(i′, j′)$ in $S$, $ abs(i-i′) + abs(j-j′) \leqslant k$.

Key notion here is that that

\[|i-i′|+|j-j′| \leqslant k \Leftrightarrow \max(|(i+j)-(i′+j′)|,|(i-j)-(i′-j′)|)\leqslant k,\]

so we only need to store the minimum and maximum of all $(i+j)$ and $(i-j)$.

Complexity

It is O(n^2) for time and 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
 
n, k = I()
v = [I() for _ in range(n)]
m = n * n
x, y = [0] * m, [0] * m
 
for i, row in enumerate(v):
    for j, val in enumerate(row):
        x[val - 1] = i
        y[val - 1] = j
 
ans = [["G"] * n for _ in range(n)]
xm, ym = x[-1], y[-1]
mi1 = ma1 = xm - ym
mi2 = ma2 = xm + ym
 
for xi, yi in zip(x[::-1], y[::-1]):
    d1, d2 = xi - yi, xi + yi
    if max(abs(mi1 - d1), abs(ma1 - d1), abs(mi2 - d2), abs(ma2 - d2)) <= k:
        mi1 = min(mi1, d1)
        ma1 = max(ma1, d1)
        mi2 = min(mi2, d2)
        ma2 = max(ma2, d2)
        ans[xi][yi] = "M"
 
for row in ans:
    sys.stdout.write("".join(row) + "\n")

Solution 2

There is also solution using segment trees/binary indexed trees. The idea is to start again from the biggest values and when we have new element, check how many M elements we have in square of size k (rotated by 45 degrees).

Complexity

It is O(n^2 log^2n) for time and O(n^2) for space, and it gives TLE in python.

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 BIT_2d:
    def __init__(self, m, n):
        self.sums = [[0] * (n + 1) for _ in range(m + 1)]
        self.m, self.n = m, n

    def update(self, i, j, delta):
        while i <= self.m:
            j2 = j
            while j2 <= self.n:
                self.sums[i][j2] += delta
                j2 += j2 & (-j2)
            i += i & (-i)

    def query(self, i, j):
        res = 0
        while i > 0:
            j2 = j
            while j2 > 0:
                res += self.sums[i][j2]
                j2 -= j2 & (-j2)
            i -= i & (-i)
        return res

n, k = I()
v = [I() for _ in range(n)]
m = n * n
x, y = [0] * m, [0] * m

for i, row in enumerate(v):
    for j, val in enumerate(row):
        x[val - 1] = i
        y[val - 1] = j

ans = [["G"] * n for _ in range(n)]
bit = BIT_2d(2*n, 2*n)
cc = 0

for i, j in zip(x[::-1], y[::-1]):
    x, y = i + j, i - j + n - 1
    xa, ya, xb, yb = max(0, x - k), max(0, y - k), min(2*n - 1, x + k), min(2*n - 1, y + k)
    sm = bit.query(xb, yb) - bit.query(xa - 1, yb) - bit.query(xb, ya - 1) + bit.query(xa - 1, ya - 1)
    if sm == cc:
        ans[i][j] = "M"
        bit.update(x, y, 1)
        cc += 1

for row in ans:
    sys.stdout.write("".join(row) + "\n")

Problem F statement

[]

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

Solution

Complexity

Code