### MarkBcc168's blog

By MarkBcc168, history, 2 years 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

| Write comment?
 » 2 years ago, # |   0 Auto comment: topic has been updated by MarkBcc168 (previous revision, new revision, compare).
 » 2 years ago, # |   0 Can you continue in the sun time next time?
 » 2 years ago, # |   +14 So fast Editorial...Love it.
•  » » 2 years ago, # ^ |   +11 The editorial with hints is excellent :)
 » 2 years ago, # | ← Rev. 2 →   +23 C was nice
 » 2 years ago, # |   +25 A and B were normal. C was kinda nice. D felt kind of easier than normal.
 » 2 years ago, # |   -12 why my solution is giving memory limit 164324383
•  » » 2 years 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.
•  » » 2 years 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
 » 2 years ago, # |   0 For C: https://codeforces.com/contest/1705/submission/164336489 why this code give TLE. and how to remove TLE? please tell
•  » » 2 years 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.
 » 2 years ago, # | ← Rev. 3 →   +8 Good Tasks for Codeforces Round #807) Editorial is perfect.
 » 2 years ago, # |   +5 So fast Editorial！！！！！
•  » » 2 years ago, # ^ |   +4 you are 607 mouse ?
•  » » 2 years ago, # ^ |   +4 you are 607 mouse ?
 » 2 years ago, # |   +12 Problem C was just awesome <3
 » 2 years ago, # |   +14 Thanks for the superfast editorial, interesting round with mArK!
 » 2 years 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.
 » 2 years ago, # |   +2 Hints are always helpful.
 » 2 years ago, # |   +12 Wow, very fast editorial! I like this contest because the problems are easy to understand. Great job!
 » 2 years ago, # |   +9 I thik C is very nice
 » 2 years ago, # |   +1 So fast Editorial！！
 » 2 years ago, # |   +9 Question D is so difficult
 » 2 years ago, # |   +5 Amazing tutorial! It made me everything easy to understand.
 » 2 years 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?
•  » » 2 years 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
•  » » » 2 years ago, # ^ |   0 It is actually very easy, sir.
 » 2 years 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¯ ?
•  » » 2 years ago, # ^ |   0 Great catch! Fixed.
•  » » » 2 years 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 years 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!
 » 2 years ago, # |   0 which topic i should learn for solving problems as C?
•  » » 2 years ago, # ^ |   0 There is no specific knowledge required to solve C. You can try reading the hints and tutorial provided above.
•  » » » 2 years 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
•  » » » » 2 years ago, # ^ |   0 the best way to improve at problems like div2C is through problem solving and gaining experience
•  » » » » 2 years ago, # ^ |   0 Practice more div2Cs would be OK.Try to solve them as quickly as you can.
•  » » 2 years ago, # ^ |   0 C is just about implementation
•  » » 2 years ago, # ^ |   0 I though the observation that for each query you have to travel back through the (c<=40) operations was the hardest part.
 » 2 years ago, # | ← Rev. 2 →   0 It was super hard for me. I should do more practice
 » 2 years 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
•  » » 2 years ago, # ^ |   +5
•  » » » 2 years 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
 » 2 years 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)?
•  » » 2 years ago, # ^ |   +3 Same bro :(
•  » » 2 years 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.
•  » » » 2 years ago, # ^ |   +3 this was my sol as well.
•  » » 2 years ago, # ^ |   0 Same
•  » » 2 years 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.
•  » » 2 years ago, # ^ |   +5 I think the invariant that the number of chunks of 1 stays the same is easier to be observed.
•  » » 2 years 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
•  » » 2 years 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.
•  » » 2 years ago, # ^ |   0 This could be helpful: https://codeforces.com/blog/entry/85172 (there is one problem with an invariant)
 » 2 years ago, # |   0 So fast editorial and fantastic contest!
 » 2 years ago, # |   0 C was kinda hard for me, but I really enjoyed solving it. Great problem
 » 2 years ago, # |   0 Thanks for the fast tutorial ...
 » 2 years ago, # |   0 Enjoyed this contest — definitely has a good math olympiad flavor to it (both problems and solutions)!
 » 2 years ago, # |   +9 Does qn D answer overflow int ? passed three pretests then failed.
•  » » 2 years 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.
•  » » » 2 years 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.
 » 2 years ago, # |   +8 C was bit tricky for me, Good problemset overall. Happy Coding & Happy friday :)
 » 2 years 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.
 » 2 years ago, # |   -8 Thanks for fast tutorial and E was cool.
 » 2 years ago, # |   0 Does somebody have binary search solution for C?
•  » » 2 years ago, # ^ |   0 Not needed
•  » » 2 years ago, # ^ |   0 See my submission: https://codeforces.com/contest/1705/submission/164314488
 » 2 years 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
•  » » 2 years 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.
•  » » » 2 years ago, # ^ |   0 Thanks a lot, that would explain what happened.
•  » » 2 years ago, # ^ |   +11 [unrelated] why are you removing the legendary line :( #define ick cout<<"ickbmi32.9\n" 
 » 2 years 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?
•  » » 2 years 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.
•  » » 2 years 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.
•  » » » 2 years ago, # ^ |   0 I disagree, the $O(nlog^{2}n)$ solution was more obvious to me. I couldn't come up with that observation.
•  » » 2 years ago, # ^ |   +1 Can you share your Approach towards problem D?
 » 2 years 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?
•  » » 2 years ago, # ^ |   +3 This was written when there was the second operation (of deleting numbers). The editorial is updated now. Hope this eliminates your confusion.
 » 2 years 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.
•  » » 2 years 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)
•  » » » 2 years 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".
 » 2 years 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.
 » 2 years ago, # |   0 Auto comment: topic has been updated by MarkBcc168 (previous revision, new revision, compare).
 » 2 years 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 :(
 » 2 years 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)
•  » » 2 years ago, # ^ |   0 Coz of integer overflow. You need to use long long. Made the same mistake :")
 » 2 years ago, # |   0 Nice contest! Thanks for the fast editorial! :)
 » 2 years 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
•  » » 2 years ago, # ^ |   +3 Take a look at Ticket 15743 from CF Stress for a counter example.
 » 2 years ago, # |   0 PROBLEM can someone plz explain why this code didnt work!! please
•  » » 2 years ago, # ^ |   +3 Take a look at Ticket 15750 from CF Stress for a counter example.
 » 2 years ago, # |   +1 Spoiler (Problem C)
 » 2 years ago, # | ← Rev. 4 →   0 Why is it TLE?164335406
 » 2 years 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 years ago, # |   +1 Can someone please recommend some problems similar to D?
•  » » 2 years ago, # ^ |   +6 this problem I think
 » 2 years 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)
•  » » 2 years ago, # ^ |   0 From diagnostics: "Probably, the solution is executed with error 'division by zero' on the line 37".
 » 2 years 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?
 » 2 years 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?
 » 2 years ago, # |   0 Does anybody have the same idea with me? it got a Memory Limit Exceeded 164356635
•  » » 2 years 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
•  » » » 2 years 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.
 » 2 years ago, # |   0 Thanks for the superfast editorial, interesting round with mark!
»
2 years 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.

•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Try this test: Input: 1 5 2 0 0 0 0 Output: 5 
 » 2 years ago, # |   0 One of the best CF rounds in a while!
 » 2 years 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?
•  » » 2 years 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 :)
 » 2 years ago, # |   +1 > be me > reading editorial > read "This is a well known fact" > sure bud
 » 2 years 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.
 » 2 years 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?
•  » » 2 years 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.
 » 2 years ago, # | ← Rev. 2 →   0 For D, I understand how "cool" the solution looks like, but seriously, how can I even approach the XOR thing.
•  » » 2 years 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.
 » 2 years ago, # | ← Rev. 6 →   -10 F can be solve in $n/{2.08}$ times. Here is another solution: blog (in Chinese).
 » 2 years ago, # |   +5 Video Solutions for Problem C and Problem D
 » 2 years ago, # |   +16 F is the same as thisand solution here 20210527
 » 2 years 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.
 » 2 years 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.
•  » » 2 years 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.
•  » » » 2 years 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!
 » 2 years 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
•  » » 2 years ago, # ^ |   0 Our solutions are identical, but I find that my vocabulary is not enough when writing editorials.
•  » » 2 years 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);
•  » » » 2 years 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.
 » 2 years ago, # |   +5 The editorial with hints is excellent :)
 » 2 years ago, # |   +16 https://codeforces.com/contest/1705/submission/164391480 another solution for E using SegmentTree
•  » » 2 years ago, # ^ |   0 @Omar_Mohammad please can you tell what we are storing at one node of segment tree, it would be very helpful.
•  » » » 2 years 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
 » 2 years 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!
 » 2 years 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.
•  » » 2 years ago, # ^ |   0 Can anyone explain this?
•  » » » 2 years 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 ;)
•  » » » » 2 years 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$.
•  » » » » » 2 years ago, # ^ |   0 Thank you very much for your explanation.
 » 2 years 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.
 » 2 years 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?
•  » » 2 years ago, # ^ |   0 Actually there is no method to get the testcases.
 » 2 years 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 years ago, # ^ |   0 Awesome approach! I felt that the problem is about something more general, and it was entropy indeed.
•  » » » 2 years ago, # ^ |   0 Thanks :)
 » 2 years ago, # |   0 Great Round!! But why my submission on B got TLE on test 5?Submission: https://codeforces.com/contest/1705/submission/164288648
 » 2 years ago, # |   0 F is a great problem, thank you!
 » 23 months 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