PRGIFT - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

DIFFICULTY:

CakeWalk

PREREQUISITES:

None at all :slight_smile:

PROBLEM:

Given an array of integers a1,a2…an, check whether there is a subarray which consists of exactly k even integers.

EXPLANATION:

Since n<=50, you can traverse over all subarrays and count how many even numbers are there in each substring. Complexity: O(N3).

Or, we can do this cleverly. If there are atleast k even numbers in the whole array, we can always pick a subarray which will contain k even numbers.

One tricky case would be k=0, and all numbers are even in the array. In this case we can’t pick any subarray.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

1 Like
2

#include
using namespace std;
int main()
{
int t,n,k,a[1000],l,i,j,b;
cin>>t;
for(i=0;i<t;i++)
{
l=0;
cin>>n>>k;
for(j=0;j<n;j++)
cin>>a[j];
for(b=0;b<n;b++)
if(a[b]%2==0) l++;
if(l==k) cout<<“YES”<<endl;
else cout<<“NO”<<endl;
}
return 0;
}

3

If anyone can please tell me, which test case did I fail. It will be of great help. This is my solution:

http://www.codechef.com/viewsolution/4478036

1 Like
4

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct jg
{
int num;
int lx;
}t[100005];
int a[100005];
int main()
{
int time;
int n,k;
cin>>time;
while(time–)
{
cin>>n>>k;
int count=0;
bool flag=false;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]%2==0)
{
count++;
}
else
{
if(count>=k)
{
flag=true;
}
count=0;
}
}
if(count>=k)
{
flag=true;
}
if(flag)
{
cout<<“YES”<<endl;
}
else
{
cout<<“NO”<<endl;
}
}
return 0;
}

5

#include
using namespace std;
int main(){
int i,j=0,k,n;
cout<<“Enter max array size:”;
cin>>n;
int a[n];
cout<<“Enter array elements:”;
for(i=0;i<n;i++){
cin>>a[i];
if(a[i]%2==0)
j++;}
cout<<“Enter the exact no of even integers in substring:”;
cin>>k;
if(k>n||j<k||k==0)
cout<<“not possible substring of given length”;
else
cout<<“substring found”;
}

6

I am unable to understand why k= 0 is a special case here …When the requirement of the chef is zero then the case is definitely possible… CORRECT ME IF I AM WRONG

1 Like
7

This is my code what possible error is in this code.
thankyou!

#include<iostream>
#include<cstring>
#include<sstream>
#include<stdio.h>


using namespace std;

int main() 
{
int t, n, k, count = 0;
int num;
cin >> t;
while (t--)
{
	cin >> n;
	cin >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> num;
		if (num % 2 == 0)
		{
			count++;
		}
	}
	if (count == k && k!=0)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	count = 0;
}
return 0;

}

8

when k is 0 then you can select any subarray of length with no even numbers, but when all the elements in the array are even numbers then you cannot select any sub array. so this is the edge case.

9

One Tricky case is when your array contains all even numbers but chef wants 0 (k=0) so in this case there is no choice for chef as all are even so answer should be NO.