### MarkBcc168's blog

By MarkBcc168, history, 3 months ago,

Thanks for participating. We apologize for problem F that has appeared before. Still, we hope you all enjoy our round!

## 1705A - Mark the Photographer

Author: MarkBcc168

Hint 1
Hint 2
Tutorial
Code

## 1705B - Mark the Dust Sweeper

Author: MarkBcc168

Hint
Tutorial
Code

## 1705C - Mark and His Unfinished Essay

Author: MarkBcc168

Hint 1
Hint 2
Hint 3
Tutorial
Code

## 1705D - Mark and Lightbulbs

Author: MarkBcc168

Hint 1
Hint 2
Hint 3
Tutorial
Code

## 1705E - Mark and Professor Koro

Author: abc241

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Code (Bitsets, by errorgorn)
Code (Lazy Segment)

## 1705F - Mark and the Online Exam

Author: MarkBcc168

Unfortunately, a harder version of this problem has appeared in a Chinese contest here and here. You can look at their solution here. We thank many contestants who pointed it out.

Hint 0
Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Code

• +121

 » 3 months ago, # |   0 Auto comment: topic has been updated by MarkBcc168 (previous revision, new revision, compare).
 » 3 months ago, # |   0 Can you continue in the sun time next time?
 » 3 months ago, # |   +14 So fast Editorial...Love it.
•  » » 3 months ago, # ^ |   +11 The editorial with hints is excellent :)
 » 3 months ago, # | ← Rev. 2 →   +23 C was nice
 » 3 months ago, # |   +25 A and B were normal. C was kinda nice. D felt kind of easier than normal.
 » 3 months ago, # |   -12 why my solution is giving memory limit 164324383
•  » » 3 months ago, # ^ | ← Rev. 5 →   +1 C in that problem can be up to 40, so the string can have a length of up to n times 2 powered by 40. That is because the string can be "duplicated" if they simply spam 1 as L and the current length of it as R, so it becomes twice as big. But you can not make a string of that size, because it takes too much memory, so you get MLE.
•  » » » 3 months ago, # ^ |   -8 Oh okay, I got it..Thanks a lot.
•  » » » 5 weeks ago, # ^ |   0 Cn u check my submission and tell why am I getting TLE on this: https://codeforces.com/contest/1705/submission/170049529
•  » » 3 months ago, # ^ |   0 l, r⩽10^18, means r-l ⩽ 10^18 this is already a large value, even if we do not take into account that q can be of the order of 10^4
•  » » 3 months ago, # ^ |   0 pay attention to the range of data, especially 1e18.
 » 3 months ago, # |   0 For C: https://codeforces.com/contest/1705/submission/164336489 why this code give TLE. and how to remove TLE? please tell
•  » » 3 months ago, # ^ |   +6 Note that the length of the string can be upto $2^{40}\cdot 200000$ because the copying operation could be $[1,n]$, $[1,2n]$, $[1,4n]$, $\dots$, $[1,2^{39}n]$.Your solution has a loop from l to r, which varies by the length of the string. Therefore, it can never loop through in time.
•  » » » 3 months ago, # ^ |   0 ok Thanks a lot!
 » 3 months ago, # | ← Rev. 3 →   +8 Good Tasks for Codeforces Round #807) Editorial is perfect.
 » 3 months ago, # |   +5 So fast Editorial！！！！！
•  » » 3 months ago, # ^ |   +4 you are 607 mouse ?
•  » » 3 months ago, # ^ |   +4 you are 607 mouse ?
 » 3 months ago, # |   +12 Problem C was just awesome <3
 » 3 months ago, # |   +14 Thanks for the superfast editorial, interesting round with mArK!
 » 3 months ago, # |   +5 If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints. Disclaimer: There is a quota of 1 request per 24 hours on the free plan.
 » 3 months ago, # |   +2 Hints are always helpful.
 » 3 months ago, # |   +12 Wow, very fast editorial! I like this contest because the problems are easy to understand. Great job!
 » 3 months ago, # |   +9 I thik C is very nice
 » 3 months ago, # | ← Rev. 2 →   0 for me, D is more difficult than E even than F(though I didn't solve E or F because typing speed)
•  » » 3 months ago, # ^ |   0 I am sorry to keying D as C
 » 3 months ago, # |   +1 So fast Editorial！！
 » 3 months ago, # |   +9 Question D is so difficult
 » 3 months ago, # |   +5 Amazing tutorial! It made me everything easy to understand.
 » 3 months ago, # | ← Rev. 2 →   -28 very terrible contest. C easier than B and too easy. F appeared before. E is DS. In F you get the same result when Wrong Answer and when too many queries. Downvoted. why do you all say quick editorial? does it make the contest less bad in any way?
•  » » 3 months ago, # ^ |   +16 wheather a problem is easy or not depends on personal opinions,ds is good,it's not easy to find out F appeared before
•  » » » 3 months ago, # ^ |   0 It is actually very easy, sir.
 » 3 months ago, # |   0 The tutorial for D "Moreover, if a1,a2,…,ak are the positions of 1's in s and b1,b2,…,bk are the positions of 1's in t. " , should here s/t be s¯¯¯ and t¯ ?
•  » » 3 months ago, # ^ |   0 Great catch! Fixed.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 In problem F editorial If the difference is +1, then both answers must be F. If the difference is −1, then both answers must be T. should we replace ±1 on ±2?By the way, do you know an algorithm which finds all answers faster than 2n/3 questions (without randomization)? just curious
•  » » » » 2 months ago, # ^ |   +1 Fixed, thank you.The Chinese problem linked above has a much stricter query limit. I haven't checked their solution yet, so I cannot guarantee that it gives a faster deterministic algorithm. Feel free to check it out!
 » 3 months ago, # |   0 which topic i should learn for solving problems as C?
•  » » 3 months ago, # ^ |   0 There is no specific knowledge required to solve C. You can try reading the hints and tutorial provided above.
•  » » » 3 months ago, # ^ |   0 ok i got it but always i solve A, B in div2 but i cant solve any C problem in div 2 could you give me some tips for improving) thx
•  » » » » 3 months ago, # ^ |   0 the best way to improve at problems like div2C is through problem solving and gaining experience
•  » » » » 3 months ago, # ^ |   0 Practice more div2Cs would be OK.Try to solve them as quickly as you can.
•  » » 3 months ago, # ^ |   0 C is just about implementation
•  » » 3 months ago, # ^ |   0 I though the observation that for each query you have to travel back through the (c<=40) operations was the hardest part.
 » 3 months ago, # | ← Rev. 2 →   0 It was super hard for me. I should do more practice
 » 3 months ago, # | ← Rev. 4 →   +7 it's funny how bitset codes pass (in E) but my std::set solution TLE'd until i replaced them with fenwick trees desperate pretentious and angry comments...which WA'd, but I still desperately claim my solution was correct, as it does the only normal thing that the problem could ask: maintain a huge base two number and add/subtract powers of two to it. Also, apparently std::sets are at least 10 times slower than a fenwick tree, as the fenwick tree solution got ~200ms, and the std::set got >2000ms. Happy summer holiday guys
•  » » 3 months ago, # ^ |   +5
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +3 This made my day a whole lot better i will just go and jump off a cliff now. Thank you, stranger
 » 3 months ago, # |   0 Very fast nice
 » 3 months ago, # |   0 very fast editorial
 » 3 months ago, # |   +61 D was really good. I don't know why I find such kinds of problem a bit hard. I wasn't able to come up with the invariant that sum of $(01)$ and $(10)$ is constant. Can someone suggest set of problems like $D$ (where I need to recognise an invariant)?
•  » » 3 months ago, # ^ |   +3 Same bro :(
•  » » 3 months ago, # ^ |   +2 It is easy to come up with solution for D by observing carefully. Say we have 10001 then we can convert it to 11101 -> the first block of 1 got expanded to last continuous 0 we had Say we have 11101 then we can do the opposite and convert it to 100001 -> the first block of 1 got compressed to first continuous 1 we had This is for left to right . U can observe similarly for right to left. Now this implies that if i have some block of 1 i can always expand(through continuous zeroes and stop before last zero) or compress it(through continuous ones and stop after 1st one). So we can easily notice that -1 case will be when count of blocks of 1 in s and t are different. Also there is that case for first and last character to be same which can also be deduced by the observation since when expanding [x,y] to [l,r] (ly) element at l and y will never change.There we you can now just expand and compress these blocks greedily and make them same now.
•  » » » 3 months ago, # ^ |   +3 this was my sol as well.
•  » » 3 months ago, # ^ |   0 Same
•  » » 3 months ago, # ^ |   +2 One perhaps easier solution is, if you separate the bit string into substrings containing either only ones or only zeros, you realize that the operations we can do only allow for moving borders between neighboring substrings. Then the solution exists only if the order of the substrings is matched and the minimal number of operations is calculated by differences in positions of borders of the substrings.
•  » » 3 months ago, # ^ |   +5 I think the invariant that the number of chunks of 1 stays the same is easier to be observed.
•  » » 3 months ago, # ^ |   +1 Same for me :/After the contest I continued to try and solve D and was surprisingly able to come up with a constructive solution that works, but it was hell to make. As a new expert who hasn't solved that many Ds before I was very pleased to read the editorial and realize that what I did wasn't the expected smart solution.Here is my code (it isn't pretty, but I will never touch it again): 164362277
•  » » 3 months ago, # ^ |   +5 I only solved that problem b/c I saw 3+ similar problems in the past and I knew which direction to push my solution in, if that makes any sense.
•  » » 3 months ago, # ^ |   0 This could be helpful: https://codeforces.com/blog/entry/85172 (there is one problem with an invariant)
 » 3 months ago, # |   0 my english is not well, so at that time ,i forgot this race ,however, i think there exit a long way for me to aprove my algorithm
 » 3 months ago, # |   0 So fast editorial and fantastic contest!
 » 3 months ago, # |   0 C was kinda hard for me, but I really enjoyed solving it. Great problem
•  » » 3 months ago, # ^ |   0 yeah I got the idea from josephes problem finding the value of index in previous recursion using mathematics
 » 3 months ago, # |   0 Thanks for the fast tutorial ...
 » 3 months ago, # |   0 Enjoyed this contest — definitely has a good math olympiad flavor to it (both problems and solutions)!
 » 3 months ago, # |   +9 Does qn D answer overflow int ? passed three pretests then failed.
•  » » 3 months ago, # ^ |   +1 The maximum possible answer is on the order of n^2, so yes, there is an overflow, and you have to use long long.
•  » » » 3 months ago, # ^ |   0 Yup that was the problem,felt horrible to lose a qn like that,also i feel the bitmask soln is over complicated,all i did was checked that first and last same,the number of continuous groups of 1 same ,since a group of cont. ones can never split up or merge with another group of ones,then check if number of groups in s and t same ,then calculate distance by moving start and end points of each group in s to corresponding one in t.
 » 3 months ago, # |   +8 C was bit tricky for me, Good problemset overall. Happy Coding & Happy friday :)
 » 3 months ago, # | ← Rev. 4 →   0 This contest was great, I wish I hadn't had classes until 8:45pm (quite sad). Anyways, that's a rapid editorial.
 » 3 months ago, # |   -8 Thanks for fast tutorial and E was cool.
 » 3 months ago, # |   0 Does somebody have binary search solution for C?
•  » » 3 months ago, # ^ |   0 Not needed
•  » » 3 months ago, # ^ |   0 See my submission: https://codeforces.com/contest/1705/submission/164314488
•  » » » 3 months ago, # ^ |   0 Can you please explain your solution. Thanks
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 .
•  » » » » » 3 months ago, # ^ |   0 Thanks a lot
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 .
 » 3 months ago, # |   0 Awesome round and woah super fast tutorial. Absolutely loved it ❤️. C was special in many ways.
 » 3 months ago, # |   0 problem C was breathtaking for me :D
 » 3 months ago, # |   0 A and B was normal, but C was hard :)
 » 3 months ago, # |   0 Hi all, if any of you could please give suggestion on this, please do so. I am able to solve at least A problem but still get negative rating after contest.. could u please tell why does that keep happening... I have been a user here for a while but just recently started being active here... I recently learnt there is hacking phase here during contest after passing pretests. how can one lock their solution? and if someone uses your code, would that mean you will get penalty for it.. thanks in advance.
 » 3 months ago, # |   +22 Fun fact: something happened during testing of problem F related to different behaviours of different versions (and 64-bit or not) of g++ and we couldn't figure out the reason behind it, so I'm putting it here to see if anyone can offer some insights into the different behaviours, thanks in advance :DThis submission gets AC: Submission164341892I used some randomised heuristicsBut when I submit the same code in non 64-bit version, it gets WA: Submission164341855But once again when I remove two lines from the header it gets AC again, however, those two lines don't seem to be relevant at all to the algorithm: Submission164342019
•  » » 3 months ago, # ^ | ← Rev. 4 →   +32 It has to do with unsigned ints, in this case vector.size(). Casting all .size() values to int in the second submission makes it AC. Here's what I think is happening here:The first submission passes since you are dealing with 64-bit numbers on both sides, so converting unsigned to signed you get the same number even after overflow, so == works ok. Likewise for the third submission with 32-bit numbers. For the second submission, you convert a signed integer to an unsigned one in 32-bit (after some possible overflow), which is not the same as the signed int in 64-bit, so == doesn't work as intended. Removing #define int long long fixes this.Moral of the story: always cast .size() to a signed int to avoid situations like this.
•  » » » 3 months ago, # ^ |   0 Thanks a lot, that would explain what happened.
•  » » 3 months ago, # ^ |   +11 [unrelated] why are you removing the legendary line :( #define ick cout<<"ickbmi32.9\n" 
 » 3 months ago, # | ← Rev. 2 →   0 isn't the TL on D too tight? My code with long long int gives TLE but when I change long long int to int, it passes in 600ms.My solution is $O(nlog^{2}n)$. Was this done on purpose to cut the solutions of this logistic?
•  » » 3 months ago, # ^ |   +1 Based on our testing, the segment tree has a high constant factor that an $O(n\log^2 n)$ is very hard to pass. You should either use bitsets or aim for $O(n\log n)$. We apologize for the strict TL.
•  » » 3 months ago, # ^ |   -30 But $O(n log^2 n)$ is too much for a problem, that can be solved in linear time, so it's quite ok that your solution TLE-d.
•  » » » 3 months ago, # ^ |   0 I disagree, the $O(nlog^{2}n)$ solution was more obvious to me. I couldn't come up with that observation.
•  » » 3 months ago, # ^ |   +1 Can you share your Approach towards problem D?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 i was going to upvote your comment but by mistake i clicked on the downvote. i am sorry about that. I too want to know this seg tree approach.
 » 3 months ago, # |   +8 E, I would like to read a simpler version of the paragraph starting with "Proof: The upper bound is pretty clear...".What is the upper bound here? What exactly is decreasing?
•  » » 3 months ago, # ^ |   +3 This was written when there was the second operation (of deleting numbers). The editorial is updated now. Hope this eliminates your confusion.
 » 3 months ago, # | ← Rev. 3 →   +84 I'm very bad with segment trees, so I came up with the following solution for problem E. Let's maintain two sets $S$ and $T$ ("positive" and "negative" sets) such that $\sum 2^{a_i} = \sum_{s\in S}2^s-\sum_{t\in T}2^t.$The following properties should hold: No number appears in both $S$ and $T$. The largest element of $T$ (if it exists) is not equal to the largest element of $S$ minus $1$. The second property is important because it allows us to answer queries by taking the largest element of $S$ and subtracting $1$ if the largest element of $T$ is greater than the second largest element of $S$. (If the property didn't hold, we might need to deal with something like $2^6-2^5-2^4$.)To add $2^x$, do the following: If $x$ is in $T$, cancel it out. Otherwise, if $x$ is not in $S$, add it to $S$. Otherwise, remove the copy of $x$ in $S$ and add $2^{x+1}$ instead (recursively). Subtraction is entirely analogous. To maintain the second property, just check if it doesn't hold and if so, delete $x$ from $S$, $x-1$ from $T$, add $x-1$ to $S$, and check the property again.For all of these operations, we can do an amortized analysis by using $|S|+|T|$ as a potential function. The overall time complexity is $O((n+q)\log n)$ since we use sets to maintain the maximum.The implementation of this is very easy compared to the other solutions.
•  » » 3 months ago, # ^ |   0 In the complexity, how do you account for the 'recursive' updates? Is there a bound on the number of updates? (a constant factor maybe? Certainly not just $n + q$ updates)
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +3 That's what the amortized analysis handles, because all the extra steps that we do will reduce the value of $|S|+|T|$. You should be able to find some resources by searching "amortized analysis" and "potential method".
 » 3 months ago, # | ← Rev. 3 →   +3 Other simpler in understanding approach for D: (TC: O(q*n*logn)): s==t -> ans=0 basic check s[0]!=t[0] or s[n-1]!=t[n-1] -> ans=-1 create can_toggle[i] = (s[i-1]!=s[i+1]) want_toggle[i] = (s[i]!=t[i]) iterate from 1 to n-2 if want_toggle[i] = false, move on if want_toggle[i]=true -> get id>=i such that can_toggle[id]=1 (can use binary search or monotonous can_toggle queue too) if no such id present -> ans=-1 revert all want_toggle between i and id (i.e say add 1 to range[i,id] or other way xor with 1 for [i,id]) (use Binary index tree/segment tree Logn comes from here) ans += range[i,id] i.e id-i+1; using can_toggle[id] we reverted state of can_toggle[id+1] too, add this can_toggle[id+1] to our consideration if its true TLDR: for each want_toggle[i] we get just right can_toggle[i] and bring that can_toggle to current i by toggling id, id-1, id-2..... Idea comes from fact that when we use toggle at i the state of can_toggle[i-1] and i+1 changes.
 » 3 months ago, # |   0 Auto comment: topic has been updated by MarkBcc168 (previous revision, new revision, compare).
•  » » 3 months ago, # ^ |   0 in b what if the array is 3 0 0 0 0 2 0 0 4 how it work ??
•  » » » 3 months ago, # ^ |   0 Initially: 3 0 0 0 0 2 0 0 4 1 => 2 1 0 0 0 2 0 0 4 2 => 1 1 1 0 0 2 0 0 4 3 => 0 1 1 1 0 2 0 0 4 4 => 0 0 1 1 1 2 0 0 4 5 => 0 0 0 1 1 2 1 0 4 6 => 0 0 0 0 1 2 1 1 4 Now you can see that for clearing the rest, you need a minimum of (1+2+1+1) = 5 turns Total: 5+6 = 11 turns
•  » » » » 3 months ago, # ^ |   0 the array should be 0 0 0 0 1 2 1 1 4 6 not 0 0 0 0 1 2 1 1 4the final answer is 9+6
•  » » » » 3 months ago, # ^ |   0 thank bro^_^
 » 3 months ago, # | ← Rev. 2 →   +3 C is a nice implementation problem. It also gave me a lesson:BE EXTREMELY CAREFUL using int when you see anything like $x \le 10^{18}$ or $x \le 10^{12}$ . I literally spend ~1h struggling on C because of this :(
•  » » 3 months ago, # ^ |   0 Yes, you are right, I made a lot of mistake on $int$ and $long \ long$.In a contest, you can try this: #define int long long …… signed main() { } **** And when you use printf to output, don't forget to use "%lld" instead of "%d".
 » 3 months ago, # | ← Rev. 3 →   0 Can anyone please explain why for problem C, there is a runtime error in my solution. solution.......got my mistake.(solved)
•  » » 3 months ago, # ^ |   0 Coz of integer overflow. You need to use long long. Made the same mistake :")
 » 3 months ago, # |   0 Nice contest! Thanks for the fast editorial! :)
 » 3 months ago, # |   0 164338999 Can't understand why I am getting tle in C. Please help.
 » 3 months ago, # |   0 I followed the editorial solution but I'm getting error for a particular test case that isn't even visible and I can't figure out why. Any help!? Here's my solution: https://codeforces.com/contest/1705/submission/164347601
•  » » 3 months ago, # ^ |   +3 Take a look at Ticket 15743 from CF Stress for a counter example.
 » 3 months ago, # |   0 PROBLEM can someone plz explain why this code didnt work!! please
•  » » 3 months ago, # ^ |   +3 Take a look at Ticket 15750 from CF Stress for a counter example.
 » 3 months ago, # |   +1 Spoiler (Problem C)
 » 3 months ago, # | ← Rev. 4 →   0 Why is it TLE?164335406
 » 3 months ago, # |   +9 Funnily enough, in E, I never realised that we are just maintaing a binary number. The final algorithm you get is very similar to the editorial, albeit slower by a constant factor.Here's what I did, let $f_x$ be the frequency of $x$ on the blackboard. Let $g_x$ be the maximum possible frequency of $x$ after some operations. It's easy to see that $g_x = f_x + \lfloor g_{x - 1} / 2 \rfloor$. The answer is simply the largest $z$ such that $g_z$ is non-zero.Now, if we can somehow efficiently maintain $g$ after $f$ increases/decreases by $1$ we'd be done.Suppose we decrement $f_x$ by $1$. Consider what happens to $g$, let's call it $g'$ after the change. Obviously $g_y' = g_y$ for all $y < x$, and $g_x' = g_x - 1$. What about the following values? $g_{x + 1}' = f_{x + 1} + \lfloor g_x' / 2\rfloor = f_{x + 1} + \lfloor (g_x - 1) / 2\rfloor = \begin{cases} g_{x + 1} & g_x\text{ is odd}\\ g_{x + 1} - 1 & g_x\text{ is even} \end{cases}.$In the former case, we don't need to propagate the changes any further, in the latter case, it's as if we reduced $f_{x + 1}$ by 1 and the process repeats.In effect, we find the maximal interval $[x, r)$ such that $g_y$ is even for all $y \in [x, r)$ and then reduce $g_y$ by $1$ for all $y \in [x, r]$. Similar thing happens on incrementing $f_x$.We can maintain all this information using two lazy segment trees, one storing $g_x$ and $g_x \text{ mod } 2$ on the leaves, and their sum in the internal nodes. The first segtree supports range increment, and the second range flip operation.
•  » » 2 months ago, # ^ |   0 I did almost the same way but I store the range maximum, range bitwise AND, and range bitwise OR. I thought it was what everyone did because imo it is relatively easier to come up with.
 » 3 months ago, # |   +1 Can someone please recommend some problems similar to D?
•  » » 3 months ago, # ^ |   +6 this problem I think
 » 3 months ago, # | ← Rev. 2 →   0 problem C can anyone tell me why my solution is giving runtime error[submission:164331309][click here](https://codeforces.com/contest/1705/submission/164331309)
•  » » 3 months ago, # ^ |   0 From diagnostics: "Probably, the solution is executed with error 'division by zero' on the line 37".
•  » » » 3 months ago, # ^ |   0 thanks . I will try to fix out
•  » » » 6 weeks ago, # ^ |   0 Can you help me with my code too I don't know why it is giving TLE. My solution: https://codeforces.com/contest/1705/submission/169237458 Question: https://codeforces.com/problemset/problem/1705/C
 » 3 months ago, # |   0 Why is my solution for C throwing a memory limit exceeded error?I am iterating over the queries and splitting the queries with length > n as subcomponents and evaluating the final answer.I am essentially generating 40 * 40 * 1000 (q^2 * TC) query ranges for each test case which should still pass the given memory limit right?
 » 3 months ago, # | ← Rev. 2 →   0 I don't get how to convert E to those binary numbers ? I mean i get the part for the sum being constant. But what about the condition of first number in the streak of 1's appearing more than once?
 » 3 months ago, # |   0 can anybody explain the editorial by taking an example for problem c? im not understanding editorial
 » 3 months ago, # |   0 Does anybody have the same idea with me? it got a Memory Limit Exceeded 164356635
•  » » 3 months ago, # ^ |   0 I'm trying to enumerate the all indexes for lowercase charsm['a'~'z'][po1, po2, po3] when the query gives me a pos, I will search it and return the char. I think the pos array is too large
•  » » » 3 months ago, # ^ |   0 It doesn't change that much storing the position that each element of the final string is equivalent to in the original string (as you are doing) and just constructing the final string, because in both instances you are storing the equivalent of the final string's length in elements, which can be up to 10^5 * 2^40 (n duplicated c times) a.k.a: way too much.So your guess is correct, the position array is getting too big.
 » 3 months ago, # |   0 Thanks for the superfast editorial, interesting round with mark!
 » 3 months ago, # |   0 Can anyone please tell me what's wrong in my submission of C.164359468I wrote the code simple so that you understand.I just don't understand what's wrong in the idea.I used the index of the first element of each operation and distance of the indexes of asked element and first element of the operation.One glance to the code will be much appreciated :(
•  » » 3 months ago, # ^ |   0 Take a look at Ticket 15738 from CF Stress for a counter example.
•  » » » 3 months ago, # ^ | ← Rev. 4 →   0 Thank you so much bro!!!!! Being depressed I almost started a mission to get the 4992-th testcase using this:if(cas==4992) { cout<
•  » » » 3 months ago, # ^ |   0 Bro please add stress test for 1702 — E.It's been 6 days
•  » » » » 3 months ago, # ^ |   0 I don't add problems on demand. (Not on the free plan at least).
•  » » » » » 3 months ago, # ^ |   0 On what basis do you add problems?
•  » » » » » » 3 months ago, # ^ |   0 If I feel like it, or when someone pays me to. You can find the details on the pricing page.
»
3 months ago, # |
-14

For problem B, I started traversing the array from the second last element(n-1th for 1 Indexing). If the element is 0 and the previous element is a non-zero element, then that particular 0 will contribute in reducing the non-zero element. Thus, it will take two steps to reduce that 0 to 0 again(0 to 1 and again 1 to 0). So add 2 to the answer. If the element is non zero, then first decrement that element with the number of steps taken by the 0 element(if any) which was present next to it. Now, the dust remaining at that index is the actual dust which require individual steps to get reduced to zero. So add that number to answer.

Here is the code for the same.

# define ff(i,n) for(int i=0;i<n;i++)

using namespace std;

void solve(){

int tc; cin>>tc; while(tc--){ int n; cin>>n; vector vect(n,0); int i=0; ff(i,n){ cin>>vect[i];

}
int curr = 0;
int ans = 0;
for(int i=n-2;i>=0;i--){
if(vect[i]==0 && i>0 && vect[i-1]>=0){
ans+=2;
curr = 1;
}
if(vect[i]!=0){
vect[i]-=curr;
ans+=vect[i];
curr=0;
}
}

cout<<ans<<endl;

} }

int main() { solve(); return 0; }

This logic is somehow not working and I am unable to determine the failed test case. Can anyone please help.

•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Try this test: Input: 1 5 2 0 0 0 0 Output: 5 
•  » » » 3 months ago, # ^ |   0 Got it. Thanks.
 » 3 months ago, # |   0 One of the best CF rounds in a while!
 » 3 months ago, # |   0 C was kinda tricky.
 » 3 months ago, # |   0 I marked the topics I need to study
 » 3 months ago, # |   0 For B: what if you can't fill all the zeros. for example, the input : 2 0 0 0 3 0 0 0 0 0 6 . In this input, you can't make all the zeros into ones and apply the operation on i and j. You would end up with 1 1 0 0 1 1 1 0 0 0 6. But then you haven't filled all the zero entries have you? You would then have to move the 1s to the right?
•  » » 3 months ago, # ^ |   0 After you end up with 1 1 0 0 1 1 1 0 0 0 6, you can move 1->3, to do operation i->j, all elements from i to j-1 must be >=1, but the j-th element could be equal to 0 :)
 » 3 months ago, # |   +1 > be me > reading editorial > read "This is a well known fact" > sure bud
 » 3 months ago, # |   0 Thanks for the great contest!Here is my solution to E which used ChthollyTree, i.e., use set to maintain all the intervals.actually, we just need these operations and there are only two types of values: 0 and 1. : set interval find first a after b. because:operate +1 on position x: a[x] == 0: set a[x] to 1 a[x] == 1: find the first 0 after x, assume on pos y; then set a[y] to 1, set a[x..y] to 0. operate -1 on position x: a[x] == 1: set a[x] to 0 a[x] == 0: find the first 1 after x, assume on pos y (always exist); then set a[y] to 1, set a[x..y] to 1. So we can use set or map to maintain the 1 intervals.here is my code: https://codeforces.com/contest/1705/submission/164369724it is written by Rust, but the logic and comment are still suitable for all languages.
 » 3 months ago, # |   0 I wonder that why I fail to hack to this code.linkint a[110]; The size of the array is only $110$, but when $n = 100$, and there will be $200$ numbers, why it will not get WA / RE?Can anyone tell me, thanks a lot.
 » 3 months ago, # | ← Rev. 3 →   0 in problem D: I can't understand why the XOR is the key idea? I see how this applied on the 4th test case but Why not we lucky that this is the case with the 4th test case only?
•  » » 3 months ago, # ^ |   +1 In my opinion, after serveral operations, the number of the sum of $01$ and $10$ will not change.The problem says that $s_{i - 1} != s_{i + 1}$, for example, "100" will change to "110", and "001" will change to "011".We can find that the count of differences of the adjoining numbers will not change.In fact, XOR can find that if the adjoining numbers is not same, because $0 \ XOR\ 1 = 1$, $1 \ XOR \ 0 = 1$, $0 \ XOR \ 0 = 0$, $1 \ XOR \ 1 = 1$.I hope this solution can help you.
•  » » » 3 months ago, # ^ |   0 Thanks alot
 » 3 months ago, # | ← Rev. 2 →   0 For D, I understand how "cool" the solution looks like, but seriously, how can I even approach the XOR thing.
•  » » 3 months ago, # ^ |   0 Personally I don't think I would ever directly land in the xor thing. The human and logical approach to get to the solution and possibly to that xor realization would be to look for blocks/groups of elements that have some relation with each other or certain relevant behaviour, that's a common and effective idea that you can train yourself to pay attention to in some problems and can become better in finding/identifying.For example, one group you might find is that all the elements with odd positions can only change the elements with even positions and vice-versa. But a more important one in this problem are the groups of ones and zeroes for example, you might realize that you can expand and contract those as much as you want, from there you start to get somewhere.
 » 3 months ago, # | ← Rev. 6 →   -10 F can be solve in $n/{2.08}$ times. Here is another solution: blog (in Chinese).
 » 3 months ago, # |   +5 Video Solutions for Problem C and Problem D
 » 3 months ago, # |   +16 F is the same as thisand solution here 20210527
 » 3 months ago, # |   +8 Problem E can also be solveed by set. I store the segments of continuous 1. For examplpe, 10110111 may be stored as {1,11,111}. We also stored the segment's left bounder and right bounder, so when we need to check a position, we can use std::set::lower_bound to find a section that may include that position. Modifying the set is similar as the solution of segment tree, including splitting a section, and merge two sections, tottal complex is NlogN.
 » 3 months ago, # |   +3 Can somebody tell me how to think of D's solution? I think, it's just a little hard to think of. So is there anything lead to the soltuion? thx.
•  » » 3 months ago, # ^ |   +3 Bro, I used to be very afraid of this kind of problems. But realize that the main approach is observing and trying. I found the solutution by this way: 110->100 100->110 This transform told me nothing, so I tried to write some long strings, such as the strings in the sample cases: 000101-> 001101 -> 011101 -> 011001 -> 010001 ->010011. I read this transform from the node under the problem statements. It is really amazing that 000101 can turn to 011101. It means that 0001 can turn to 0111, further more, 0001000 can be turn to 0111110. That is, you can freely extend or shrink a continuous ones(1111...) or zores(000...), but you can't make a section disappear. This lead to a great conclusion: If string s1 start by 1 and end by 0, then s1 is like this: 1..0...1...0...1..0.. Realizing that you can extend or shrink a section(but you can't make any section disappear), so if s1 can be transformed to s2, then s2 must be this way: 1..0...1...0...1..0.. The number of sections is the same as s1.The problem has almost been solved! Please finish the remaining work.
•  » » » 3 months ago, # ^ |   +3 Oh yeah, i got it. It's just observing and trying to find the clues as you are calculating the samples. thx a lot, bro!
 » 3 months ago, # |   0 All good fellows. Congratulations on your success. Problem C was interesting and good, wasn't it, friends?
 » 3 months ago, # | ← Rev. 2 →   +6 I've decided to create my own editorial for the problems I solved(A-D) AJust sort the array and h[i] where 1<=i<= n will have to be matched with h[i+n]. So just check if it can be matched.164266799 BIf the first n-1 rooms are already clean, print 0. Else, find the first nonzero room i less than n, and store the positions of all the 0's in front of it that are less than n. Then all you have to do is make all the 0's 1's by performing the operation from the closest 0 to the farthest 0. If room i ever becomes 0, move on to the next nonzero room and repeat. Once all the 0's are gone, the answer is just the sum of all elements except element n.164278651 CFor each query, you're going back and "unconstructing" the operations. I created an array that stores the original lengths of each string after performing no operations, 1 operations, etc... Then you have to look for the first element in the array greater than or equal to k and reduce k using that. If k ever becomes less than or equal to the string's length, just print s[k-1]. This process can be done iteratively or recursively, though iteratively was slightly easier for me and is probably faster.164294136 DFirst of all s[0] = t[0] and s[n-1] = t[n-1] must be true if their is a solution, because those 2 elements can't be changed by the operation. Now let's define a group to be a list of consecutive 1's. The key observation is that a group can be increased or decreased to any size as long as it doesn't touch any other groups. So if there is to be a solution, the number of groups in s and t must be the same. Now in order to count the # of moves, we are going to match group i in s with group i in t for all groups i. The cost to move group i in s to t is the absolute value of the difference of their left-sides plus the absolute value of the difference of their right-sides. So just sum up this value for all the pairs of groups and you have your answer.164312198
•  » » 3 months ago, # ^ |   0 Our solutions are identical, but I find that my vocabulary is not enough when writing editorials.
•  » » 3 months ago, # ^ |   0 Hi, thank you so much for your take on the problems! If you don't mind could you explain the logic behind this line of your code in problem C:k = operations[i].second - (origlen[i] - k);
•  » » » 3 months ago, # ^ |   0 Since we're going back in time, right now we know that the index of the kth character must be between the left and right values of operation i. This is true because operation i was the first value we found >= k, so the above statement must be true. What "origlen[i] — k" does is that it gets the distance between the end of the string and the kth character. But since the end of the string is the rth character of the previous string, we can reduce k by going that same distance down from that right value instead.
•  » » » » 3 months ago, # ^ |   0 That makes it so much more clear, thank you!
 » 3 months ago, # |   +5 The editorial with hints is excellent :)
 » 3 months ago, # |   +16 https://codeforces.com/contest/1705/submission/164391480 another solution for E using SegmentTree
•  » » 3 months ago, # ^ |   0 @Omar_Mohammad please can you tell what we are storing at one node of segment tree, it would be very helpful.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 it's a segment tree sum i.e( each node holds the sum of its segment and each leaf node holds either 0 or 1) that sets a value to some range[l,r] with some modification on its implementation to get the first one, the first zero, and the last one in a given range
 » 3 months ago, # |   0 what's wrong with this submission for problem C. I'm using the same approach, but it is showing WA on test 2 ? link
 » 3 months ago, # |   -16 D is so beautiful that I used the second method and did'nt finish now!
 » 3 months ago, # |   -34 https://codeforces.com/contest/1705/submission/164346961Another Solution for E with BLOCK.It's $O(n\sqrt{n\log n})$, which have Successfully Passed the System Test!
 » 3 months ago, # |   +16 The complexity of using bitests to solve D is $O(n^2/w)$. But the maximum of n is $2*10^5$. I think this complexity can not pass the problem.
•  » » 3 months ago, # ^ |   0 Can anyone explain this?
•  » » » 3 months ago, # ^ |   0 I can give you answer that "bitsets are fast lol" but I think that is not very satisfying so I shall summon sslotin and hopefully he can give a better explanation ;)
•  » » » » 3 months ago, # ^ |   +21 Bitsets are fast lol.But seriously, if you are performing a simple bitwise operation, then, by the virtue of vectorization (processing a block of 256 bits per instruction) and instruction-level parallelism (capacity to execute two such instructions per cycle), $w=512$, or about $512 \times 3.60 \times 10^9 \approx 2 \cdot 10^{12}$ bitwise operations per second on CF server, which theoretically even lets you submit a $O(n^2)$ algorithm for $n=10^6$.
•  » » » » » 3 months ago, # ^ |   0 Thank you very much for your explanation.
 » 3 months ago, # |   0 The editorial of D is a bit obscure for what it is. A more natural way to interpret and make the key observation is to note that the number of "segments" of 1's, alongside the endpoints of the string, are invariant under operations. After checking this condition, simply notice that each operation moves a boundary of some segment by 1 unit (eg. 011000 -> 011100 is expanding the right boundary by 1), so repeatedly greedy matching the leftmost segments of both strings would give the answer if we take the absolute differences between their boundaries.
 » 3 months ago, # |   0 Is there a way that i can access the testcase on which i fail? when i click on my failed submission it shows first few cases of each test but if it is failing the 272nd testcase then can i know what it was?
•  » » 3 months ago, # ^ |   0 Actually there is no method to get the testcases.
•  » » » 3 months ago, # ^ |   0 thanks for the info, i think its good if i figure out the mistake on my own
 » 3 months ago, # |   0 C is nice problem
 » 3 months ago, # |   -8 Nice round.I would like to have problems descriptions in MORE LANGUAGES。
 » 3 months ago, # |   0 In problem D , why did we XOR like we did in solution? How to arrive at this conclusion of XORing , please help!
 » 3 months ago, # |   0 c was quite good ,it seems easy but it is not...
 » 3 months ago, # |   +16 F can be solved with "Entropy" (https://en.wikipedia.org/wiki/Entropy_(information_theory)) .You can split the positions into some groups , and each group includes at most B elements .You find the positions of 'F' of each group independently , and use Entropy to find the optimal choice . which can be solved in $O(2^{2B})$ for each group . Solution: 164420897 ,(B=12, and the number of queries is about 520 for n=1000).
•  » » 2 months ago, # ^ |   0 Awesome approach! I felt that the problem is about something more general, and it was entropy indeed.
•  » » » 2 months ago, # ^ |   0 Thanks :)
 » 3 months ago, # |   0 can somebody explain me the solution of problem C , i am unable to get it . Thanks You.1705C - Mark and His Unfinished Essay
 » 3 months ago, # |   0 Great Round!! But why my submission on B got TLE on test 5?Submission: https://codeforces.com/contest/1705/submission/164288648
 » 3 months ago, # |   0 F is a great problem, thank you!
 » 3 months ago, # |   0 I want to see solution O((clogc)q) or solution O(c*c*q) of problem C.
 » 3 months ago, # |   0 Can someone kindly explain C.Didn't understand the editorial.
 » 3 months ago, # |   0 Can anyone explain the Second Proof(Exchange Argument) of Problem A. I am watching https://www.youtube.com/watch?v=Oq1seKJvfQU and getting interested to know more about that technique to prove the Greedy idea.
 » 2 months ago, # | ← Rev. 2 →   0 Can someone tell me how did you get the idea for prioritizing 0's first that is filling those and then just summing up all the elements except the last for problem B?
 » 7 weeks ago, # |   0 I would like to suggest a different proof for problem A: Let's say we have already sorted those 2n numbers; if difference between nth number and first number isn't greater or equal to x then it won't be >= to x for any number with less index than n. therefore this number must be assigned to some number which index is higher than its index. but by pigenhole principle in bottom n there will be some number then who has to be assigned with number from bottom n, therefore their difference won't be greater or equal to x. P.S by bottom n I mean numbers with index from 1 to n.
 » 6 weeks ago, # |   0 what is the maximum size of string that we can store?
 » 5 weeks ago, # | ← Rev. 2 →   0 There is an alternate easier solution (without using xor operation ) for D where you can store indices where change is made in a queue. Then the current element at index i will be (s[i]-48+length)%2 where length is length of queue which stores no. of indices where changes from 0 to 1 can be made with element values >=i and https://codeforces.com/contest/1705/submission/170797410
»
17 hours ago, # |
0

# include<bits/stdc++.h>

using namespace std;

# define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main(){ // fast #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif long int t; cin>>t; while(t--){ long long n,c,q; cin>>n>>c>>q; string s; cin>>s; vector v; v.push_back(s.size()); unordered_map<long long,pair<long long ,long long>> m; long long int size=s.size(); long long int x,y; while(c--){ cin>>x>>y; m[size+y-x+1]={x,size+1}; size+=y-x+1; v.push_back(size); }

    while(q--){
cin>>x;
y=*lower_bound(v.begin(),v.end(),x);
while(y!=s.size()){
x=m[y].first+(x-m[y].second);
y=*lower_bound(v.begin(),v.end(),x);
}
cout<<s[x-1]<<"\n";

}

}
`

}