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.

# | User | Rating |
---|---|---|

1 | tourist | 3645 |

2 | Radewoosh | 3403 |

3 | Um_nik | 3348 |

4 | LHiC | 3336 |

5 | Benq | 3316 |

6 | V--o_o--V | 3275 |

7 | mnbvmar | 3241 |

8 | yutaka1999 | 3190 |

9 | ainta | 3180 |

10 | Petr | 3106 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 192 |

2 | Radewoosh | 177 |

3 | rng_58 | 164 |

4 | PikMike | 163 |

5 | Vovuh | 160 |

6 | majk | 158 |

7 | 300iq | 154 |

7 | antontrygubO_o | 154 |

9 | Um_nik | 151 |

10 | kostka | 149 |

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.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/22/2019 19:58:21 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 ?

Any other approaches, as i think 2 pointer technique would be quite hard to implement.

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.

Thanks Prakhar, i looked at ur solution, its very clear and easy to implement, than what i thought !

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

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 ?

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.

wow , clever approach .

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.

Here is my explanation and code. I have added a lot more details here.

Thanks !