A. Odd Selection | Codeforces Round 646 (Div. 2) | Solution

                                    A. Odd Selection

Shubham has an array  of size , and wants to select exactly  elements from it, such that their sum is odd. These elements do not have to be consecutive. The elements of the array are not guaranteed to be distinct.

Tell him whether he can do so.


The first line of the input contains a single integer  (1100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers  and  (11000) — the length of the array and the number of elements you need to choose.

The next line of each test case contains  integers 1,2,, (11000) — elements of the array.


For each test case, print "Yes" or "No" depending on whether it is possible to choose  elements such that their sum is odd.

You may print every letter in any case you want.


What we need is odd number of odd numbers so we will iterate over number of odd numbers and check if we can select x numbers to form the sum as odd

#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
  int x = 1;
  while (b)
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  return x;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

const int N = 200005;

void solve() {

int n,x;

vi v(n);
int odd = 0, even = 0;
for (int i = 0; i < n; i++)
even = n-odd;


for(int i=1; i<=odd && i<=x; i+=2){
    int need = x-i;
    if(need<=0 || need<=even){


int32_t main()
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();

  int t = 1;
  cin >> t; 
  while (t--) solve();

  return 0;

Post a Comment