All problems were created by MikeMirzayanov and developed by me (Stepavly) and Supermagzzz.

**Editorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> v(n);
for (int &e : v) {
cin >> e;
}
int left = 0, right = n - 1;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
ans[i] = v[left++];
} else {
ans[i] = v[right--];
}
}
for (int i : ans) {
cout << i << " ";
}
cout << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
```

**Editorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
for (int i = 0; i <= 4; i++) {
if (s.substr(0, i) + s.substr(n - 4 + i, 4 - i) == "2020") {
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
int main() {
int tests;
cin >> tests;
while (tests-- > 0) {
solve();
}
return 0;
}
```

**Editorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int x;
cin >> x;
vector<int> ans;
int sum = 0, last = 9;
while (sum < x && last > 0) {
ans.push_back(min(x - sum, last));
sum += last;
last--;
}
if (sum < x) {
cout << -1 << "\n";
} else {
reverse(ans.begin(), ans.end());
for (int i : ans) {
cout << i;
}
cout << "\n";
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
```

1462D - Add to Neighbour and Remove

Problem authors: MikeMirzayanov, Supermagzzz, Stepavly.

**Editorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<ll> a(n);
ll sum = 0;
for (ll &x : a) {
cin >> x;
sum += x;
}
for (int i = n; i >= 1; i--) {
if (sum % i == 0) {
ll needSum = sum / i;
ll curSum = 0;
bool ok = true;
for (int j = 0; j < n; j++) {
curSum += a[j];
if (curSum > needSum) {
ok = false;
break;
} else if (curSum == needSum) {
curSum = 0;
}
}
if (ok) {
cout << n - i << endl;
return;
}
}
}
}
int main() {
int tests;
cin >> tests;
while (tests-- > 0) {
solve();
}
return 0;
}
```

1462E1 - Close Tuples (easy version)

**Editorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<ll> cnt(n + 1);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
ll ans = 0;
for (int i = 2; i < n; i++) {
ans += cnt[i - 1] * cnt[i] * cnt[i + 1];
}
for (int i = 1; i < n; i++) {
ans += cnt[i] * (cnt[i] - 1) / 2 * cnt[i + 1];
}
for (int i = 2; i <= n; i++) {
ans += cnt[i - 1] * cnt[i] * (cnt[i] - 1) / 2;
}
for (int i = 2; i < n; i++) {
ans += cnt[i - 1] * cnt[i + 1] * (cnt[i + 1] - 1) / 2;
}
for (int i = 2; i < n; i++) {
ans += cnt[i + 1] * cnt[i - 1] * (cnt[i - 1] - 1) / 2;
}
for (int i = 1; i <= n; i++) {
ans += cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
}
cout << ans << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
```

1462E2 - Close Tuples (hard version)

**Editorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 300500;
const int mod = 1000000007;
ll fact[N];
ll invFact[N];
ll fast_pow(ll a, ll p) {
ll res = 1;
while (p) {
if (p % 2 == 0) {
a = (a * a) % mod;
p /= 2;
} else {
res = (res * a) % mod;
p--;
}
}
return res;
}
ll C(int n, int k) {
if (k > n) {
return 0;
}
return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<ll> v(n);
for (ll &e : v) {
cin >> e;
}
sort(v.begin(), v.end());
ll ans = 0;
for (int i = 0; i < n; i++) {
int l = i + 1;
int r = upper_bound(v.begin(), v.end(), v[i] + k) - v.begin();
ans = (ans + C(r - l, m - 1)) % mod;
}
cout << ans << "\n";
}
int main() {
fact[0] = invFact[0] = 1;
for (int i = 1; i < N; i++) {
fact[i] = (fact[i - 1] * i) % mod;
invFact[i] = fast_pow(fact[i], mod - 2);
}
int t;
cin >> t;
while (t--) {
solve();
}
}
```

1462F - The Treasure of The Segments

**Editorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
vector<int> L;
vector<int> R;
int n;
cin >> n;
vector<pair<int, int>> v(n);
for (auto &[l, r] : v) {
cin >> l >> r;
L.push_back(l);
R.push_back(r);
}
sort(L.begin(), L.end());
sort(R.begin(), R.end());
int ans = n - 1;
for (auto [l, r] : v) {
int left = lower_bound(R.begin(), R.end(), l) - R.begin();
int right = max(0, n - (int)(upper_bound(L.begin(), L.end(), r) - L.begin()));
ans = min(ans, left + right);
}
cout << ans << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
```

Thanks for quick editorial! Great contest too and interesting problems

Thank you!

Felt more like a div4 but fun problems nonetheless. Cheers.

Another solution for D using dynamic programming.

Let's consider $$$dp[i][k]$$$ — bool variable, that means "is it possible divide $$$a_1, a_2, ..., a_i$$$ on $$$k$$$ segments of equal sum".

Initially, $$$dp[0][0] = true$$$, others — $$$false$$$.

How to count $$$dp[i][k]$$$? If we can divide $$$a_1, ..., a_i$$$ on $$$k$$$ segments of equal sum, it means that this sum is $$$(a_1+...+a_i)/k$$$ (let's called it $$$s$$$)

So we need to find such $$$j$$$, that $$$a_j+...+a_i$$$ = $$$s$$$. We know that $$$a_i \geq 1$$$, so if this $$$j$$$ exists — it is only one. We can find this $$$j$$$ using binary search, or map with prefix sums, or just maintain $$$n$$$ pointers (one for each $$$k$$$), e.t.c

So if there is no such $$$j$$$, $$$dp[i][k] = false$$$. In other case $$$dp[i][k] = dp[j-1][k-1]$$$.

To find answer, we need to find maximal $$$k$$$ such that $$$dp[n][k] = true$$$. It means we can divide it on $$$k$$$ segments, so we need $$$n-k$$$ operations.

Code: 101285918

I also thought the same approach, i just stored the index of first element of last partition. I think each will be visited only once.

brilliant, thanks!

Bruh, problem C got a way easier solution. Just brute force result from $$$1$$$ to $$$123456789$$$ and then, store the result and just handle when $$$N>45$$$ and that is all. Oh, make sure also to use pragma optimizations and unrolling loops for this funny solution to pass. Here is my code. Or, you can play it safe and handle few more N's like I did in contest. Here is my second code.

Funny thing ikr..i played it safe for 40,41,...45..etc. Till 39 the answer fits in 1e6 so no TLE issues.

Cor just go with all the permutations $$$O(9*9!)$$$ sub

Thank You

is that n*n factorial :)

nah. It's not n*n! actually. The implementation's worst calculation is 9^9, so I hacked it.

I Don't know what's worse, my life or your code's indentation

there is also a faster way, we need to check all subsets of set {1,2,...,9} using something like bitmasks.

this works with O(9 * 2^9)

Yes, I know that solution. But I was trolling with the above solutions so I can see some few people who desperately tries to hack me. Hahahha.

There's another way around Click

You can get solution in $$$O(1)$$$

Edit: Mahfel have a look, this is far faster then $$$O(9*2^9)$$$

yes,you're definitely right.

but copying 45 numbers in an array is kind of boring for me,what about you? :)

Ah $$$!$$$ Finally a man with values

Or you could just brute force over the subsets from 1 to 2 ^ 10 — 1 and check if the sum is of the digits is the same or not. If it is, then just take the min like this : 101355465

The formulas in the Editorial of Problem E1 do not reflect the formulas used in the Code.

Yes, I think so.

They mistakenly wrote $$$\frac{cnt[x]\times cnt[x]\times cnt[x]}{6}$$$ instead of $$${cnt[x] \choose 3} = \frac{cnt[x]\times (cnt[x] - 1)\times (cnt[x] - 2)}{6}$$$ and $$$\frac{cnt[x]\times cnt[x]}{2}$$$ instead of $$${cnt[x] \choose 2} = \frac{cnt[x]\times (cnt[x] - 1)}{2}$$$

Thanks, that was a typo. I fixed it

1462E1 - Close Tuples (easy version) and 1462E2 - Close Tuples (hard version)

Two small variations of this problem: https://www.geeksforgeeks.org/triplets-array-absolute-difference-less-k/

Who told you to look on the internet? during the contest

Who has forbidden you to look on the internet? During the contest?

Reasonable difficulty parameters of div 3.....

I am not talking about the difficulty parameters of div3. I am talking about the fact you mentioned: "You can't look through the internet during the contest". There is no rule against using google/prewritten code in codeforces. You may even consider "googling" a special skill for CP :D

I have one small doubt , during the contest I used printf for printing output and I got 4 WAs and after contest I submitted same solution by using cout and it got accepted.Why so?

Don't mix cout with printf when you are using fastIO, printf is faster so, it might output the result before the cout does.

Ohh,thanks . I will never forget this in my life.

Please help me with this solution of F, 101358483 I am basically trying to count the number of elements that will be good with one element

I am using a set to get the number of elements good with it before that element and upper_bound to get the number of elements after that element.

So, I get the number of elements good with any element and store the maximum of it And therefore the answer is n- (the number calculated above) Any help will be highly appreciated.:)

In problem F — The Treasure of The Segments, how do we make sure that the i-th start segment and the i-th end segment (which we use to calculate the current value) — both these start and end points belong to the same segment? Isn't the hypothesis that we iterate over all segments. But in many cases, when sorting the start and end points separately, it should violate the hypothesis that the i-th segment is being considered.

e.g. (1, 2), (3, 7), (4, 5), (6, 9), (8, 10)

Left endpoints in sorted order : 1 {belongs to 1st segment}, 3 {2}, 4 {3}, 6 {4}, 8 {5}

Right endpoints in sorted order : 2 {1}, 5{3rd segment and NOT 2nd}, 7 {3}, 9 {4}, 10 {5}

Even if it is true that the cases for l > R and r < L are handled separately, I cannot understand how calculating these half-values for the same position in sorted order ensures reaching the optimal answer.

Edit: Looks like I didn't read the editorial code carefully. We are considering the i-th segment only (by iterating over the original vector of pairs

`v`

). Thanks to both the gentlemen who replied.???

We can say if a segment $$$(a,b)$$$ coincides with segment $$$(c,d)$$$, then $$$c<=b$$$ (vice versa may not be true). So, for a particular segment $$$(a,b)$$$ we can find all those segments whose $$$start<=b.$$$

In the above picture if I calculate such segments for red segment, I'll get $$$5$$$ such segments (including the red segment itself).Now, we have to remove such segments in which $$$end<a$$$ because such segments (segment $$$1$$$ in this example) will surely be included in the above ans but in actual they don't intersect with red segment. Thus, we get $$$5-1=4$$$ segments intersecting with red segment (including itself).

I fail to see how this answers my question. Please note that I had solved this question, just without sorting the two arrays independently. That's my issue — how can you ignore that you're not considering the same segment anymore? It's been bothering me a lot and I'm sure it's something silly that I'm missing. Thanks nevertheless.

It isn't necessary that $$$i^{th}$$$ index of both the arrays after sorting belong to same segment. The proof above still remains valid.

For each segment, we are calculating the number of segments that end before the current one starts and the number of segments that start after the current one ends. Now, think a minute and see that these two values will never have a common value.

I had a slightly different approach to D using more of an analytical/brute force method.

Similar to the reasoning presented in the posted solution, the sum of the overall array will always stay the same, meaning that the original value of each part of the array will be preserved either as an individual number in the final array or as a component of another number in the final array.

As such, it can be seen that the number at an index of

1must always be included in the final array in some form, allowing for an iterative solution over the array to be created.Iterating over all values

ifrom1tonand keeping the cumulative sumsumof each number that was iterated upon to represent one "fixed" value in the final array, this sum can then be validated by iterating over the remainder of the array. When iterating over the remainder of the array, keep a sumcSumof numbers that have already been reached. If that sum is equal to the sum of the fixed window, resetcSumto0and continue and if it is greater than the sum, then break from the iteration since that means it doesn't work. Store the number of timescSumwas equal tosum.Finally, take the maximum number of times that

cSumwas reset through all iterations, add 1 to signify the initial reset at the end of the first window, and subtract fromnfor the final answer.This solution would run with an O(n

^{2}) time complexity in its worst-case.Code: 101330471

Why is time limit for E1 2 secs but time limit for E2 4 secs?

Problem C can be done by bruteforcing all $$$2^9$$$ possible numbers of different (non null) digits that are the smallest in lexicographical ordering for that set of digits, since the solution must satisfy this constraint.

Example

Here's a fairly simple $$$O(n \log(an))$$$ solution for D: 101370002

It can also be optimized to just $$$O(n \log n)$$$.

Also quick note, I'm still seeing Russian in the English title of this post ("Разбор").

can you please explain it a lit bit? Thanks!

Sure! I actually didn't explain this in my stream (I came up with it after my stream).

Let's say the sum of the array is $$$s$$$ and we want to know whether we can end up with a final array of length $$$len$$$ with all equal elements. Then we need to cut the array up into $$$len$$$ subarrays, each with sum $$$\frac{s}{len}$$$.

If we compute the prefix sums of the $$$a_i$$$, this means we'll need to find one prefix sum matching each of $$$\displaystyle \frac{1}{len} \cdot s, \frac{2}{len} \cdot s, \dots, \frac{len}{len} \cdot s$$$. Since $$$a_i > 0$$$ we really just need $$$len$$$ different prefix sums that are divisible by $$$\displaystyle \frac{s}{len}$$$.

If we have a particular prefix sum $$$p$$$, what values of $$$len$$$ does it work for? It turns out we take $$$\displaystyle x = \frac{s}{\gcd(s, p)}$$$ and then we want all multiples of $$$x$$$. (For example if $$$p = \frac{3}{5} s$$$ then $$$x = 5$$$.)

We compute GCDs, generate all these counts, and then do a sieve-style summation to cover all multiples, and we're done.

To get to $$$n \log n$$$, notice that the bottleneck is computing the GCDs which takes $$$\log(an)$$$ time each iteration: 101370002. However we only care about the value of $$$g$$$ when $$$\displaystyle len = \frac{s}{g} \leq n$$$, or namely when $$$\displaystyle g \geq \frac{s}{n}$$$. So we can stop our GCD algorithm once we go below $$$\displaystyle \frac{s}{n}$$$, which means it only takes $$$\log n$$$ time.

neal can you tell what exactly does

xsignify. I understand that if i can dividesumintoxparts than it is possible to divide it into alldivisors of xparts as well. for example if we can divide sum into4parts we can also divide it into2parts as well, just by clubbing the two parts into one.So instead of taking all multiples of x should not we take

divisors of x?I am trying to grasp on what case this submission (101340630) for problem

Dis failing. According to the editorial, a check to verify if`k`

is the answer can be implemented greedily. In the above implementation, i try to pick the`min-element`

in the original array and add it to`min(left-element, right-element)`

before deleting that`min-element`

. Is that theory wrong?Yes, example 5 6 2 6 3 gives the wrong solution(or 3 6 2 6 5 depending on your code). The answer is 3, but greedy will give 4 for one of these inputs.

Got it, thanks for the case.

No problem :)

https://codeforces.com/contest/1462/submission/101325108 Please tell me what i did wrong as i think i have applied the same thing as mentioned in the editorial.

I got WA in D , can anyone prove why my idea is incorrect? Every time I check whether all the elements are equal or not, if they are equal just print the current number of operation else pick the smallest element and add it to the smallest neighbour and increase operation count by 1, my sub link:- https://codeforces.com/contest/1462/submission/101310473

https://codeforces.com/blog/entry/85594?#comment-733356

??

I answered to this exact question in the link I pasted, anyway this is the answer. Example 5 6 2 6 3 gives the wrong solution(or 3 6 2 6 5 depending on your code). The answer is 3, but greedy will give 4 for one of these inputs.

OMG! got it, when they have equal values in both sides it fails to choose optimally

Not true. Reason is that greed will just fail. :)

I did the same in the contest like an idiot without thinking. Simply put, it's wrong. Adding the smallest to the one of it's neighbouring elements seems to work, but there is no way that it should work.

Eg. {9, 1, 5, 3, 2}

Another solution for problem B:

Lets create a $$$DP[idx][idx2][state]$$$. $$$idx=$$$prefix of first string, $$$idx2=$$$prefix of second string, $$$state=0,1,2$$$. Transition is to check if $$$s[idx]=t[idx2]$$$ where $$$s$$$ is the first string and $$$t="2020"$$$. If $$$state=1$$$, change it to $$$2$$$. Because $$$state=0$$$ means that we didn't delete anything, state=1 means we are currently deleting, $$$state=2$$$ means we are not allowed to delete anymore. And another transition depending on the state. If state is equal to $$$0$$$, then it will turn $$$1$$$ as you are forced to delete that number. If state equals to $$$1$$$, you will keep deleting. Otherwise, you have nothing to do and you didn't find an answer. I hope you liked my overkill solution!

Warning, bad indented code101283920

E2For those who are looking how to calculate for a NcR % mod for huge N and R , for

E2.just call the preNCR() in main().

What is wrong in this? Problem 2 101403407

You should consider two more cases: - when string begins with "2020" - when string ends with "2020"

What's wrong with my solution of E2? link

Upd. Wow! I find the problem! AC.

Thanks a lot for the contest and the editorial learnt many things from this round!

can anyone explain whats wrong with my solution for E1 ``` public static void solve1() {

} ```Is it something related to the data type this solution is not passing or 5th pretest

.

Thank you for great contest!

Very Interesting problems!!

in problem F how the output of this test case 1

4

1 2

2 3

3 5

4 5

it should be 2 right? correct me if i am wrong

It should be 1 because we can provide the required property with the 3rd segment by deleting only the 1st segment.

I am confused between E1 an E2 if E1 is lower version of E2 then why solution of E2 without mod is not passing E1 it is giving wrong answer on test case 5 can anyone explain this ?

my submission of E1 converted from E2 101642503

You are using mod operator while evaluating Factorial , nCr , invfact

below is code without mod operation it won't even paas sample test cases

It will not pass surely because ans%i might not be 0 , do ans/i in another loop , or just do ans/=2 , answer will come. Here is my submission. https://codeforces.com/contest/1462/submission/101844558

Problem E has $$$\mathcal{O}(n \log n)$$$ solution, which doesn't use, that elements are in $$$[1, n]$$$. Let's sort our array, and calculate number of possible subsets if minimal element in subset is $$$a_i$$$. Let $$$l$$$ be max index, such that $$$a_l \leqslant a_i + k$$$, let $$$x$$$ be numbers equal to $$$a_i$$$ in range $$$[i, l]$$$ in array, and $$$M$$$ is number of other numbers in this range. So if in chosen subarray $$$a_i$$$ is minimal value, then all subarray is in this range. So number of possibilities to choose this subarray is $$$\sum_{i=1}^x C^i_x \cdot C^{m - i}_M$$$, where $$$C^k_n$$$ is number of possibilities to choose $$$k$$$ elements from $$$n$$$ elements, also known as binomial coefficient which can be easily find as $$$C^k_n = \dfrac{n!}{(n - k)!k!}$$$. If we precalculate factorials, and numbers, that is inverse modulo $$$10^9 + 7$$$ to factorials, we can calculate $$$C^k_n$$$ for $$$\mathcal{O}(1)$$$(Warning: if $$$k < 0$$$ or $$$k > n$$$ we must return 0). Because $$$a$$$ is sorted, we can find $$$l$$$ using two pointers technique and calculate $$$x$$$ for $$$\mathcal{O}(n)$$$ total. Because sum of $$$x$$$ is $$$n$$$ it will be $$$\mathcal{O}(n)$$$ time and $$$\mathcal{O}(n \log n)$$$ time to sort array. We can precalculate factorials and inverse factorials for $$$O(n \log A)$$$ using binary pow or extended gcd. Also we can calculate inverse factorials for $$$\mathcal{O}(n)$$$ using linear sieve technique which described here, but it is not necessary. Space complexity is $$$\mathcal{O}(n)$$$

Submission, which can help to understand solution: https://codeforces.com/contest/1462/submission/103030183

Can anyone tell what is wrong with problem E2 submission 120341826.

What is wrong in this? Problem E2 178055245