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 :)

thanks i was confused

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.com/contest/1798/submission/199283535

This case can hack it.

1

100000

1 49999 1 1 1 1 ...... 49999 1

Really great round, problems till D felt pretty solvable. Although managed to solve only 2 but had fun.

Fastest Editorial but I wanna unsolve first...

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 = 0`

this 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.

codecan you provide B code in c++

check

thissubmission 199295933.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.

Take a look at Ticket 16782 from

CF Stressfor a counter example.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.

Can you tell me what I'm doing wrong submission? It failed in test case 10 of problem D.

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

niceee, good to know people with 1600 rating are also HOPING for solutions to cover all cases , not just me

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?

Yes, I also felt it. I regretted solving C before D.

(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.

In C, I really thought as long as the biggest bi (i.e max(b1,b2...bn) could divide the GCD, it should be fine. It took me like an hour after the contest ended to figure out why this wouldn't work.

Love it when my brain turns off when I need it.

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

CodeLike these hints.Thanks.

easy and cool up to problem D. However, can't solve problem E. I hope I will see a color change.

anyone provide me problem B c++ code

https://codeforces.com/contest/1798/submission/199261171

are you on discord

no

199363305

another opportunity to feel ashamed....!!![ ]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).

<0000000000000000000>

how to solve the problem C if the types can be shuffled?

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?

Would there be any efficient algorithm for Problem C when also allow reordering of the packs? Like for

`20 3 6 2 14 5 20 7 21 2`

we would still need 2 tags but we cannot use the prefix argument.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.

gcd(a1⋅b1,…,an⋅bn) is divided by lcm(b1,…,bn) can someone prove this?

Let $$$x$$$ be $$$lcm(b1,…,bn)$$$. Now let's try to price each type of candy with $$$x$$$. For each $$$i$$$, if cost of one pack is $$$x$$$ and one candy costs $$$b_i$$$, one pack will contain $$$x/b_i$$$ candies. So $$$a_i$$$ must be divisible by $$$x/b_i$$$. If we reorder that, $$$a_i⋅b_i$$$ must be divisible by $$$x$$$. Since $$$gcd(a1⋅b1,…,an⋅bn)$$$ is divisible by $$$x$$$, Each $$$a_i⋅b_i$$$ contains $$$x$$$ as a divisor.

why is my submission on problem c showing tle in test case 4. its a O(n) solution https://codeforces.com/contest/1798/submission/199363574

edit: i found my mistake in worst case it was going upto n^2 . thank you

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

Can anyone point out the mistake in logic for C?

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.

Nice explanation.

Is there any proof for these statements or material for reading:-

[LCM and GCD Universal Property](https://www.cut-the-knot.org/arithmetic/GcdLcmProperties.shtml#:~:text=For%20two%20(positive)%20integers%20N,N)%20%3D%20M%20%C3%97%20N.)

My contest went bad. But the overall quality of the problems are really good. I really appreciate the tutorial format too :)

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.

Why D is easier than C, is it intended?Story of problem AStory of problem BStory of problem CStory of problem DStory of problem EStory of problem FForgive 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.

Can you please explain why in your initial question "Is one price tag enough", just checking

LCM(b1,b2,b3,...bn)as the cost of each bag was working?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.

I didn't understand that C should be greedy. Anyone to explain?