Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### pakhomovee's blog

By pakhomovee, history, 3 months ago, We hope you liked our problems!

1858A - Buttons

Tutorial
Code

1858B - The Walkway

Tutorial
Code

1858C - Yet Another Permutation Problem

Tutorial
Code

1858D - Trees and Segments

Tutorial
Code

1858E2 - Rollbacks (Hard Version)

Tutorial
Code

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. Tutorial of Codeforces Round 893 (Div. 2) Comments (176)
 » 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！
 » 3 months ago, # | ← Rev. 2 →   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.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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
 » 3 months ago, # | ← Rev. 2 →   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.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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 837653445shouldn't the answer be 52 after removing the first cookie seller? These are the benches where petya can eat a cookie1 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 2then the winner in that case should be the first one right ?
•  » » Tell us why the winner will be the first one
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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 1
•  » » you 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 permutationour 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 valueslet'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 :(
 » 3 months ago, # | ← Rev. 2 →   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.com/blog/entry/74847Regardless 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: 219006017UPDATED: 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).
•  » » 3 months ago, # ^ | ← Rev. 2 →   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
 » 3 months ago, # | ← Rev. 2 →   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. 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
•  » » 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
 » 3 months ago, # | ← Rev. 2 →   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: 219013362The 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   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 l1How 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
 » 3 months ago, # | ← Rev. 2 →   The Code given in the editorial for B is wrong , pakhomovee please update it 219020834
 » Video editorial for problems A&C: https://youtu.be/8HABUgytApkThought would be useful for newbies(some of the pupils)
 » 3 months ago, # | ← Rev. 2 →   https://codeforces.com/contest/1858/submission/219013214Can 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; FOR(i, 1, n + 1) { for (int j = i; j <= n; j *= 2) { auto a = v.find(j); if (a != v.end()) break; else { cout << j << " "; v.insert(j); } } } cout << endl;} 
 » 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
 » //This is a easy solution code for C++ which time complexity is O(N) #include using namespace std; int main() { int t; cin >> t; while (t --) { int a, b, c; cin >> a >> b >> c; if (c % 2 == 0) { if (a > b) { cout << "First" < a) { cout << "Second" <
 » 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?
 » How is the case where he eats the first cookie handled in the second problems?
 » 3 months ago, # | ← Rev. 6 →   deleted
•  » » I'm stuck there as well, can you explain it to me please?
•  » » » 3 months ago, # ^ | ← Rev. 3 →   intitally, pre[i][j] is equal to max length of segment of 0's ending at and including position i and using exactly j operations.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 i and using exactly j operations. 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?
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   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.
 » 3 months ago, # | ← Rev. 3 →   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
 » 3 months ago, # | ← Rev. 2 →   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 ? void solve(){ int n, m, d; cin>>n>>m>>d; _vi v(m); mapmp; for(auto &it : v) { cin>>it; mp[it - 1]++; } _vi eat(n, 0), left(n), right(n); int c = 0; eat++; c++; int left_cookie = 0; for(int i = 0; i < n; i++) { if(i - left_cookie >= d) { left_cookie = i; eat[i]++; } if(mp[i]) { eat[i]++; left_cookie = i; } if(i > 0 && eat[i])c++; } debug(c); left_cookie = 0; for(int i = 1; i < n; i++) { if(mp[i]) { left[i] = left_cookie; } if(eat[i])left_cookie = i; } int right_cookie = n; for(int i = n - 1; i >= 0; i--) { if(mp[i]) { right[i] = right_cookie; } if(eat[i])right_cookie = i; } int ans = INT_MAX; int cnt = 0; for(auto &pa : mp) { if(pa.second == 0)continue; int ind = pa.first; // debug(ind); int l = left[ind]; int r = right[ind]; if(abs(l - r) >= d) { int curr = c; if(c == ans) { // ans = c; cnt++; }else if(c < ans) { ans = c; cnt = 1; } } else{ int curr = c - 1; if(c == ans) { // ans = c; cnt++; }else if(c < ans) { ans = c; cnt = 1; } } } cout<
 » can someone please explain me this line in problem B while calculating pref--->no. of cookies eaten until first stall (given m stalls position in stalls[]) pref = 1 + (stalls + 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
•  » » 3 months ago, # ^ | ← Rev. 2 →   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.
 » 3 months ago, # | ← Rev. 2 →   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.