Problem A statement

[string, palindrome]

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

Solution

If length if more than 2 or we have 00 or 11, then we can choose palindrome, it the opposite case, no.

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 = I()
    s = input().rstrip()
    if len(s) >= 3 or s == "00" or s == "11":
        print("NO")
    else:
        print("YES")

Problem B statement

[greedy, constructive]

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

Solution

The idea is if we have say n = 28, then we have x = 16 = 10000, and if we look at the first bit, there will be adjacent pair, where it is goes from 1 -> 0 or 0 -> 1. It means, that we can not make answer smaller than 16. Also we can construct answer in the way 15 14 13 ... 0 16 17 18 ... 28: in the first part values will be <= 16, in the second as well and also 0 ^ 16 = 16.

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 = I()[0]
    x = 1<<((n-1).bit_length() - 1)
    arr = list(range(x-1, -1, -1)) + list(range(x, n))
    print(" ".join(str(x) for x in arr))

Problem C statement

[greedy]

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

Solution

The idea is that operation number 3 can be used only once. Also it can be shown that

  1. We increase a -> x, then we increase b to x | b and finally use operation 3.
  2. We increase b -> y, then we increase a to a | y and finally use uparation 3.

Complexity

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

Code

import sys
 
input = sys.stdin.readline
I = lambda: [int(x) for x in input().split()]
T = int(input())
 
for _ in range(T):
    a, b = I()
    ans = float("inf")
    for x in range(a, b + 1):
        ans = min(ans, (x | b) - b + x - a + (x != b))
 
    for y in range(b, (a|b) + 1):
        ans = min(ans, (a | y) - b + (a != y))
 
    print(ans)

Problem D statement

[sparse table, math, segment tree, intervals, binary search, dp, greedy]

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

Solution

The idea is that gcd(xk, ..., xl) will decrease when l increased. For every element l find the biggest r, such that gcd(xk, ..., xl) >= r - l + 1 using binary search and sparse table (gcd have properties for this) (or segment tree). We call segment bad if we have equality. Then the idea is find all bad segments: we have no more than n of them.

After this we can use greedy strategy with dp: dp[i] = dp[i-1] if end is not occupied and dp[ints[i-1]] + 1 if we have end in this point - hopefully we can have only one end for each segment.

Complexity

Time complexity is O(n log n log A), where log A here because we have gcd.

Code

from math import gcd
import sys
input = sys.stdin.readline
I = lambda: [int(x) for x in input().split()]

class RangeQuery:
    def __init__(self, data, func):
        self.func = func
        self._data = _data = [data]
        i, n = 1, len(_data[0])
        while 2 * i <= n:
            prev = _data[-1]
            _data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
            i <<= 1

    def query(self, L, R):
        depth = (R - L).bit_length() - 1
        return self.func(self._data[depth][L], self._data[depth][R - (1 << depth)])

n = int(input())
arr = I()
STable = RangeQuery(arr, gcd)
ints = {}

for i in range(n):
    beg, end = i, n
    while beg + 1 < end:
        mid = (beg + end)//2
        if STable.query(i, mid + 1) >= mid - i + 1:
            beg = mid
        else:
            end = mid

    if STable.query(i, end) == end - i:
        ints[end - 1] = i

dp = [0] * (n + 1)
for i in range(1, n + 1):
    dp[i] = dp[i-1] if i-1 not in ints else dp[ints[i-1]] + 1

print(" ".join(str(x) for x in dp[1:]))

Problem E statement

[]

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

Solution

Complexity

Code