infj1's blog

Can someone help me with this problem?
By infj1, history, 12 months ago, In English

Given an array of length n containing only zeros and ones, you can perform operations by removing either the first or the last element of the array. Calculate the minimum number of operations required to achieve a total sum of s in the array. If it is not possible to obtain the sum s after any number of operations, the output should be -1.

The code below is my approach. But when I submit its giving wrong answer. Could you guys what's the problem with the code? Or the approach?

for _ in range(int(input())):

n,s=[int(i) for i in input().split()]

a=[int(i) for i in input().split()]

c=0

for i in range(n):


    if a[i]==1:
        c+=1


if c<s:
    print(-1)
else:
    l=0
    r=n-1
    req=c-s
    got=0
    ans=0
    if got==req:
        print(0)
        continue
    while l<r and got<req:
        old_l=l
        while l<r and a[l]==0:
            l+=1
        old_r=r
        while r>l and a[r]==0:
            r-=1
        l_dis=l-old_l
        r_dis=old_r-r
        if l_dis<r_dis:
            r=old_r
            ans+=l_dis+1
            l+=1
        else:
            l=old_l
            ans+=r_dis+1
            r-=1
        got+=1
    print(ans)
  • Vote: I like it
  • -4
  • Vote: I do not like it

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

Auto comment: topic has been updated by infj1 (previous revision, new revision, compare).

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

There can only be 3 cases if you can get sum:

1. You obtain sum via some prefix in the array lets say [1, L]

2. You obtain sum via some suffix in the array lets say [R, N]

3. You obtain sum via some prefix + suffix lets say [1, Li] + [Ri, N]

Enumerate all cases using prefix and suffix sums (suffix sum not required) and ans is just sum of above ranges.

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

    I mean min of sum of all possible ranges*

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

Essentialy, your task is to find a pair $$$(l, r) : \sum\limits_{i=l}^{r} a[i] = s$$$, which maximizes $$$r - l$$$. The problem of finding the largest subsegment with $$$sum <= k$$$ can be solved with two pointers technique (if you're not familiar with it, the EDU section might be helpful).

→ Reply