We hope you liked our problems!

**Tutorial**

Tutorial is loading...

**Code**

```
t = int(input())
for i in range(t):
a, b, c = map(int, input().split())
if c % 2 == 0:
if a > b:
print("First")
else:
print("Second")
else:
if b > a:
print("Second")
else:
print("First")
```

**Tutorial**

Tutorial is loading...

**Code**

```
#include <bits/stdc++.h>
using namespace std;
int solve(int d, vector<int> x)
{
int ans = 0;
for (int i = 1; i < x.size(); i++)
{
ans += (x[i] - x[i - 1] - 1) / d;
}
ans += int(x.size()) - 2;
return ans;
}
void solve()
{
#define tests
int n, m, d;
cin >> n >> m >> d;
vector<int> r(m);
for (int i = 0; i < m; i++) cin >> r[i];
r.insert(r.begin(), 1 - d);
r.push_back(n + 1);
int ans = 2e9;
vector<int> res;
for (int i = 1; i <= m; i++)
{
int A = r[i] - r[i - 1] - 1;
int B = r[i + 1] - r[i] - 1;
int C = r[i + 1] - r[i - 1] - 1;
int D = C / d - (A / d + B / d);
if (D < ans)
{
ans = D;
res.clear();
}
if (D == ans)
{
res.push_back(r[i]);
}
}
cout << ans + solve(d, r) - 1 << ' ' << res.size() << endl;
}
int main()
{
int t = 1;
#ifdef tests
cin >> t;
#endif
while (t--)
{
solve();
}
}
```

1858C - Yet Another Permutation Problem

**Tutorial**

Tutorial is loading...

**Code**

```
#include<iostream>
#include<vector>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
int cur = 0;
for (int i = 1; i <= n; i += 2) {
for (int j = i; j <= n; j *= 2) {
a[cur++] = j;
}
}
for (int i = 0; i<n; ++i) {
cout << a[i] << " ";
}
cout << '\n';
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Code**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
void solve();
template<typename ...Args>
void println(Args... args) {
apply([](auto &&... args) { ((cout << args << ' '), ...); }, tuple(args...));
cout << '\n';
}
int32_t main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int t = 1;
cin >> t;
for (int tc = 0; tc < t; ++tc) {
solve();
}
return 0;
}
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> max0by1(n + 1, -1e9);
vector<vector<int>> max0pref(n + 1, vector<int>(n + 1));
vector<vector<int>> max0suf(n + 1, vector<int>(n + 1));
for (int l = 0; l < n; ++l) {
int cnt1 = 0;
for (int r = l + 1; r <= n; ++r) {
cnt1 += s[r - 1] == '1';
max0pref[r][cnt1] = max(max0pref[r][cnt1], r - l);
max0suf[l][cnt1] = max(max0suf[l][cnt1], r - l);
}
}
for (int r = 0; r <= n; ++r) {
for (int cnt = 0; cnt <= n; ++cnt) {
if (r) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r - 1][cnt]);
if (cnt) max0pref[r][cnt] = max(max0pref[r][cnt], max0pref[r][cnt - 1]);
}
}
for (int l = n; l >= 0; --l) {
for (int cnt = 0; cnt <= n; ++cnt) {
if (l + 1 <= n) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l + 1][cnt]);
if (cnt) max0suf[l][cnt] = max(max0suf[l][cnt], max0suf[l][cnt - 1]);
}
}
vector<int> ans(n + 1, -1e9);
for (int l = 0; l < n; ++l) {
int cnt0 = 0;
for (int r = l; r <= n; ++r) {
if (r > l) cnt0 += s[r - 1] == '0';
if (cnt0 > k) break;
max0by1[r - l] = max(max0by1[r - l], max0pref[l][k - cnt0]);
max0by1[r - l] = max(max0by1[r - l], max0suf[r][k - cnt0]);
}
}
for (int i = 0; i <= n; ++i) {
for (int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);
}
for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
cout << '\n';
}
```

1858E2 - Rollbacks (Hard Version)

**Tutorial**

Tutorial is loading...

**Code**

```
#include <iostream>
#include <vector>
#include <numeric>
#include <set>
using namespace std;
const int maxn = 1e6 + 1;
int f[maxn];
int get(int i) {
int ans = 0;
while (i >= 0) {
ans += f[i];
i = (i & (i + 1)) - 1;
}
return ans;
}
void upd(int i, int x) {
while (i < maxn) {
f[i] += x;
i = i | (i + 1);
}
}
int a[maxn];
int rev[maxn];
set<int> ids[maxn];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fill(rev, rev + maxn, -1);
fill(a, a + maxn, -1);
int q;
cin >> q;
int ptr = -1;
vector<pair<pair<int, int>, int>> changes;
while (q--) {
char t;
cin >> t;
if (t == '?') {
cout << get(ptr) << endl;
} else if (t == '+') {
int x;
cin >> x;
int mem = a[ptr + 1];
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
ids[a[ptr + 1]].erase(ptr + 1);
}
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
a[ptr + 1] = x;
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
}
ids[x].insert(ptr + 1);
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
++ptr;
changes.push_back({ { 1, mem }, -1 });
} else if (t == '-') {
int k;
cin >> k;
ptr -= k;
changes.push_back({ { -1, k }, -1 });
} else {
if (changes.back().first.first == 1) {
if (a[ptr] != -1) {
if (ids[a[ptr]].size()) {
upd(*ids[a[ptr]].begin(), -1);
ids[a[ptr]].erase(ptr);
}
if (ids[a[ptr]].size()) {
upd(*ids[a[ptr]].begin(), 1);
}
}
a[ptr] = changes.back().first.second;
--ptr;
if (a[ptr + 1] != -1) {
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), -1);
}
ids[a[ptr + 1]].insert(ptr + 1);
if (ids[a[ptr + 1]].size()) {
upd(*ids[a[ptr + 1]].begin(), 1);
}
}
} else {
ptr += changes.back().first.second;
}
changes.pop_back();
}
}
}
```

**Note:** At about 20 minutes into the round one of our testers (SomethingNew) came up with a linear solution for problem E2, and jiangly implemented the same solution shortly after the contest! For further details, see 219001999. The main idea (as jiangly pointed out in the comments) is that we can use prefix sums instead of the Fenwick tree.

Auto comment: topic has been updated by pakhomovee (previous revision, new revision, compare).thanks for fast editorial

no problem

thanks for the quick editorial :)

hope to learn how to solve B, wonder why it had so less solves?

for some reason the authors thought c is harder than b idk how

exactly, was able to understand C, but B was like reading a confusing story :(

i actually saw b easier than c though (maybe because i not good at proving)

I finished it to late, dammed to be newbie :\

B had a lot of different cases to concider and plenty of chances to make mistakes. even if the concept for solving it wasn't that hard to find.

imho it is poorly written and hard to understand

Yes!Agree fiercely！

Thanks for super fast editorial. Btw can I reach expert? :)

You did! orz

orz

where is E1?

E1 is an easier version of E2, so any solution that works for E2 will work for E1

Yeah but maybe E2 is too hard to understand/code, and a simpler idea would be nice to know

I explained how to solve it here

Prety explain and after I read it, I impelment it and get accepted.

For problem E2, have you ever tested that 200MB static memory will exceed the 256MB memory limit?

Rollbacks this comment, guess it has something to do with C++'s memory alignment.

Fast editorial!

Amazing! The question title for Problem C was exactly what I was thinking.

Why some recent contests always have C as a number theory problem?

especially permutation

true

The title wrongly mentions the round as 892.

Hi all!

Very interesting competition!

Thank you very much arbuzick I love you

B was a little weird.

is problem B designed to prevent contestants from using ChatGPT?

But human only won't understand the statement.

To be honest I lost interest in B the moment I saw it. It's all about interpreting.

one of the worst problem B i've ever seen :<

Why in B we should set d — 1 for first element, instead of 1. I'm wondering, maybe I got WA because of that

You might be having the same problem as mine. Could you please check the following scenario.

If there's a seller at bench 1, then that seller could be removed. If after its removal, the cookie count is minimum then it would contribute to the answer. Even after the seller at index 1 is removed, Petya would still eat a cookie at index 1.

Try this testcase:

1

7 3 2

1 3 5

Expected output:

4 3

C is similar to A Problem in Chinese OJ — Luogu、will the contest unrated?

I'm afraid that it may will be.

Well contests on codeforces will not be unrated easily, and I think C is just too simple and doesn't make difference. It only affects a small number of Chinese contestants.

However there are several serious mistakes (B is just interpreting, C is too easy, E with 256MB Memory Limit), and the contest may be unrated. Similar problem is not the point.

with this many issues its got to be unrated

There is nothing to do with those things to make a round unrated. Almost every div2a, div2b and div2c are probably appeared somewhere before, because authoring a different easy problem is actually a very hard thing. Diffuculty balance or some limits doesn't affect contest's ratedness, also there is nothing to do with them as a participant.

C is the same problem from another OJ。Here's the link

(By the way, the owner of this problem is my friend.)

and I think E1&E2 are 2ez and trivial.

Well I had the solution to E1 and was unable to implement it properly so I guess that the implementation makes it harder ? Also this is a div2 round so I can understand that it's trivial for you but if it isn't for most div2 contestants then that's fine. The problem by itself is good and educative (I think)

you are wrong. E1 and E2 are completely different. that's means you cant solve E2 based on E1's solution.

I only talked about E1, not E2

I mean，E2 is easier than E1.

ehm, my sol (perform dfs on a tree) somehow generalises to E2 I think

Nice contest! Although I think B is a tiny bit too difficult. See you on the next contest!

aku adalah from Makassar South Sulawesi

b was all about how you interpret. if it would have been c, then everything would be great.

In B for the last testcase

`1000000000 3 20000000 57008429 66778899 837653445`

shouldn't the answer be 52 after removing the first cookie seller? These are the benches where petya can eat a cookie

`1 20000001 40000001 60000001 66778899 86778899 106778899 126778899 146778899 166778899 186778899 206778899 226778899 246778899 266778899 286778899 306778899 326778899 346778899 366778899 386778899 406778899 426778899 446778899 466778899 486778899 506778899 526778899 546778899 566778899 586778899 606778899 626778899 646778899 666778899 686778899 706778899 726778899 746778899 766778899 786778899 806778899 826778899 837653445 857653445 877653445 897653445 917653445 937653445 957653445 977653445 997653445`

True, that's why you should remove the third cookie seller instead of the first. I guess you misunderstood the problem due to the terrible problem statement.

Oh, thanks! you are right, I misunderstood the problem. I thought we needed to print the index of the cookie seller to be removed. My bad

I didn't participate in this contest, but took a quick look at E1/E2. Why is the memory limit 256 MB? It seems kind of on the edge of what is possible with O(q log(q)) memory, but clearly this was not intended. Why not make the memory limit a lot lower?

Very cool problems, especially problem E, although I think problems B and C should have been swapped.

You don't need a fenwick tree in problem E2, just maintain a prefix sum array and update it when adding number, and then you get a linear solution! 219001999

I think B is the actual C problem rather being original B in this contest was stuck on it for past 45 mins :(

i spent all my time on b and did not even look at C :D

Hope to learn to solve E1. Can someone tell me the observation behind it?

Maybe E should give 512MB.

I think so.I've got a lot of memory limit exceed in the contest.

b question is tricky its language is not simple

Hey guys, I'm new to CP and need help understanding the first question.

If example taken is 1 2 2

then the winner in that case should be the first one right ?

Tell us why the winner will be the first one

1 2 2 a-->after 1st turn 0 2 2 b--->second turn 0 1 2. a--->third turn(first person will use extra one) 0 1 1 b--->fourth turn 0 0 1 a--->fifth turn 0 0 0 . for b no chances so a wins

Read the problem statement again.

"... The girl who cannot press a button loses. Determine who will win if both girls play optimally."

Do you think the move sequence you showed us satisfies the condition of both girls playing optimally?

Yea I thought the same thing yesterday

In B why the test case #7

`2 2 2 1 2`

should print`1 1`

and not`1 2`

Since removing either of the sellers will reduce the cookie count by 1you should print the number of sellers that would make the cookies minimum, not the index

Since Petya hasn't yet eaten a cookie at the 1st bench, removing its seller will not reduce the total cookie count.

Yes, thank you.

my approach for C:

Our goal is to have all pairs (1,2), (2,4), ... (i, 2*i), ..., (n/2, n/2*2) next to each other in the permutation

our first attempt is an array: [n/2,n/2*2, ..., i,2*i, ..., 3,6,2,4,1,2] but the array contains duplicates, and is missing values

let's build our answer array by looping i = n/2 -> 1, and attempt to append values

`i`

,`2*i`

onto the back. Value`i`

won't appear in the array since we're looping decreasing, but what if`2*i`

appears in the array (from previously appended pair)?In this case, we can insert value

`i`

next to value`2*i`

(but not in between previous pair`2*i`

,`4*i`

)and at the end, we append all missing values

For Problem B, Can you please explain this line?

`it might help to assume that there are two more cookie sellers at positions 1-d and n+1`

Maybe you needed 14 more authors to realise that problem B was harder than problem C. Also you missed the number of the round in the name of the blog.

Why so agitated?

Great contest! Really enjoyed problem D, so sad I'm too slow :)

Guess problem B was given in the problem set to drop the overall rating of the contestants :(

There is an $$$O(q)$$$ solution for E2 that I found after initial testing. However, I did use array of size $$$max(x)$$$, so the solution would be $$$O(qloq(q))$$$ if $$$x$$$ can be arbitrarily large.

This solution use the idea that the states of a data structure can be represented as a tree. The root is the initial state, when we modify the data structure, we add a new node that represent that data structure. When we do rollback, we move to the node that represent the rolled-back-to state.

In this problem, there are actually $$$2$$$ types of rolling back: the actual rollback operation, and the remove $$$k$$$ last numbers operation.

Let's solve the problem without actual rollback first. For the adding $$$x$$$ and removing $$$k$$$, we basically have a "prefix tree" of the states, the array at each node is just all the numbers on the path from the root to that node. When we get a removing $$$k$$$ operation, we just go $$$k$$$ node to the root.

So we need a data structure that support the following operations:

This can be done with binary lifting. You will get MLE if you try to implement the binary lifting with $$$O(nlog(n))$$$ memory, but it won't be a problem if you use the $$$O(n)$$$ memory implementation. You can check this blog out if you're interested: https://codeforces.com/blog/entry/74847

Regardless of how you implement binary lifting, you will get $$$O(log(q))$$$ time per operation, but we can actually do this in $$$O(1)$$$:

There might be different ways to explain it, but we can prove by contradiction:

So after all that, we know that we can get any $$$k$$$-th ancestor of the current node by checking what is the last node that has the target height. This is $$$O(1)$$$ insert and query by just saving the last node at each height whenever we insert a node.

So now we know how to go to the correct node, what about calculating the answer?

Realise that the answer when we insert a new value to the array is just whether this value is new or not. We will use the same idea here, the answer for a node is the answer at the parent node + whether this node is new.

To check if a value is new, we can use some sort of persistent data structure, but this would be $$$O(qlog(q))$$$ time and memory, and would almost certainly give you MLE. The way to check if a value is new is in fact pretty similar to the way to find the $$$k$$$-th ancestor in $$$O(1)$$$:

new when inserted, is $$$v$$$.After all that, we can insert, go to $$$k$$$-th ancestor in $$$O(1)$$$. We also calculate the answer for each inserted node in $$$O(1)$$$. So how to add the actual rollback operation?

We will handle the normal rollback with a stack, this is pretty classic, think of it as the call stack in DSU rollback and such. Whenever we insert or move to a new node, we will add that node to the stack. When rollback, we simply have to go to the previous node. Of course, this introduce the problem of the "last time a height appear" and "last time a value appear" array being wrong.

To solve that, instead of just storing the last value, we also store stacks. When we pop from the rollback state stack, we will check and pop from the corresponding stacks as well. This is of course $$$O(1)$$$ because at each node, we only change at most 1 value in each array.

You can find my implementation here: 219006017

UPDATED: Since this solution also only modify $$$O(1)$$$ values for every operation, you can also just store all the changed value + original value in the stack to do rollback.

My binary lifting with $$$O(n \lg n)$$$ memory passed. $$$10^6 \log 10^6 \times 32$$$ bits $$$\approx 76$$$ MiB only.

Why I am getting WA in C can any one explain 219004421

Your code only works for the prime GCDs only. Non-prime GCDs will be skipped.

Your permutation for n=12 doesn't contain the pair (6,12) and hence 6 is missing from the array d.

I think you should use another method to make the E2 an online version of E1, such as encoding the queries.

flushing the result can be super slow in some languages. Actually, i used GPT to translate the code of jiangly's into Python. Problem E1 took only less than 900ms while Problem E2 showed TLE. This is really sad.

i dont get this pandering to different languages aside from a general "not setting constraints too tight" perspective.

is it reasonable in any field to say "you are allowed to do a worse job because you chose a wrong tool?". Ofcourse this doesnt mean problems should only be solvable in c++17, rather that you dont forcefully have to ensure every problem is solvable in python.

I mean, after all, it wouldn't hurt to change the problem to make it possible to solve in different languages. The key to solving the problem doesn't change at all.

In this problem, i believe Python is not that of a "wrong tool" except for its poor performance in flushing, which i think should not be a constraint in solving the problem.

I don't expect any problem to be solvable in any languages like Python, but I think in this problem, the problemsetter can do better.

retarded take

Your code for B doesn't even work for sample inputs.

Can someone please give me intuition or some good explanation for D it will be quite helpful

The problem B reminds me a lot of 1836B. Though I know my difficulty in solving it probably comes down to a lack of skill, I still don't think a problem with such a complicated & unclear statement is suitable, especially for Codeforces contests(strictly limited time).

btw, the tutorial code of problem B can't even pass the example testcase. Not a big deal tho, just a little funny.

Here is my Approach using Graph for C Link

Nice

Today's round proved that many authors != good problems

i didn’t even read problem B. What is the logic behind this as div2 B? Can you answer? You are writing a Problem statement not an essay! Specially to say this is div2 B man!

I think some rules should be applied in CF to write problem statements.

problem B is confusing ,is not it?

oh hell it is.

For E2 we only need to maintain the first occurence of each number in array $$$a$$$ and the value at each position in $$$a$$$. If we maintain these, then if we delete $$$k$$$ numbers from the back, we only need to set the current length of $$$a$$$ to $$$len-k$$$ and the answer to the answer of length $$$len-k$$$, where $$$len$$$ is the current length. We don't need to rollback all these $$$k$$$ elements. Then when we add an element $$$x$$$, we only need to check if the first occurence of $$$x$$$ is earlier than the current length and the value at the position is indeed $$$x$$$. For rollback operation we only need to simply rollback all modifications of any

variables. The modifications can be stored in a stack. Time complexity is $$$O(n)$$$ and the implementation is really simple. 218993941Here's a very simple solution to E2 that works on $$$O(q)$$$ time. It uses a similar idea to the editorial: we keep a large array $$$A$$$ and a value $$$L$$$ such that $$$a$$$ is exactly the prefix of $$$A$$$ of length $$$L$$$. We also keep two auxiliary arrays, also with large size, with the following invariants:

Then, to delete $$$k$$$ elements, we can simply decrement $$$L$$$ by $$$k$$$.

To insert an element $$$v$$$, we can detect that it's a duplicate iff $$$occ[v] < L$$$. Then, we should set $$$vals[L] \gets v$$$, and $$$distinct[L+1] \gets distinct[L] + [occ[v] \ge L]$$$, and set $$$occ[v] \gets \min(occ[v], L)$$$. We also might need to clear out the original state of $$$occ[vals[L]]$$$: if originally $$$occ[vals[L]] = L$$$, then we should first invalidate that by setting $$$occ[vals[L]] = \infty$$$ (which is legal by our relaxed condition on $$$occ$$$).

These two operations both simply do $$$O(1)$$$ array/integer updates, so we can store all updates in a stack to roll back in also $$$O(1)$$$.

Answering queries is simply printing $$$distinct[L]$$$.

Submission: 219008803 219008852

exactly the same as my solution XD

Problem B was really weird to me and it got even weirder when I saw how many people solved it

your solution of problem B doesn't work for the first test case !!!!!!!!!!!!!

I am really confused why there is an easy version of problem E. I kept thinking about the reason behind making the queries offline, while the solution for E2 is somewhat more intuitive xD.

in problem C : can anyone please tell me why I am getting wrong answer 218983298 I have used the idea of printing n, n/2, n-2, n/2 — 1, ... so on and at the end all the missing values.

See the testcase bro on which your code is failing 12 6 10 5 8 4 2 1 3 7 9 11 It has 5 distinct gcds -> 6,2,5,1,4 But it is not optimal permutation for n = 12. Optimal is 1 2 4 8 3 6 12 5 10 7 9 11 It has 6 distinct gcds -> 1,2,4,3,6,5

thanks!

Quick Editorial, Nice.

It seems that there is an issue with the solution for problem B, the sample cannot pass

Was hoping a separate tutorial for E1. Any ideas how to do E1 ?

Here is my implementation of E1: 219013362

The idea is to keep the operations performed on the array in the form of a tree. The root, $$$0$$$, means that you haven't performed any operation. Now when you add $$$v$$$ to the array, you create a new node that has $$$0$$$ as a parent (and you now move to this node as it represents the current state you are in).

At any point in time, the values in nodes from the root to the current node will be the values in the array, in order.

To perform $$$- k$$$ queries, you have to move $$$k$$$ times to your parent. It can be done efficiently by using binary lifting.

Finally, $$$!$$$ just means that you should go back to the previous state of the datastructure (you can just keep a stack of the different states).

You will also remember the node that you were at during the $$$?$$$ queries. Now just perform dfs on the tree, when you arrive on a node you add the value to the array, when you get out of a node you remove it.

Thanks! Looks good. I will try to implement this.

For problem c I have found largest prime number from 1 to n then from largest prime to 2 found its multiples within n . To avoid duplication created one visited array. Is this approach is wrong? Here is my code 219004421

Yes, if you just keep visiting to the next multiple then the gcd of those two numbers will be the prime itself.

Video Editorial for Problem B

The editorial code for B is giving WA on the 1st test case only lol

Can anyone explain the solution to D?

I got lost after

`Now, calculate the new dynamics dplen for the length len=r−l+1 of the segment of ones, which equals the maximum length of a subsegment of zeros that we can obtain. Update this value with max(prefl−1,k−x,sufr+1,k−x)`

I dont understand too, its weird that the max 0's segment is right after or before the max 1's segment.

Did you understand yet, why those two segments should be adjacent?

It isnt adjacent. The pre[i][j] mean the max 0's segment in [1, i] and use no more than j operations. If you read the tutorial more carefully in the second paragraph, you will see that the author update the pre[i][j] from max 0's segment that end with i and use j operations to max 0's segment in [1, i] and use no more than j operations.

Oh i have understood. The pre, as author has explained, mean the max 0's segment that use no more than j operations and have position no more than i. The suf is similar.

Now return to the problems. You can just calculate the answer by run all l1 can be in the answer (obviously it's just from 0 -> n the string's length is only n how can it be bigger =)) ). with each l1, you will calculate the max l0 if the max 1's segment is l1

How can we calculate it ? we can just assume that the max 1's segment is from l to r. we will check how many operations we need to use to make that segment become all 1. We call the number of operations is x. Obviously we only have k — x operations to make the 0's segment as big as possible. so we will use this k — x operations or in the 1 to l — 1 segment or r + 1 to n segment. if we use k — x operations in 1 to l — 1 segment, the answer is pre[l — 1][k — x]. Similar with r + 1 to n

Tutorial of D:

Solutions with complexity O(nk logn) and O(nk) using various optimizations of the dynamics (convex hull trick, D&Q) also exist.D&Q is probably meant to be D&C (divide and conquer).

author's solution for B is giving me wrong answers when I test it on the sample input, I even tried submitting it (you can check my submissions), am I doing anything wrong?

Author's solution is failing on the first pretest? That sure is SomethingNew (but what does that make the author?)

Why this contest get down vote i think the problems are very good

I think mostly because of the problem B just confuses the hella people out. Other than that the problems seem fine.

Awesome contest , thanks for the authors

The Code given in the editorial for B is wrong , pakhomovee please update it 219020834

Video editorial for problems A&C: https://youtu.be/8HABUgytApk

Thought would be useful for newbies(some of the pupils)

https://codeforces.com/contest/1858/submission/219013214

Can anyone please provide a counter example for my code? I have been trying to find a counter example by stress testing my solution against the correct ones on Codeforces, but I still cannot find a counter example.

UPD: I just fixed it, and the problem was I forgot to consider the case where the optimal ways to plant trees consists of no oaks

I will described my idea for the E1, I don't sucess to proof it or to code it but think it's true :)

I use "offline queries", I use a stack and an occurrences tables, when there is a "!" I pop the last element of the stack wich contains only values of the structure. When it's a "-" I pop the n-first from the top element of the stack.

With that, we can compute the final "?" in O(n). After the idea of my solution is "We can deduce the "?"^(i-1) with the i.

From the actual state, we erase all the values wich were add after the "?"^(i). Next, will remember all the actions before the "?"^(i) which were erased by a "!" and we'll add they in the stack.

I hope that was clear. SORRY FOR MY POOR ENGLISH :)

Memory limit was tight on D. I failed with a 280MB solution. Also, is there a lag between submission time and when the judge sees the submission as submitted? I submitted around 2-3 seconds before the end of the contest, but by the time it loaded the judging page (10 seconds later), it came with a popup 'contest is over'. At least I did not lose out on an accepted submission because I had overflow there (shorts, used to save memory, were overflowing).

Thanks for fast editorial!

The problem of B is too long.

Here is a clean solution for C in c++: ``` void solve() { int n; cin >> n; unordered_set v;

} ```

di=gcd(ai,a(imodn)+1)

How does a((i mod n )+ 1) make sense? We'd mod it and then increase the index by 1, this mean it could go out of bounds right? Can someone explain this statement?

"i" denotes 1 based indexing hence it is in fact correct

Thanks man

Thanks for fast editorial!

I think this one I'm getting a bit better, as I managed to solve A and almost came so close to solving C. I didn't solve B because I kinda don't get how it works and I saw that more people solve C.

For problem A, I saw that if

`a + c > b + c`

then it's always 'First', since the first player to press will always win because they have more buttons.When

`a + c == b + c`

, there are two cases: Either c is divisible by 2, then the second player will always win (they came out last), or c isn't, which the first player will win.When

`a + c < b + c`

, the second player will always win.For problem C, I only saw that the after

`a1 = 1`

, we can put factors of 2, then factors of 3, etc. until we filled the permutation. That's the reason why I didn't get the final test of the pretest 1 correct because for '10' the answer will be`1 2 4 6 8 3 9 5 10 7`

, which isn't correct.I feel proud solving B.

about x13837 participants can solve C but only x5448 participants can solve B

This contest helped me find my weakness.

Thanks.

Personally,I think if B could be described more clear,it is easier than C

In Q>B Does petya eat first cookie at 1st chair or before 1st chair?. Que ki maa chodna koi inse sikhe

Amazing!

Problem B: Could someone clarify the reasoning behind selecting the initial and final segments as 1 — d and n + 1 consecutively for me?

Why put 1 — d in problem B and not 1 initially? She is supposed to eat first cookie at 1st position or not?

Petya would indeed eat a cookie at index 1, no matter what. If you by default put index 1 as a seller, then you would need to differentiate that from the case where you actually are given index 1 as the seller. When you actually have a seller at index 1, it might contribute to the ans (if removing it gives minimum cookie count).

Try this testcase:

1

7 3 2

1 3 5

Expected output:

4 3

How is the case where he eats the first cookie handled in the second problems?

deleted

I'm stuck there as well, can you explain it to me please?

intitally, pre[i][j] is equal to max length of segment of 0's

ending at and including position iand usingexactly joperations.We want to calculate new pre[i][j] which is equal to max length of segment of 0's till position i (not necessarily including position i) and using at most j operations (and not exactly j operations).

So, we need to update pre[i][j]. Note that when we are trying to update pre[i][j], pre[i-1][j] and pre[i][j-1] have already been updated,i.e., pre[i-1][j] is equal to max length of segment of 0's till position i-1 (not necessarily including position i-1) and using at most j operations (and not exactly j operations)---and similarly for pre[i][j-1].

Now, we can update pre[i][j] using the following 2 lines:

pre[i][j]=max(pre[i][j],pre[i-1][j])

pre[i][j]=max(pre[i][j],pre[i][j-1])

The above 2 lines would work, because the NEW pre[i][j] has only 3 options:

it can be equal to old pre[i][j], which is equal to max length of segment of 0's

ending at and including position iand usingexactly joperations.it can be equal to new pre[i-1][j],which is equal to max length of segment of 0's till position i-1 (not necessarily including position i-1) and using at most j operations (and not exactly j operations)

it can be equal to new pre[i][j-1],which is equal to max length of segment of 0's till position i (not necessarily including position i) and using at most j-1 operations (and not exactly j-1 operations)

new pre[i][j] will be max of above 3 options.

Thanks for the detailed explanation.

Thanks for the detailed answer. I have a basic beginner's question here. How would someone be able to even think of this? What kinds of questions should be solved beforehand in order to even think in such a direction?

For me the following has worked:

I have seen enough solutions (directly, without trying to solve on my own) of many DP problems rated around 1900-2100. So, the moment i saw this problem, i was able to understand that there is a high chance of DP(although i still couldnt solve it in contest), since you can either change a 0 to 1 or 1 to 0 (transitions/choices).

You need to solve many DP problems(or atleast just see the solutions-to familiarise yourself with patterns) in order to identify DP in such questions.

In short, the answer is "just solve problems". There is no other way.

Yeah, that makes sense. Thanks.

did anyone solve task E1 using binary lifting?

here is my code

Can someone tell what's wrong in 219096582 solution for D?

pakhomovee why does 219102302 gets timeout?

I believe the problem is that your solutions works in $$$O(nk\log{n} + n^{2})$$$ and is implemented using

`std::set`

, which has quite a big constant, and, therefore, slows down your solution :(I'd recommend you to think of an $$$O(nk+n^2)$$$ solution if you haven't read the editorial yet since there are quite many different dynamic programming solutions you can come up with!

Is there a video editorial for E?

Can anyone explain why the number of points where Petya will eat cookies between [a,b] is (b-a-1)/d ?

Sure!

Actually, we want to calculate the number of cookies Petya will it on a half-closed interval $$$[a;b)$$$ if there are no cookie sellers on this interval and there is a cookie seller at point $$$a$$$. He will eat cookies at points $$$a$$$,$$$a+d$$$,$$$a+2d$$$ and so on. The number of cookies Petya will eat is equal to the number of times we can add $$$d$$$ to $$$a$$$ so that $$$a+k\cdot d < b$$$ (plus 1, since he will also eat a cookie at $$$a+0\cdot d = a$$$). Let's write out the numbers $$$a,a+1,a+2,\ldots,b-1$$$ and subtract $$$a$$$ from them. Now we need to calculate how many numbers are divisible by $$$d$$$ (or equal to zero, which is also divisible by $$$d$$$) among $$$0,1,2,\ldots,(b-a-1)$$$. It is easy to see that the number we need is $$$\left\lfloor\frac{b- a - 1}{d}\right\rfloor+1$$$ (there are $$$(b-a-1)$$$ numbers which are greater than zero, and zero which we take into account separately).

Hope this helps!

Thanks very much for helping

I tried solving problem $$$E$$$ using persistent segment tree.

I tried to increase the memory limit but I got WA.

can someone tell what is wrong ,here is my submission (the same solution got WA after putting 1000 megabytes memory limit) : 219115174 .

Can anyone tell me what's wrong in this approach ?

can someone please explain me this line in problem B while calculating pref[0]--->no. of cookies eaten until first stall (given m stalls position in stalls[]) pref[0] = 1 + (stalls[0] + d — 2) / d; (d->given in question)

please, specify the problem statement and make it easier to understand, worst problem B i have ever seen in my life....:/

I have a doubt in Problem D dp defination of pref[i][j]. Does it mean longest segment of 0 ending at i index with exactly j operations or this longest segment of 0 can end anywhere before i index as well.

i think d is difficult...

Isn't code of problem D different from that of tutorial? Can anyone tell me what's wrong with my approach? Any short testcase where this code fails? https://codeforces.com/contest/1858/submission/219023351

For test case -

4 1 1101 Your output — 4 5 7 9 Correct — 4 6 8 10

Please suggest some resources to learn number theory.

for n=10 is this permutation is wrong, whose score is 22? 1 2 4 8 3 6 9 5 10 7

Guys I want some friends with whom I can do cp, So, if any one who loves problem solving we could somehow connect.

I have a question in B. \n 8 3 9 \n 2 8 9 10 \n why can't i remove the first seller?

is there any solution of problem D trees and segment using Lichao trees?

B is quite easy to understand, solution is also intuitive. Just another ad hoc number line problem. Why complaints?

Can someone help me debug D. Its giving WA in TC 9 which is very large. Link — https://codeforces.com/contest/1858/submission/227510370 . My code is very similar to editorial one.

I like this coding style.

in

problem Dwhere this greedy approach fails? for $$$j > 1$$$ it is always better to keep longest substring of $$$'0'$$$ because even if we replace one $$$'1'$$$ (which is adjacent to this longest substring of $$$0$$$) with $$$'0'$$$ it results in j — 1 change in answer and since $$$j > 1$$$ so $$$j - 1$$$ is positive.WA submission

I tried to solve E1 using Trie, however I get WA as the result. Can anyone help me point out where I went wrong?

My submission