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

thanks for fast editorial

thanks for the quick editorial :)

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

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

where is E1?

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

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?

The title wrongly mentions the round as 892.

B was a little weird.

is problem B designed to prevent contestants from using ChatGPT?

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

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

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

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

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

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

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

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

Maybe E should give 512MB.

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 ?

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 1

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

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.

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

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:

• Add a child to the current node.
• Go to the $$$k$$$-th ancestor of the current node.

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.net/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)$$$:

• Let's keep track of all the positions that the current node has been. I.e. keep a list of all the node we are at after each query, call this list $$$S$$$.
• Let's say the current node is $$$u$$$, the $$$k$$$-th ancestor is $$$v$$$.
• Then the $$$v$$$ and be the last node in $$$S$$$ that has the same height as $$$v$$$ is the same.

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

• Assume that the last node in $$$S$$$ that has the same height as $$$v$$$ isn't an ancestor of $$$u$$$.
• Then we know that from that node, we have to use a $$$k$$$-th ancestor operation that go to a height lower than that of $$$v$$$ (otherwise we will always be in the subtree of the node, and the node would be an ancestor)
• After that, we have to get from said lower height to the height of $$$u$$$.
• But the only way to get more height is to add a new node.
• Which mean that to get to the height of $$$u$$$, we have to increase the height once by once (can also go back), but there must exists a node that appear later than $$$S$$$ that has the same height as $$$v$$$.
• This contradict the assumption that we start at the last node.

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

• Let's say we inserted node $$$u$$$ and has value $$$x$$$.
• Let's say in $$$S$$$ (defined similarly as above), the last node with value $$$x$$$, that is new when inserted, is $$$v$$$.
• If $$$v$$$ is an ancestor of $$$u$$$ then clearly $$$x$$$ is not new. This can be checked by checking what $$$u$$$'s ancestor at $$$v$$$'s height is.
• Otherwise, $$$x$$$ must be a new number at $$$u$$$. The proof is pretty similar.
• Because $$$v$$$ isn't an ancestor of $$$u$$$, and $$$v$$$ is new, once we get out of the subtree rooted at $$$v$$$, there is no value $$$x$$$ in all the ancestors.
• Because we know there is no value $$$x$$$ aside from $$$v$$$ in the way from $$$v$$$ to $$$u$$$ in $$$S$$$, we can guarantee that no ancestor of $$$u$$$ that is in that range has $$$x$$$.
• From the 2 points above, $$$x$$$ is new at $$$u$$$.

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.

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

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.

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

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

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

Here'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:

• $$$occ[v]$$$ is the minimum index that the value $$$v$$$ occurs in $$$A$$$ (the editorial uses a set, but this is not necessary). We'll relax the condition a little further: if the first occurrence of $$$v$$$ is after $$$L$$$ (outside of $$$a$$$), we'll also allow $$$occ[v]$$$ to be $$$\infty$$$ instead.
• $$$distinct[i]$$$ stores the number of distinct elements in the prefix of length $$$i$$$, and must be correct for all $$$0 \le i \le L$$$; for $$$i > L$$$, it can be anything.

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

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

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.

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

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)

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?

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

Awesome contest , thanks for the authors

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

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

https://codeforces.net/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

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.

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 feel proud solving B.

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

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

deleted

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?

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 ?

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 .

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.net/contest/1858/submission/219023351

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?

I like this coding style.

in problem D where 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