Thank you all for participating, I hope you enjoyed the problems! You can rate the problems of the round in the corresponding spoilers.
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
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
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
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
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
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
#include <bits/stdc++.h>
#define pb push_back
// #define int long long
#define all(x) x.begin(), x.end()
#define ld long double
using namespace std;
const int N = 210;
bool dp[N][N][N];
bool take[N][N][N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n), s(k);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < k; i++) {
cin >> s[i];
}
vector<pair<int, int>> s2;
for (int i = 0; i < k; i++) {
s2.pb({s[i], i});
}
sort(all(s2));
vector<vector<int>> ans(k);
for (int i = 0; i < k - 1; i++) {
int class_size = s2[i].first;
vector<int> boxes;
for (int _ = 0; _ < 2 * class_size - 1; _++) {
boxes.pb(a.back());
a.pop_back();
}
for (int sz = 0; sz <= class_size; sz++) {
for (int r = 0; r < class_size; r++) {
dp[0][sz][r] = false;
take[0][sz][r] = false;
}
}
dp[0][0][0] = true;
dp[0][1][boxes[0] % class_size] = true;
take[0][1][boxes[0] % class_size] = true;
for (int j = 1; j < (int) boxes.size(); j++) {
for (int sz = 0; sz <= class_size; sz++) {
for (int r = 0; r < class_size; r++) {
dp[j][sz][r] = dp[j - 1][sz][r];
if (sz > 0 && dp[j - 1][sz - 1][(class_size + r - boxes[j] % class_size) % class_size]) {
dp[j][sz][r] = true;
take[j][sz][r] = true;
} else {
take[j][sz][r] = false;
}
}
}
}
vector<bool> used(2 * class_size - 1);
int sz = class_size, r = 0;
for (int j = (int) boxes.size() - 1; j >= 0; j--) {
if (take[j][sz][r]) {
used[j] = true;
sz--;
r += (class_size - boxes[j] % class_size);
r %= class_size;
} else {
used[j] = false;
}
}
vector<int> to_class;
for (int j = 0; j < (int) boxes.size(); j++) {
if (!used[j]) {
a.pb(boxes[j]);
} else {
to_class.pb(boxes[j]);
}
}
ans[s2[i].second] = to_class;
}
int sum = 0;
for (auto x : a) {
sum += x;
sum %= (int) (a.size() + 1);
}
int add = (int) (a.size() + 1) - sum;
ans[s2[k - 1].second] = a;
ans[s2[k - 1].second].pb(add);
cout << add << '\n';
for (auto arr : ans) {
for (auto x : arr) {
cout << x << ' ';
}
cout << '\n';
}
}
