Блог пользователя Dsxv

A spin off problem from Educational Div2 91 — D
Автор Dsxv, история, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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]);
→ Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Care to share your approach?.

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

    Thanks!

    → Ответить
    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +3 Проголосовать: не нравится

      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]))$$$

      → Ответить
»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +3 Проголосовать: не нравится

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
→ Ответить
»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +6 Проголосовать: не нравится

      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.

      → Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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).

→ Ответить