Here is the link to the contest. All problems are from Codeforces' problemset.
A. The Coordinate Challenge
We can divide the given string into substrings of length 1, 2, 3, 4, ... and take the first character from each subarray. Since we don't have to actually generate the substrings, we can just take the first character in $$$t$$$, jump one step and take a character, then jump two steps and take a character, then three steps, ...
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
t = input()
jump = 1
i = 0
s = ""
while i < n:
s += t[i]
i += jump
jump += 1
print(s)
B. Excluded Integer Sum Problem
Let's use the greedy solution: we will go through the digits in decreasing order. If the sum of $$$s$$$ we need to dial is greater than the current digit, we add the current digit to the end of the line with the answer.
Note that in this way we will always get an answer consisting of the minimum possible number of digits, because we are going through the digits in descending order.
Suppose that the resulting number is not optimal. Then some digit can be reduced, and some digit that comes after it can be increased, in order to save the sum (we can not increase the digit before it, as then we get a number greater than the current one). Two variants are possible.
We want to increase the digit $$$x$$$ to $$$x+1$$$, but then it becomes equal to the digit following it, or exceeds the value $$$9$$$. Then we can't increment that digit. Otherwise, in the first step, we can get $$$x+1$$$ instead of $$$x$$$, but since we are going through the digits in decreasing order, we cannot get the value of $$$x$$$ in that case. Contradiction.
T = int(input())
for _ in range(T):
n = int(input())
ans = []
for digit in range(9, 0, -1):
if n >= digit:
ans.append(digit)
n -= digit
ans.reverse()
print(*ans, sep="")
C. Filling the Plate
To begin with, let's note that potions of types $$$p1,p2,…,pk$$$ are essentially free, so we can replace their costs with 0.
Let $$$ans_i$$$ be the answer for the $$$i-th$$$ potion. Each potion can be obtained in one of two ways: by buying it or by mixing it from other potions. For mixing, we obtain all the required potions at the minimum cost. That is, if there is a way to mix a potion of type $$$i$$$, then the answer for it is either $$$c_i$$$ or the sum of answers for all $$$e_i$$$. Since the graph in the problem does not have cycles, this can be done by a simple breadth-first or depth-first search.
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
def solve():
n, k = map(int, input().split())
cost = [0] + list(map(int, input().split()))
nums = set(map(int, input().split()))
graph = defaultdict(list)
degree = [0] * (n + 1)
future = [0] * (n + 1)
ans = [0] * (n + 1)
for i in range(1, n + 1):
line = list(map(int, input().split()))
m, edges = line[0], line[1:]
if i in nums:
continue
degree[i] = m
for a in edges:
graph[a].append(i)
queue = deque()
for node in range(1, n + 1):
if node in nums:
queue.append(node)
elif degree[node] == 0:
ans[node] = cost[node]
queue.append(node)
while queue:
node = queue.popleft()
for child in graph[node]:
degree[child] -= 1
future[child] += ans[node]
if degree[child] == 0:
queue.append(child)
ans[child] = min(cost[child], future[child])
print(*ans[1:])
q = int(input())
for _ in range(q):
solve()
D. Binyam and Kalkidan
The answer lies between $$$max(a)$$$ and $$$max(a) + min(n, k)$$$
We can binary search for the answer?
We will do binary search on the answer. The lower bound can be set to $$$max(a_{1},…,a_{n})$$$, while $$$max(a_{1},…,a_{n}) + min(n, k)$$$ is enough for the upper bound.
Let $$$b$$$ be some resulting array after performing at most $$$k$$$ operations.
Suppose for some $$$x$$$ we want to check if we can get $$$max(b_{1},…,b_{n})≥x$$$ in at most $$$k$$$ operations. That is, there must exist some index $$$i$$$ such that $$$b_{i}≥x$$$. So, let's iterate $$$i$$$ from $$$1$$$ to $$$n$$$ and check if it possible to have $$$b_{i}≥x$$$ in at most $$$k$$$ operations.
Let $$$f(i,y)$$$ be the minimum number of operations needed to make $$$b_{i}≥y$$$. Then:
- $$$f(i,y)=0$$$ for all $$$y≤a_{i}$$$,
- $$$f(i,y)=y−a_{i}+f(i+1,y−1)$$$ for all $$$1≤i<n$$$ and $$$y>a_{i}$$$,
- $$$f(i,y)=+∞$$$ for $$$i=n$$$ and all $$$y>a_{i}$$$.
It is easy to see that calculating $$$f(i,x)$$$ takes $$$O(n)$$$ time for one call in the worst case.
Thus, our check consists of comparing $$$f(i,x)$$$ and $$$k$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$. If at least one of the values is $$$≤k$$$, it is possible to have some $$$b_{i}≥x$$$ in at most $$$k$$$ operations and we increase the lower bound in the binary search after updating the current answer. Otherwise, it is impossible and we decrease the upper bound.
Time Complexity: $$$O(n^2⋅log(A))$$$, where A is the minimum of $$$n$$$ and $$$k$$$.
import sys
input = lambda: sys.stdin.readline().rstrip()
def check(max_val):
# consider each index if it can be where we can achieve this 'max_val'
for i in range(n):
cost = 0
cur_val = max_val
for j in range(i, n):
# if it is the last index and in needs to be incremented
# we are not allowed to increase the last number
# we can get away by making cost = k + 1, it will not return True
if a[j] < cur_val and j == n - 1:
cost = k + 1
break
if a[j] >= cur_val:
break
cost += cur_val - a[j]
next_val = max(cur_val - 1, 0)
cur_val = next_val
if cost <= k:
return True
return False
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
a = list(map(int, input().split()))
low = max(a)
high = max(a) + min(k, n)
while low <= high:
mid = low + (high - low)//2
if check(mid):
low = mid + 1
else:
high = mid - 1
print(high)
E. Rap vs Pop
We don't need to ever go over an edge more than once, since going over an edge twice cancels out (since $$$a$$$ $$$XOR$$$ $$$a$$$=0 for all $$$a$$$)
Let's ignore the teleporting, and decide how to find the answer. Note that we don't need to ever go over an edge more than once, since going over an edge twice cancels out (since $$$a$$$ $$$XOR$$$ $$$a$$$=0 for all $$$a$$$). In other words, the only possible value of $$$x$$$ equals the XOR of the edges on the unique path from $$$a$$$ to $$$b$$$. We can find it through a DFS from $$$a$$$, continuing to keep track of XORs as we move to each adjacent node, and XORing it by the weight of the corresponding edge as we travel across it.
Now let's include the teleport. It means that we travel from $$$a→c$$$, then teleport to $$$d$$$, and go from $$$d→b$$$, for some nodes $$$c$$$ and $$$d$$$. Also, we cannot pass $$$b$$$ on the path from $$$a→c$$$.
Again, note that the value of $$$x$$$ is fixed on each of the paths from $$$a→c$$$ and $$$d→b$$$, since there is a unique path between them. Let $$$x_1$$$ be the XOR of the first path and $$$x_2$$$ be the XOR of the second. Then we need $$$x_1 XOR x_2=0⟹x_1=x_2$$$. So we need to find if there are two nodes $$$c$$$, $$$d$$$ such that the XORs from $$$a$$$ and $$$b$$$ to those nodes are the same. To do this, we can do our $$$DFS$$$ from before, but instead run one $$$DFS$$$ from $$$a$$$ and another from $$$b$$$, and check if any two values are the same.
Make sure not to include nodes past $$$b$$$ while we look for $$$c$$$ on our DFS from $$$a$$$. The time complexity is $$$O(nlogn)$$$.
import sys
from collections import defaultdict
def solve():
n, a, b = map(int, sys.stdin.readline().strip().split())
graph = defaultdict(list)
for _ in range(n - 1):
u, v, w = map(int, sys.stdin.readline().strip().split())
graph[u].append((v, w))
graph[v].append((u, w))
pref1 = [-1] * (n + 1)
pref1[a] = 0
stack = [(a, -1)]
while stack:
node, par = stack.pop()
for ne, w in graph[node]:
if ne != par:
if ne == b:
if w ^ pref1[node] == 0:
return "YES"
continue
pref1[ne] = w ^ pref1[node]
stack.append((ne, node))
ss = set(pref1)
pref2 = [-1] * (n + 1)
pref2[b] = 0
stack = [(b, -1)]
while stack:
node, par = stack.pop()
for ne, w in graph[node]:
if ne != par:
pref2[ne] = w ^ pref2[node]
if pref2[ne] in ss:
return "YES"
stack.append((ne, node))
return "NO"
t = int(sys.stdin.readline().strip())
for _ in range(t):
print(solve())
