math
constuctive
string
interactive
graph
graph algo
]
Codeforces contest 1634
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))