atlasworld's blog

By atlasworld, history, 3 years ago,

How to solve problem D of abc124. The editorial is in japanese. Can anyone who solved it, share logic!

i m thinking on using 2 pointer.

• +4

 » 3 years ago, # | ← Rev. 2 →   0 i think 2 pointer technique can work, move our right pointer till we utilised all k, and then move left pointer to the right until k become > 0 , then again move the right point till k gets exause,make continuous movements of both the pointers and each time keep track of max answer ? is this approach correct ?
•  » » 3 years ago, # ^ |   0 Any other approaches, as i think 2 pointer technique would be quite hard to implement.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Not hard. Check my submission. Whenever you encounter a '0', and it starts a new segment of '0's, you increment the number of 0 segments by 1. And, similarly, when move beyond the last '0' of a segment of '0's, you decrement the number of segments by 1. You just maintain the number of segments of '0's to ≤ k.
•  » » » » 3 years ago, # ^ |   0 Thanks Prakhar, i looked at ur solution, its very clear and easy to implement, than what i thought !
 » 3 years ago, # |   0 It was a good implementation question. I stored all the segments of consecutive 0's in an vector and after doing this iteratively pick consecutive k segments of 0's and make them 1 and then check the answer . this is a greedy approach for this. Link to my submission https://atcoder.jp/contests/abc124/submissions/4954185 Hope it helps
•  » » 3 years ago, # ^ |   0 Thanks, but as u said "iteratively pick consecutive k segments of 0's and make them 1 and then check the answer " , but on what basis u pick them , did u just pick first k segments of 0's ?
•  » » » 3 years ago, # ^ |   0 Suppose you got 10 segments of 0's and k=3. Now pick segment {1,2,3} first then {2,3,4} then {3,4,5} and so on and calculate the maximum length subsegment of 1's. This is the optimal way to do it.
•  » » » » 3 years ago, # ^ |   0 wow , clever approach .
 » 3 years ago, # | ← Rev. 3 →   0 Hi, I solved this question with $2$-pointer sliding window technique. I created two arrays $Z$ and $O$, where $Z[i]$ denotes the length of the $i$-th segment of $0$s and $O[i]$ denotes the length of the $i$-th segment of $1$s. Suppose I am flipping $Z[L], Z[L + 1], \dots , Z[R]$ What is the resulting length of the segment of $1$s ? If we are flipping $K$ $0$-segments, then we must add the $(K - 1)$ $1$-segments in between and the $2$ $1$-segments at each end. (Totally $(K + 1)$ $1$-segments.)The number of $1$ s is either $(O[L - 1] + Z[L] + O[L] + \dots + O[R] + Z[R])$ or $(Z[L] + O[L] + \dots + O[R] + Z[R] + O[R + 1])$ depending on whether the first segment is a $1$-segment or a $0$-segment. I checked every set of $K$ consecutive $0$ segments and the one that maximises the number of $1$'s is the answer. Here is my explanation and code. I have added a lot more details here.
•  » » 3 years ago, # ^ |   0 Thanks !
 » 2 years ago, # |   +2 See my solution in case you need help https://atcoder.jp/contests/abc124/submissions/15330027