Thank you all for participating, I hope you enjoyed the problems! You can rate the problems of the round in the corresponding spoilers. Codes will be added after system testing.
Hint 1
For each index $$$i$$$, it makes no sense to perform the operation $$$\ge 2$$$ once, since applying the operation with the same index twice does not change anything.
Hint 2
Condition $$$a_n = \max(a_1, a_2, \ldots, a_n)$$$ is equivalent to $$$a_i \leq a_n$$$ for all $$$i$$$. So for each index $$$i$$$ there are only 2 conditions: $$$a_i \leq a_n$$$ and $$$b_i \leq b_n$$$.
Tutorial
Tutorial is loading...
Solution
[submission:]
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(n):
if a[i] > b[i]:
a[i], b[i] = b[i], a[i]
if a[-1] == max(a) and b[-1] == max(b):
print("YES")
else:
print("NO")
Hint 1
Let the participant with the number $$$X$$$ participate in the lottery in days $$$i_1 < i_2 < \ldots < i_k$$$. On what days could the participant $$$X$$$ be chosen as the winner so as not to break the conditions?
Hint 2
If there are several candidates for the lottery winner on the day of $$$i$$$ (who did not participate in the days from $$$i+1$$$ to $$$m$$$), does it matter which of them we choose as a winner?
Tutorial
Tutorial is loading...
Solution
[submission:]
MAX = 50000
last = [0] * (MAX + 777)
for _ in range(int(input())):
m = int(input())
a_ = []
for day in range(m):
n = int(input())
a = list(map(int, input().split()))
for x in a:
last[x] = day
a_.append(a)
ans = [-1] * m
for day in range(m):
for x in a_[day]:
if last[x] == day:
ans[day] = x
if ans[day] == -1:
print(-1)
break
else:
print(*ans)
Hint 1
In which case 1 price tag is enough?
Hint 1.1
For any positive integers $$$x, y, z$$$, the statement ``$$$x$$$ is divisible by $$$y$$$'' equivalent to the statement ``$$$xz$$$ is divisible by $$$yz$$$'
Hint 1.2
Let's denote the total cost of all packs of candies for $$$cost$$$. Rewrite all the conditions given in the problem so that they become conditions only for the number $$$cost$$$. Hint1.1 will help in this.
Hint 2
If one price tag is enough for a set of candies, then if you remove any type of candy from this set, one price tag will still be enough. This is a reason to think about greedy.
Tutorial
Tutorial is loading...
Solution
[submission:]
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
for _ in range(int(input())):
n = int(input())
a = []
b = []
for i in range(n):
ai, bi = map(int, input().split())
a.append(ai)
b.append(bi)
g = 0
l = 1
ans = 1
for i in range(n):
g = gcd(g, a[i] * b[i])
l = lcm(l, b[i])
if g % l:
ans += 1
g = a[i] * b[i]
l = b[i]
print(ans)
Hint 1
Express $$$\max\limits_{1 \leq l \leq r \leq n} \lvert a_l+a_{l+1}+\ldots+a_r\rvert$$$ in a simpler way.
Hint 1.1
Use the prefix sums of the array $$$a$$$.
Hint 2
Build the answer starting from an empty array. If you add numbers to the response so that the prefix sum is always in the half-interval $$$(\min(a), \max(a)]$$$, the resulting array will fit the condition. How to do it? Remember that the sum of the array is $$$0$$$.
Tutorial
Tutorial is loading...
Solution
[submission:]
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if max(a) == 0:
print("No")
else:
print("Yes")
prefix_sum = 0
pos = []
neg = []
for x in a:
if x >= 0:
pos.append(x)
else:
neg.append(x)
ans = []
for _ in range(n):
if prefix_sum <= 0:
ans.append(pos[-1])
pos.pop()
else:
ans.append(neg[-1])
neg.pop()
prefix_sum += ans[-1]
print(' '.join(list(map(str, ans))))
Hint 1
Estimate from above the number of changes for which you can make a multitest from an arbitrary array.
Hint 2
How to check for each suffix whether it is a multitest by itself (without changes)?
Hint 2.1
This is done using one-dimensional dynamic programming by suffixes.
Hint 3
Let's say you want to check if an array can turn into a multitest for $$$1$$$ change. Find all the elements that could potentially be changed (all the elements are such that changing them could lead to the array becoming a multitest without being it initially). For each of them, you need to determine whether it is possible to make a change that turns array into multitest. One-dimensional dynamic programming by suffixes will help to take into account all these variants of change.
Tutorial
Tutorial is loading...
Solution
[submission:]
N = 300777
a = [0] * N
go = [0] * N
good_chain = [0] * N
chain_depth = [0] * N
suf_max_chain_depth = [0] * N
ans = ""
for _ in range(int(input())):
n = int(input())
a = [0] + list(map(int, input().split()))
chain_depth[n + 1] = 0
suf_max_chain_depth[n + 1] = 0
curr_max_chain_depth = 0
for i in range(n, 0, -1):
go[i] = i + a[i] + 1
if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]):
good_chain[i] = True
else:
good_chain[i] = False
chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)]
suf_max_chain_depth[i] = 1 + curr_max_chain_depth
if go[i] <= n + 1:
suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]])
if good_chain[i]:
curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i])
for i in range(1, n):
if good_chain[i + 1] and chain_depth[i + 1] == a[i]:
ans += "0 "
elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]:
ans += "1 "
else:
ans += "2 "
ans += '\n'
print(ans)
1798F - Gifts from Grandfather Ahmed
Hint 1
Let's say the box you selected will be sent to the largest class. Then if this class has a size of $$$s$$$, you can send any $$$s-1$$$ from the available boxes there. So you can not worry about this class, and pick boxes for the rest, always having as potential options $$$s-1$$$ additional boxes. Plenty of room for maneuver.
Hint 2
The solution exists for any valid input
Hint 3
After Hint2 think about some specific inputs. You know, they always have a solution. This should inspire you.
Hint 3.1
$$$k = 2, s_1 = s_2$$$.
Hint 4
Erdős--Ginzburg--Ziv theorem
Tutorial
Tutorial is loading...
Solution
[submission:]
