PROBLEM LINK:
Practice
Contest
Author: Praveen Dhinwa
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu
DIFFICULTY:
CakeWalk
PREREQUISITES:
None at all 
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
#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;
}
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
3 Likes
#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;
}
#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”;
}
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
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;
}
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.
1 Like
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.
1 Like
Can someone say whats the problem?
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t–>0) {
String s[] = br.readLine().trim().split(" “);
int n = Integer.parseInt(s[0]);
int k = Integer.parseInt(s[1]);
int num =0;
int a =0;
s = br.readLine().trim().split(” ");
if(k==0) {
System.out.println(“YES”);
continue;
}
for(int i=0; i<n; i++) {
num = Integer.parseInt(s[i]);
if(num%2==0) {
a++;
if(a==k) {
System.out.println(“YES”);
break;
}
}
}
if(a!=k)
System.out.println(“NO”);
}
}
}
suppose that k=0 and all elements of array are even. Then we cannot select a subarray which has 0 even numbers i.e there is no even number in it.
1 Like
suppose that k=0 and all elements of array are even. Then we cannot select a subarray which has 0 even numbers i.e there is no even number in it. i hope it helps
1 Like
your solution is correct bro. author solution is wrong
for input:
1
6 3
1 3 2 4 7 6
from author solution output is yes. but its correct output should be no. since we have been asked choose a consecutive non-empty segment of the array which in this case is [2,4].correct me if i am wrong
3 Likes
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
int main(){
std::ios::sync_with_stdio(false);cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n, k;
cin >> n >> k;
int x[n];
int counter = 0;
for(int i = 0; i < n; i++) {
cin >> x[i];
if(x[i] % 2 == 0) {
counter++;
}
}
if(k == 0 && counter == n) {
cout << "NO" << endl;
} else if(counter < k) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
}
}
}
1 Like
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=0;
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d %d",&n,&k);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
int count=0;
bool flag =false;
if(k==0)
{
for(int i=0;i<n;i++)
{
if(arr[i]%2!=0)
flag=true;
}
if(flag)
cout<<"YES\n";
else
cout<<"NO\n";
return 0;
}
for(int i=0;i<n;i++)
{
if(arr[i]==0)
{
count=0;
continue;
}
if(arr[i]%2==0)
count++;
if(count==k)
{
flag=true;
break;
}
}
if(flag)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
Can someone please tell me what is wrong with this code
1 Like
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
vector temp;
for(int i=0;i<n;i++)
{
int count =0;
for(int j=i;j<n;j++)
{
if(a[j]%2==0)
{
count++;
}
else{
break;
}
}
temp.push_back(count);
}
sort(temp.begin(), temp.end(), greater());
if(temp[0]>=k)
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
Can anyone please tell me what’s wrong with this code
consider this
when n=4, k=2, array = {2,3,4,9}
them we can choose a subarray {2,3,4} which has exactly 2 even no in it
but according to your code
all the even no in array should always be consecutive(one after one)
so your code may not satisfy the above test case
suppose take input
3 //t : no of test case
4 0 //1st test
2 4 6 9
3 2 //2nd test case
8 9 2
In 1st test case k=0 ,
if(k==0) condition in your pgm will be satisfied
and it will return 0 ;(as you have typed inside the if loop just at the end) finally
BUT KEEP IN MIND THAT ONCE RETURN is encountered in main() pgm the whole program gets terminated just after the 1st test case in the above eg
and program will not proceed further for 2nd test case.
actually your subarray can have odd integers as well
Its not that all even integers must be consecutively(one after one) present in the subarray
in the above eg we can form a subarray with exactly 3 even integers
it can {1,3,2,4,7,6} or {2,4,7,6}
it does not matter whether odd integers are there in the subarray or not but the subarrat must have exactly k even integers anywhere inside it