PROBLEM LINK:
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;
}
}
}