DECOSUM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ritesh Gupta
Tester: Subhadeep Chandra
Editorialist: Ritesh Gupta

DIFFICULTY:

Simple-Easy

PREREQUISITES:

Ad-Hoc, Observation, Pre-Computation

PROBLEM:

You are given a sequence A_1, A_2, \ldots, A_N. You have to find the length of a minimum positive-sum subarray. If there is more than one answer then print the largest length possible or if no subarray satisfies the given property then print β€œ-1”.

Constraints:

  • 1 \le T \le 5
  • 1 \le N \le 10^5
  • 0 \le A_i \le 10^6 for each valid i

EXPLANATION:

If the sum of all the elements is zero then the answer would be β€œ-1” else answer always exists. As we need to find the minimum positive-sum possible so we should select the subarray which contains only one occurrence of the minimum positive element of the sequence and rest are zeros.

Let’s denote l_i for each valid i, as the size of zero-subarray which ends at index i and r_i for each valid i, as the size of zero-subarray which starts at index i.

Also assume that l_0 = r_n = 0.

If there are m occurences of smallest element of the sequence and represents by sequence k_1, k_2, ..., k_m such that A_{k_i} has smallest element then answer to the problem is:
maximum of l_{k_{i-1}} + r_{k_{i+1}} + 1 for each valid i.

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
int t;
cin >> t;

while(t--)
{
	int n;
	cin >> n;

	vector <int> v;
	int mx = 0;
	int mi = 1e9;

	for(int i=0;i<n;i++)
	{
		int x;
		cin >> x;

		mx = max(mx,x);

		if(x > 0)
			mi = min(mi,x);

		v.push_back(x);
	}

	if(mx == 0)
		cout << -1 << endl;
	else
	{
		int ans = 1;

		for(int i=0;i<n;i++)
		{
			if(v[i] == mi)
			{
				int cnt = 1;
				int j = i-1;

				while((j >= 0) && (v[j] == 0))
					cnt++, j--;

				j = i+1;

				while((j < n) && (v[j] == 0))
					cnt++, j++;

				ans = max(ans,cnt);
			}
		}

		cout << ans << endl;
	}
}

}

Tester's Solution

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll=long long;

int main()
{
int t,n;
cin>>t;

while(t--)
{
    cin>>n;
    vector<int> v(n);

    int z=0,lo=1e9+7;

    for(int i=0;i<n;i++)
    {
        cin>>v[i];

        if(v[i])
            lo=min(lo,v[i]);
        else
            z++;
    }

    if(z==n)
        cout<<-1<<endl;
    else if(!z)
        cout<<1<<endl;
    else
    {
        vector<int> pre(n),suf(n);

        if(!v[0])
            pre[0]++;

        for(int i=1;i<n;i++)
        {
            if(!v[i])
                pre[i]=pre[i-1]+1;
            else
                pre[i]=0;
        }

        if(!v[n-1])
            suf[n-1]++;

        for(int i=n-2;i>=0;i--)
        {
            if(!v[i])
                suf[i]=suf[i+1]+1;
            else
                pre[i]=0;
        }

        int ans=0;

        for(int i=0;i<n;i++)
        {
            if(v[i]==lo)
            {
                int tmp=0;
                if(i)
                    tmp+=pre[i-1];
                if(i!=n-1)
                    tmp+=suf[i+1];
                ans=max(ans,1+tmp);
            }
        }

        cout<<ans<<endl;
    }
}

}

1 Like

thanks this editorial is really helpfull :slight_smile: