August Challenge 2014: PRGIFT Can anyone tell me why my code is giving wrong answer?

I just counted the number of even numbers in the array. And if they are greater than or equal to k then it is possible for him to choose a segment otherwise not.

#include<iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
              int a[51];
              int n,k;
              int ans = 0;
              cin >> n >> k;
              for(int i = 0;i < n;i++)
              {
                      cin >> a[i];
                      if(a[i]%2 == 0) ans++;
              }
              if(ans >= k) cout << "YES" << endl;
              else cout << "NO" << endl;
    }
    return 0;
}
2 Likes

Hello,

This was my logic too, especially due to this sentence:

" So for the gift, chef will choose a consecutive non-empty segment of the array. The segment should contain exactly k even integers. Though it can have any number of odd integers. "

As for the highlighted part in bold, I thought something along the lines of:

“Well, they if I choose the entire array, I only need to check if the even numbers on it is >= K”

However, this gave A LOT of Wrong Answers… I also wonder why…

In the end, the only way I managed to get AC was to code a plain brute force solution by generating all the 50*49 consecutive subarrays…

Maybe I misunderstood the problem or maybe it was badly phrased… Didn’t you try the brute force method?

Bruno

1 Like

I think the case you are missing when k=0 and all number are even …your code would output YES but the correct ans is NO

4 Likes

suppose k=0 and number of even integers in the array are n…then ur code won’t work

1 Like

One special condition check is enough. It is when whole array consists of even integers and k = 0.

Consider the constraint, k=0 i.e The chef wants to gift a segment which contains no even numbers.
Eg 5 0
4 2 4 10 12
Your answer YES whereas the answer should have been NO.

Added one more if condition. This will work fine.

#include<iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
              int a[51];
              int n,k;
              int ans = 0;
              cin >> n >> k;
              for(int i = 0;i < n;i++)
              {
                      cin >> a[i];
                      if(a[i]%2 == 0) ans++;
              }
              if(ans==n && k==0) cout << "NO" << endl;
               else if(ans >= k) cout << "YES" << endl;
              else cout << "NO" << endl;
    }
    return 0;
}
1 Like

If your ans value is n and k is 0 then it should return no instead of yes

1 Like

same problem…is it consecutive even numbers is what they want ?

But it still won’t matter. I proved my algo. Its correct.

your method is wrong think it over.