Amit9's blog

Binary Deque
By Amit9, 3 months ago, In English

Submission : (https://codeforces.net/contest/1692/submission/275124032)
Problem : (https://codeforces.net/contest/1692/problem/E)

Why this approach fails, can anyone give some counter test case?

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Consider array 0 1 1 0 1 1 0, target sum is 1. Clearly it can't be done in less than 5 operations, because you must remove at least two 0s to be able to remove at least three 1s. But your approach would remove both outer zeros and set zero to 1, then remove 3 more 1s, leading to a total cost of 4. It doesn't take into account that both outer 0s had to be removed.

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

    Thank you, i haven't noticed it.

    → Reply
»
3 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it 
10 2
0 1 0 0 1 1 0 0 1 0

The correct answer is 4 your algorithm returns 3.

The reason it fails in this case is that it performs the correct steps but only counts removing zeros from both ends as 1 operation. (the last else statement in your loop)

If you correct it your approach will still be incorrect as in the case: 

10 2
0 0 0 1 1 1 1 0 0 0

After the fix your algorithm will return 8, instead of the correct 5 (it remove the first 5 numbers)

As far as I know there is no greedy solution to the problem.

This problem is equivalent to finding a subarray of maximum size with a sum equal to K (the numbers you leave). This can be solved with a sliding window.

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

    Thank you.
    Yeah, i later tried sliding window and it worked, i was just curious whether it can be done with two pointers alone but it doesn't seem to work. thank you once again.

    → Reply