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';
}
}
Shows me , posted 5 days ago, fastest editorial ??
It shows time when blog was created as a draft, not when it was published
Great contest, thanks :)
Oh, a tutorial with Python code, how avant garde
E can be passed by brute forcing all possible positions to change. Not sure if its provable but I couldn't think of any hack cases when coding it. https://codeforces.net/contest/1798/submission/199283535
This case can hack it.
1
100000
1 49999 1 1 1 1 ...... 49999 1
In Problem D:
Can anyone tell me the ans of test case:
1
5
1 2 3 -30 -20
According to my understanding, the ans should be No, as sum of abs(-30 + -20) > max(3) — min(-30), but many of the passed solutions are outputing Yes
Edit: Got it, forgot to read the very first line of question
The sum of the array needs to be 0
a1 + a2 + a3 + ... + an = 0this does not hold in your case.WoW! The editorial dropped faster than my rating :)
WOW! Lightning fast editorial
WOW! Lightning fast editorial
Problem B is very similar to Kahn's algorithm.
You can solve C by abusing the fact that LCM grows fast too.
Greedily try to make segments of the same cost. Naive $$$O(n^2)$$$ is to check if you can make the cost for the current range equal to $$$lcm(a[rstart, i])$$$ for every $$$i$$$, but you only need to do the $$$O(n)$$$ check if the value of LCM changes between $$$i-1$$$ to $$$i$$$. If it doesn't change you already know it's possible for the range $$$[rstart, i-1]$$$. So you just need to check if you can include $$$i$$$ in the range. 199293298
Can you tell me What I am doing wrong 199314288? Doing something the same.
Did you not include a pretest with n=3e5 in D on purpose?
Also he did not include a pretest with n=2e5 in C on purpose.So my C and D are all hacked haha.
Also no pretest with 50000 on B, causing my rank to drop from 2700 to 7000.
The system test of problem E is too weak. My brute force solution passed it, and it can be hacked by a very simple testcase. Please be more careful for preparing testcases.
Link:199296293
This was kind of a hope greedy works contest imo.
In both c and d i was like "i hope this covers all cases, let's submit". I don't really like this kind of problems
That's so true man I did the same with C then I could not think about the solution of D so with 5 minutes remaining just coded up whatever came to mind and it got accepted with 15 seconds remaining hehe.
True, turns out that in d you can just assign any valid value and repeat for each element of the array and it's guaranteed to find the solution
Please explain C someone ???
In C, according to tutorial if we solve for prefixes like:
{[a1, a2, a3] [a4, a5, a6] [a7, a8, a9, a10]} have price tags {c1, c2, c3} and c1 becomes equal to c3. the solution should fail, correct me where I'm wrong.
Edit: I read the question wrong
Problem D was easier than Problem C... Is it?
(For problem F) I had never heard of the Erdős--Ginzburg--Ziv theorem but I guessed that it had to be true by the fact that none of the samples had "-1" as an answer.
For those curious, an elementary proof is in the second response here.
Why that proof need to reduce the original problem to the case when n = prime?
Does any step using the property that $$$p$$$ is a prime?
Yes, because it assumes a-b is relatively prime with p when a != b
Oh, I got it. Thanks.
Did not participate in this round but surely not a well set round. You expect Div2C and Div2D to have a certain difference in difficulty. The D problem surely didn't deserve to be a Div2D.
My Solution for problem C
Like these hints.Thanks.
anyone provide me problem B c++ code
https://codeforces.net/contest/1798/submission/199261171
are you on discord
no
In C problem , wrote the code of LCM wrong. Didnt check as i was taking GCD and LCM for granted. Can't handle more negative. Wanna die :(
Negative delta loading ...
Thanks for the problems! Pretty interesting and balanced set.
By the way, it seems we can't view the reference solutions.
lol, indeed, thanks for pointing it out. fun fact is that I copied template from editorial of previous round, and it is impossible to see reference solution in that editorial too, and nobody said that before. that is pretty much proves, that this references are useless, but I'll update them soon.
How would you do D, if the sum wasn't 0?
Basically the same idea of considering prefix sums works except you have to be a bit more careful. If all the numbers are nonnegative or nonpositive it's clearly impossible. Now, without loss of generality assume the total sum is nonnegative. Let mx be the max element and mn be the minimum element. If the total sum is >= mx — mn, then of course the task is impossible no matter how you reorder the array, otherwise it's possible.
First, place all the 0s in the array at the front. Then, it is possible to add elements so that the prefix sums are always in [0, mx — mn). Specifically, if the current sum is in [0, -mn), you add a positive element, otherwise if it is in [-mn, mx — mn), you add a negative element.
This strategy ensure the prefix sum will always be in [0, mx — mn) until we run out of positive elements or negative elements. Then, since the total sum is in [0, mx — mn), adding the remaining positive or negative elements will still keep the prefix sum within [0, mx — mn).
Appreciate that the solution has hints. Helps with upsolving problems beyond our range!
About the D Problem.
max1≤l≤r≤n|al+al+1+…+ar|Is there a way to minimize this formula?
For B, you can choose the elements that appear the least later on in the future and it also works.
The solution link in the problem F is not working. Hope it will be fixed soon.
I think the testcases of problem B is weak ? My nearly brute force solution 199278375 passed (1387ms) ,and you can easily find a testcase to hack my code.
Which part is brute force? Learn meaning of it first xD. It is greedy and since everyone can take at most one place, your solution is correct. Getting 1387 ms. because for every test case (5e4), you're clearing your arrays with size 5e5.
Thanks. I should learn more.
Really great round
Great round and a great editorial indeed. If anyone wants a video editorial for these problems (for Problem A, Problem B, Problem C, Problem D). You can watch this here — video editorial
the solution for F can't be viewed.
Also if the complexity for single si is n^3(8000000) and the restriction is 1s, how can this avoid getting TLE?
I pasted my code in editorial. For a more understandable and better written code, I recommend to look into jiangly's submissions (Top1 of this round).
On practise, this is very very fast $$$O(n^3)$$$ (it can be even improved to $$$O(n^3/w)$$$, where $$$w = 64$$$, with bitset), a lot of solutions fits into 50ms, and also there is Python solution that fits under 200ms.
$$$200^3$$$ is just $$$8*10^6$$$ which is super fast for 1 second on Codeforces' servers.
I didn't notice that the sum of $$$s_i$$$ is no greater than 200. I thought for each $$$s_i$$$ there is a O($$$n^3$$$) dp and the total complexity will reach O($$$n^4$$$)...
$$$8*10^6$$$ can be done in 1s is pretty fast though
E is a beautiful problem
In Problem C I don't understand why using GCD and LCM. can anyone explain it in detail? I really appreciate any help you can provide.
let the cost of each pack of candies be $$$C$$$. So, it must satisfy that $$$C = B_i \times D_i$$$ for each $$$ 1 \leq i \leq n$$$.
Thus, All $$$B_i$$$ must divide $$$C$$$ which means $$$lcm(B_1, B_2,..., B_n)$$$ must divide $$$C$$$.
Now, $$$D_i$$$ is a divisor of $$$A_i$$$. let, $$$K_i = \frac{A_i}{D_i}$$$.
$$$C = B_i \times \frac{A_i}{K_i}$$$ for each $$$ 1 \leq i \leq n$$$.
$$$K_i = \frac{B_i \times A_i}{C}$$$ for each $$$ 1 \leq i \leq n$$$.
$$$K_i$$$ must be an integer which means $$$C$$$ must divide $$$B_i \times A_i$$$.
Thus, $$$C$$$ must divide $$$gcd(B_1 \times A_1, B_2 \times A_2,..., B_n \times A_n)$$$.
You are the God Sir. Believe me You explained it so clearly . My whole lifetime i will not forget this(I am not exaggerating.)
I Wish every tutorial are like this. Thanks a lot sir.
For Problem F, the $$$n^3$$$ DP can be instead be done in $$$n\log n$$$ after a recent preprint. See submission 199466476 (assuming I implemented it correctly).
Obviously, this is completely unnecessary.
Ok, its 2 days after round, I decided to write a little postscriptum, which can answer some questions and show some insights of problemsetting/testing.
Firstly: thanks everyone who wrote comment with positive feedback about the problems, it's a big pleasure to see it, really. Second: apologize to everyone who got FST and negative delta because of it, pretests quality on problems B, C, D was poor, I'll be more careful with this next time.
Forgive my non-prefect English, but I believe text is still understandable despite my mistakes. Thanks everyone who read that!
Is there any basic proof for why greedy works in C? Still can really believe it or prove it myself
Consider any possible answer and any possible price tag in it. If this price tag can be expanded to the right by 1, lets expand it. Since "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 action can not increase number of price tags. So starting from any possible answer we can expand any price tag to the right while we can, and number of price tag will not increase. After we do all possible expands we will achieve greedy construction (in greedy construction no price tag can be expanded to the right. and its unique construction, because there is only way to choose prefix that cannot be expanded to the right, and so on).
Ok, it makes sense, idk why didn't I see it during contest.
Thanks for the editorial, I have a simple doubt, Can you tell me in problem C we are taking lcm(b1,b2...bn) and not lcm(b1*d1,b2*d2...bn*dn). Is that because we are trying to remove di from the picture?
Cost of each bag from i to j will be gcd(ai*bi, ai + 1 * bi+ 1,...., aj * bj) (provided the condition stated in tutorial for i to j is satisfied) Or I am thinking wrong? Please someone explain.
Thanks, in advance.
Cost can be any integer $$$x$$$ such that $$$gcd(a_i \cdot b_i, \ldots, a_j \cdot b_j)$$$ divides $$$x$$$, and $$$x$$$ divides $$$lcm(b_i, \ldots, b_j)$$$. So yeah, this gcd is one of the options of cost.
For problem E, why is it the case that you only need to check if the dynamics value at i+1 is greater than or equal to a_i? Why don't they need to be exactly equal? In other words, how is it possible to create any number of tests up until the maximum number of tests that can be achieved by changing one element?
Yes, this is fair remark. We can see that if 1 change was made to make $$$x$$$ tests, we can redo it to make exactly $$$x - 1$$$ tests. If first element was changed ($$$i+1$$$) it is pretty clear, we just extend $$$go_{i+1}$$$ to cover one more test. And if not first element was changed, you can change previous element (see picture). So if you can achieve $$$x$$$ tests you can achieve $$$x-1$$$ and so on, recursively, you can achieve any number from $$$1$$$ to $$$x$$$. And since $$$a_i \geq 1$$$ in the problem, its enough.
Oh ok I think I understand now. Thank you for the clarification.
https://codeforces.net/contest/1798/submission/245358316 I mistakenly solved the harder version of $$$D$$$ where sum of the elements of the array is not necessarily 0
Sorry for necroposting, but in problem D how could have one came to the construction algorithm presented in the tutorial? Like after getting to know the construction algorithm, it becomes clear that $$$|a_l + a_{l+1} + ... + a_r| > max(a) - min(a)$$$ but before knowing that I would only search in the realm of infinite algorithms that which one of those can give the desired result. Considering the fact everyone found problem D as easy, am I missing something important here?