A spin off problem from Educational Div2 91 — D

Revision en3, by Dsxv, 2020-07-12 21:46:42

Hi!

While solving Div2 D, I came across another problem (not related to solving the actual problem though) :

Given a binary array A of size N, you are required to remove all the occurrence of 1 in the array only using the following step:

  • Select any subarray of size K ( K <= N ) and remove it from the array. After removing it, the adjacent parts (if any) will be joined as a single array.

Let's define Ans as the size remaining array after removing all the occurrence of 1 in A. Find the maximum value of Ans or say that it's impossible.

eg,

A : [1, 0, 0, 1, 0, 0, 1, 1] ,
K = 2
We have, Ans = 2 (In the end 3rd and 6th 0 's in the remaining array, Indexing from 1), multiple answers possible.

A simple greedy solution can be to select a window with a maximum frequency of 1s and remove it, continue doing this until all 1s are gone or say it's impossible. O(n^2), not sure of the correctness though :(

I'd like to hear your approach to this problem.

Thanks in advance!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Dsxv 2020-07-12 23:55:01 63 Tiny change: '**O(n^2)**, </strike> Edit: Wrong app' -> '**O(n^2)** </strike> **Edit:** Wrong app'
en3 English Dsxv 2020-07-12 21:46:42 38 Tiny change: '**O(n^2)** \n\nI'd li' -> '**O(n^2)**( not sure of the correctness :( )\n\nI'd li'
en2 English Dsxv 2020-07-12 21:38:12 259 Tiny change: 's problem with a be' -> 's problem possibly with a be' (published)
en1 English Dsxv 2020-07-12 21:12:20 901 Initial revision (saved to drafts)