Problem A statement

[string]

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

Solution

We can notice that if string is palindrome or we have 0 steps, there will be 1 option and 2 optoins in the opposite case.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(x) for x in input().split()]
 
T = int(input())
for _ in range(T):
    n, k = I()
    s = input().rstrip()
    if s == s[::-1] or k == 0:
        print(1)
    else:
        print(2)

Problem B statement

[math]

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

Solution

What we need to notice here is invariant: is parity of our number will depend on x, y and sum(t).

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(x) for x in input().split()]
 
T = int(input())
for _ in range(T):
    n, x, y = I()
    arr = I()
    t = sum(arr) % 2
    if (x + y + t) % 2 == 0:
        print("Alice")
    else:
        print("Bob")

Problem C statement

[math, constructive]

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

Solution

First of all notice, that all numbers in each row must have the same parity. If n % 2 == 0, we can construct example, using odd numbers for the first half or rows and even for the second half. If k == 1, it is also possible to construct example. In the other cases we can prove, that it is not possible: we if n % 2 == 1 and m % 2 == 1, then we can not have numbers of the same parity in each row. If n % 2 == 1 and m % 2 == 0, then we can not have sum of numbers divisible by m in each row.

Complexity

It is O(mn) for time and space.

Code

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()]
 
T = int(input())
for _ in range(T):
    n, k = I()
    ans = []
    if n % 2 == 0:
        even = list(range(1, n*k, 2))
        odd  = list(range(2, n*k+1, 2))
        ans = [even[i*k:i*k+k] for i in range(n//2)] + [odd[i*k:i*k+k] for i in range(n//2)]
    elif n % 2 == 1 and k == 1:
        ans = [[i] for i in range(1, n+1)]
    else:
        ans = []
 
    if not ans:
        print("NO")
    else:
        print("YES")
        for line in ans:
            print(" ".join(str(x) for x in line))

Problem D statement

[interactive]

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

Solution

The idea is the following: if we have 4 numbers, we can eliminate two of them, using 4 operations: for this we need to check all 4 possible combinations and after we sorte them we can find that values in the middle can not be zeroes. We cobmine this until we have 4 or 5 numbers. If we have 5, we eliminate only one number. When we have 4`, eliminate two once again and return the last two numbers.

Complexity

It is O(n) for time and <= 2n - 2 operations.

Code

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

def q():
    val = int(input())
    return val

def p(v):
    print(v)
    sys.stdout.flush()

def eliminate(i1, i2, i3, i4):
    s1, s2, s3, s4 = str(i1), str(i2), str(i3), str(i4)
    V = []
    for i, x, y, z in (i1, s2, s3, s4), (i2, s1, s3, s4), (i3, s1, s2, s4), (i4, s1, s2, s3):
        p("? " + x + " " + y + " " + z)
        V += [(q(), i)]
    V = sorted(V)
    return V[-1][1], V[-2][1]

T = int(input())
for _ in range(T):
    n = int(input())
    indexes = list(range(1, n+1))
    while len(indexes) > 5:
        a, b = eliminate(*indexes[-4:])
        indexes.remove(a)
        indexes.remove(b)
        
    if len(indexes) == 5:
        a, _ = eliminate(*indexes[-4:])
        indexes.remove(a)

    a, b = eliminate(*indexes[-4:])
    indexes.remove(a)
    indexes.remove(b)

    p("! " + " ".join(str(x) for x in indexes) + "\n")

Problem E statement

[graph, graph algo]

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

Solution

What we need to construct in this problem is eulerian loop (or several loops in fact). Let us create bipartite graph, where the first part is index of array and the second is values in this array. We can have multiple edges in our graph. Then we need to traverse our graph with hierholzer’s algorithm and find paths. Finally, we need to reconstruct anwer: for edge going from second part to the first we put L, for the opposite we put R.

Complexity

It is O(n) for time and space, where n is total length of all arrays.

Code

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

G = defaultdict(Counter)
places = defaultdict(set)
ans = defaultdict(list)

m = int(input())
for i in range(m):
    _ = input()
    arr = I()
    for j, x in enumerate(arr):
        G[i][x + m] += 1
        G[x + m][i] += 1
        places[x + m, i].add(j)
    ans[i] = ["X"] * len(arr)

if all(sum(G[i].values()) % 2 == 0 for i in G):
    visited = set()
    for start in G:
        if start in visited: continue
        stack = [start]
        path = []

        while stack:
            v = stack[-1]
            if G[v]:
                u = next(iter(G[v].items()))[0]
                stack.append(u)
                G[v][u] -= 1
                if G[v][u] == 0: G[v].pop(u)
                G[u][v] -= 1
                if G[u][v] == 0: G[u].pop(v)
            else:
                path.append(stack.pop())

        visited |= set(path)
        for x, y in zip(path, path[1:]):
            l = "L" if x < y else "R"
            x, y = min(x, y), max(x, y)
            idx = places[y, x].pop()
            ans[x][idx] = l

    print("YES")
    for i in range(m):
        print("".join(ans[i]))
else:
    print("NO")

Problem F statement

[math, accumulate]

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

Solution

The idea here is to use special type of differences for our array, such that we can recalculate values on range in O(1) time. First of all we work with C = A - B array. Then if we create array D[i] = C[i] - C[i-1] - C[i-2], it happens that array D can be updated in O(1) time! All we need to do is D[l] += 1, D[r + 1] -= F[r - l + 2], D[r + 2] -= F[r - l + 1], where F are Fibonacci numbers. Similar logic for queries on array B, we need to use the opposite signs. Also we precalculate fibonacci numbers and we keep cnt: number of non-zero values in our array D: we are happy if we have 0 of them.

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(x) for x in input().split()]
 
def update(i, d, cnt):
    cnt -= (unfib[i] != 0)
    unfib[i] = (unfib[i] + d) % MOD
    cnt += (unfib[i] != 0)
    return cnt
 
n, q, MOD = I()
a = I()
b = I()
diff = [0, 0] + [(y - x) % MOD for x, y in zip(a, b)]
fib = [1] * n
for i in range(2, n):
    fib[i] = (fib[i - 1] + fib[i - 2]) % MOD
 
unfib = [(diff[i+2] - diff[i + 1] - diff[i]) % MOD for i in range(n)]
 
cnt = sum(x != 0 for x in unfib)
result = []
for _ in range(q):
    c, l, r = input().split()
    l, r = int(l) - 1, int(r) - 1
    sign = 1 if c == 'A' else -1
    cnt = update(l, -sign, cnt)
    if r + 1 < n: cnt = update(r + 1, sign * fib[r - l + 1], cnt)
    if r + 2 < n: cnt = update(r + 2, sign * fib[r - l], cnt)
    result += ["YES" if cnt == 0 else "NO"]
 
sys.stdout.write("\n".join(result))