CHEFZOT - Editorial

[dpraveen]

PROBLEM LINK:

Practice
Contest

Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

Cakewalk

PREREQUISITES:

processing of arrays

PROBLEM:

Given an array A. Find maximum length of sub-array with product of its elements being non zero.

EXPLANATION

• Product of a sub-array will be zero if and only if it contains at least one zero element.
  So we have to find out maximum size of the sub-array not containing zero.

• So we can start processing the array from left to right and keep track of last position where we had found the zero element, at each step
  we will compute the maximum size of the sub-array ending at the current position and not having any zeros in it (For i ^th element, the size of the sub-array will
  be i - lastZeroIndex where lastZeroIndex is the index of the last zero found).

• Finally we will take the maximum of all those values for each index i from 1 to N.

Please see the simple pseudo code.

lastZeroIndex = 0, ans = 0
for i = 1 to N:
	if a[i] == 0:
		lastZeroIndex = i
	cur = i - lastZeroIndex
	ans = max(ans, cur)

Complexity:
O(N), You just need a single pass of the array a.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution

[rkm123]

now where i can submit my solution .

[achaitanyasai]

You can use this link :

Chef and Subarray | CodeChef

or just click (practise) of the PROBLEM LINK at the start of this question

[yashtodi94]

#include
#define max 100000
using namespace std;

int main()
{

	unsigned long long int N, a[max], i, j = 1;
	unsigned long long int maxim = 0, maxfin = 0;

	cin >> N;
	for(i = 0; i < N; i++)
		cin >> a[i];
		
	for(i = 0; i < N && j < N;)
	{
		
		if(a[i] != 0)
			maxim++;

		while(a[i]*a[j] != 0)
		{
			j++;
			maxim++;
		}
		
		i = j + 1;
		j = i + 1;
		
		if(maxim > maxfin)
			maxfin = maxim;

		maxim = 0;
	}
	
	cout << maxfin;
}

Although this approach is different from the one in the editorial....i always got wrong answer...please help?

[kellymilla18]

your solution is wrong for some inputs where N = 1… since j is always starting at 1…
it will not enter the for loop and the maxfin will remain equals to 0… the answer for all N = 1 is 1 if a[0] != 0…

[drj_reddy]

import sys
t = input()
a = map(int,raw_input().split())
count = 0
mx = 0
for i in a:
if i==0:

        if count>mx:
            mx = count
        count=0
    else:
        count+=1
if count>mx:
    mx = count
print mx
sys.exit()

[yashtodi94]

oh damn…i neva thought about this and always thought my code was unable to handle large data…thanx a ton

[sanzzzay]

i think u have to use #define in place of define

[yashtodi94]

@sanzzzay

I couldn’t post the code with ‘#’ here…rest assured there arent any compilation errors…kellymilla18 solved the prob

thanx anyway

[sanzzzay]

ohh sorry i was just trying to be smarter i guess

[yashtodi94]

#include
#define max 100000
using namespace std;

int main()
{

unsigned long long int N, a[max], i, j = 1;
unsigned long long int maxim = 0, maxfin = 0;

cin >> N;
for(i = 0; i < N; i++)
	cin >> a[i];

if(N == 1)
{
	if(a[0] == 0)
		maxfin = 0;
	else
		if(a[0] != 0)
			maxfin = 1;
}
else
{
for(i = 0; i < N && j <= N;)
{
	
	if(a[i] != 0)
		maxim++;

	while(a[i]*a[j] != 0)
	{
		j++;
		maxim++;
	}
	
	i = j + 1;
	j = i + 1;
	
	if(maxim > maxfin)
		maxfin = maxim;

	maxim = 0;
}

}

cout << maxfin;

}

@kellymilla18

this approach too gives a wrong answer…i dont think that was the prob indeed

[yashtodi94]

hehe…anyway…the prob still persists n i m not able to find logical errors

[kellymilla18]

try this… N = 5, 1 0 0 1 1… output should be 2… http://www.codechef.com/viewsolution/4110862

[bug2312]

Well this solution can be optimized more in terms of space requirement by not taking the array. Instead take an element one by one and increment the count. If the input turns out to be zero then set count equal to zero
The code can be

int ans=0,c=0,i;
for(i=0;i<n;i++){
scanf("%d",&x)
if(x>0)
c++;
else
c=0;
if(c>ans)
 ans=c;
}

[mappy]

Hey all ! Can anyone tell whats wrong with this code.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

class ChefZot {
int size=0,N=0,count1=0, count2=0;
int arr[]=new int[10000];

 public void solve() throws Exception{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out=new PrintWriter(System.out);
    StringTokenizer st;
    N=Integer.parseInt(br.readLine());
    st=new StringTokenizer(br.readLine());
           for(int i=0;i<N;i++)
               arr[i]=Integer.parseInt(st.nextToken());
           size=N;            

           for(int j=0;j<N;j++)
              {
             if(arr[j]!=0)
              count1++;
             else if(arr[j]==0)
                {
                 if(count1>=size/2)
                   { 
                    System.out.println(count1);
                    System.exit(0);
                   }
                 else if(count1<size/2)
                   {
                   if(count1>count2)
                   count2=count1;
                    count1=0;
                   continue;
                   }
        }
    
      if(j==N-1)
      {
          if(count1>count2)
          count2=count1;
      }           
   }
         System.out.println(count2);
         br.close();
    }
 public static void main(String[] args)
     {
          ChefZot c=new ChefZot();
           try{ 
             c.solve();
              }
            catch(Exception e){
               System.exit(0);
                   }
    
     }

}

[prawat]

please tell me what’s wrong with this code?? It’s showing correct outputs but still there’s a ‘Wrong Answer’ to my solution…

#include
using namespace std;

int main()
{
int n,i,*a,*b,maxi,ct=0;
cin>>n;
a=new int[n];
b=new int[n];
for(i=0;i<n;i++)
{
cin>>a[i];
if(a[i]==0)
{
b[ct]=i;
ct++;
}
}
maxi=b[0];
for(i=1;i<ct;i++)
{
if(maxi<(b[i]-b[i-1]-1))
maxi=b[i]-b[i-1]-1;
}
if(maxi<n-b[ct-1]-1)
maxi=n-b[ct-1]-1;

cout<<maxi;
return 0;
}

[manish88singh]

how/where to get java solution for June2014 problems???

[shiplu]

Please post the link of your submitted code.

[prateek181996]

int main()
{
long int n,maxLength=1,currentLength=0,x=0;
cin>>n;
long int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]==0)
x++;
}

if(x==n)
    cout<<"0\n";
else
{
    for(int i=0;i<n;i++)
    {
        if(a[i]>0)
        {
            currentLength++;
        }

        else
        {
            currentLength=0;
        }

        if(currentLength>maxLength)
        {
            maxLength=currentLength;
        }
    }
    cout<<maxLength<<"\n";
}

return 0;

}

[aman1112]

def fun(a,n):
    l=0
    ans=0
    for i in range(1,n):
        if(a[i]==0):
            l=i
        cur=i-l
        ans=max(ans,cur)
    print(ans)
n=int(input())
a=list(map(int,input().split()))
fun(a,n)

This is always giving wrong answer ,how it can be improved ?