Dsxv's blog

A spin off problem from Educational Div2 91 — D
By Dsxv, history, 4 years ago, In English

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) Edit: Wrong approach sorry :p

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

Thanks in advance!

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

More TestCases ? :/

      int k;
      string s;
      cin >> s >> k;
      n = sz(s);
      vi dp(n+1,inf);
      dp[n] = 0;
      for( int i = n-1; i >= 0; i--) {
            if(s[i] == '1') {
                  if ( i + k <= n ) {
                        dp[i] = 1 + dp[i+k];
                  }
            } else {
                  dp[i] = dp[i+1];
                  if( i + k <= n ) 
                      dp[i] = min(dp[i+1],1+dp[i+k]);
            }
      }
      cout <<  ( dp[0] >= inf ? -1 : sz(s) - k*dp[0]);
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Care to share your approach?.

    Here's a test case: 1101 and k = 2, ans should be 0.

    Thanks!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks for the test_case;

      I added another condition and it seems to be correct now.

      I'm basically trying to minimize the number of segments cut, so initially $$$dp$$$ is initialized to $$$\infty$$$ and $$$dp[n] = 0$$$ Since it would require $$$0$$$ operations to correct a $$$0$$$ length array.

      So the for the transitions, at a current position you can delete it or leave it. If at the current index it's a 0 we have the choice to skip it as $$$dp[i] = dp[i+1]$$$ but in the other case we have to delete it ( if possible ) and hence $$$ dp[i] = min(dp[i],1+dp[i+k]))$$$

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

I am not sure if it is the right or wrong approach.

If you found 1 in the array then remove the subarray of length k starting from that point.

Spoiler
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep greedy works

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try This. 0101101001

    4

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what's wrong with this case? Ans should be 2 right?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It seems to be giving 0 on this one, ( Yes the answer is 2 ).

        Maybe Someone Can Cross-Check.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My code gives answer 2.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi! I also thought of the greedy but was not able to prove it. ( Greedy's are really hard to prove :p). Can anyone share some intuition around the proof?

    Thanks!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Find ind such that p[ind] = 1 and p[0...ind-1] = 0, now you should realize that we have to delete this element at some point, so if we will delete some segment p[l...r], l <= ind <= r we can notice that if we will delete p[l+1...r+1], l+1 <= ind <= r+1 <= n instead the answer will not get worse.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The Naive Brute You Wrote could be incorrect in some cases where you have same frequency of in a given range,

For example here,

0101101001

4

Deleting at index 1 gives the correct answer but deleting at 3 first would give you -1.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! It was just to apply the principles. I was never able to prove it anyway :p

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      This greedy is not so hard to prove. Every time we encounter a 1 we necessarily have to chose a subarray including this element. Since we're certain that all elements before it are 0, it can be said that the most optimal solution includes the subarray starting with this 1 if we're allowed to ie: i+k<=n since it leaves the maximum 0s, otherwise choosing the last k elements if possible deletes all possible 1s that we might encounter whilst 'wasting' minimal 0s.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Ah Silly me! it does make sense to think it that way.

        Thanks a lot!

        → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I got a solution I think. Let's think like this way.
Let the leftmost index of 1 be idx. There is no point of starting an operation from an index less than idx if we can do an operation from idx. This is the greed.
Now, save all the indexes of 1. Start with the leftmost index, Do the operation and go gradually.
Let we have an array
A = [0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1] and k = 3
We would start operation from 3. We covered 3 and 4. Then, start operation from 7. We covered 7 and 9. Now, current array length is 6. Then start from 12. Now, we can't start from 12. But, we have an array of length 6. So, we can easily cut the last segment and get the array of length 3 having the indice of [1, 2, 6].
How to implement it? Simple. Binary_search.
Complexity O(n log n).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, It does explain the process! though I think the approach is the same as that proposed by Harshil_.

    Thanks!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Why not propose problems in some contest instead of exposing. It would be better anyway. It's a perfect pick for Medium/Hard D.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Spin-off problems usually come to my mind and most of the time, I just solve it by discussing it with my friends. I am thinking of problem-setting after reaching CandidateMaster ( consider it as my dumb milestone maybe? :p)

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can start it by now. Experts can set problems according to CF rules. And you are pretty close to CM. So, you are gonna reach it quickly unless you fall down to far anyway.

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Why binary search? Just go from left to right and remove whenever you see a 1.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In this example. Let v stores the index of 1. so v = [3, 4, 7, 9, 12]
      If we start from left to right. Then, when we are in 3, we are already killing 4. When we are in 7, we are already killing 9. So, we have to always go to next unkilled element. Only way that I know is lower_bound.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you kill at current index, you know everything up to current+k is killed. Just jump there or maintain a second variable 'ignoreUntil', and check this one before the next kill.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Whaaat?? Ahh, I am fool. Why didn't it strike? Thanks man. Got it.

          → Reply