SUMPARITY - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Vishesh Saraswat
Tester: Istvan Nagy
Editorialist: Vedant Singh

DIFFICULTY:

SIMPLE

PREREQUISITES:

Bitwise Operators, Math, Observation

PROBLEM:

Given the number of elements N in a hidden array and the bitwise AND A of the entire array. Find the parity of the sum of the elements of the array.

QUICK EXPLANATION:

If the least significant bit of A is 1, the parity of sum is the same as parity of N. If the least significant bit of A is 0, the parity of sum can not be determined unless N is 1 (in which case the parity will be the same as parity of A)

EXPLANATION:

If the least significant bit of A is 1, we can see that the least significant bit(LSB) of every element of the array must be 1, because if for some element, the LSB was equal to 0, the AND would also become 0, by the definition of bitwise AND. Hence, we see that for every element, the LSB is 1, which means that all the elements are odd. The sum of N odd numbers is odd, if N is odd and is even if N is even. Thus, the parity of the sum of elements is equal to the parity of the number of elements N.

If the LSB of A is 0, we can make no deduction about the parity of the sum of elements because we cannot maintain the count of odd elements and even elements, except for when the number of elements is equal to 1.

Proof:

Let us say that the number of elements is N where N \geq 2, then there is a possibility that it has exactly N even elements and 0 odd elements, resulting in an even sum. The LSB of A in such a case is equal to 0. On the other hand, there also exists a case where there are exactly N-1 even elements and 1 odd element. In this case, the sum of elements is odd, while the LSB of A is still equal to 0. Hence, we cannot conclusively state whether the parity of the sum is even or odd.

If the LSB of A is 0 and N is equal to 1. there is only one element and since the LSB is 0 that element is even and hence the sum is also even.

TIME COMPLEXITY:

O(1) for each testcase

SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()

using ll = long long;
const int mod = 1e9+7;

void solve(int tc) {
    int n, a;
    cin >> n >> a;
    if (n == 1) {
        if (a&1)
            cout << "Odd\n";
        else
            cout << "Even\n";
        return;
    }
    if (a&1) {
        if (n&1)
            cout << "Odd\n";
        else
            cout << "Even\n";
        return;
    }
    cout << "Impossible\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}

Tester's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <cassert>
using namespace std;

#ifdef HOME
#define NOMINMAX
#include <windows.h>
#endif

long long readInt(long long l, long long r, char endd) {
	long long x = 0;
	int cnt = 0;
	int fi = -1;
	bool is_neg = false;
	while (true) {
		char g = getchar();
		if (g == '-') {
			assert(fi == -1);
			is_neg = true;
			continue;
		}
		if ('0' <= g && g <= '9') {
			x *= 10;
			x += g - '0';
			if (cnt == 0) {
				fi = g - '0';
			}
			cnt++;
			assert(fi != 0 || cnt == 1);
			assert(fi != 0 || is_neg == false);

			assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
		}
		else if (g == endd) {
			assert(cnt > 0);
			if (is_neg) {
				x = -x;
			}
			assert(l <= x && x <= r);
			return x;
		}
		else {
			//assert(false);
		}
	}
}

string readString(int l, int r, char endd) {
	string ret = "";
	int cnt = 0;
	while (true) {
		char g = getchar();
		assert(g != -1);
		if (g == endd) {
			break;
		}
		cnt++;
		ret += g;
	}
	assert(l <= cnt && cnt <= r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
	return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
	return readString(l, r, ' ');
}

int main() {
#ifdef HOME
	if (IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T = readIntLn(1, 10'000);
	for (int tc = 0; tc < T; ++tc)
	{
		int N, A;
		N = readIntSp(1, 1'000'000'000);
		A = readIntLn(0, 1'000'000'000);
		if (N == 1)
		{
			if (A & 1)
				printf("Odd\n");
			else
				printf("Even\n");
		}
		else if(A&1)
		{
			if (N & 1)
				printf("Odd\n");
			else
				printf("Even\n");
		}
		else
		{
			printf("Impossible\n");
		}
	}
	assert(getchar() == -1);
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int N,A;
        cin>>N>>A; // Taking input
        if(A%2==0){                      //Checking whether A is even
            if(N==1){cout<<"Even"<<endl; //Checking whether N is equal to 1
            }
        else{
            cout<<"Impossible"<<endl; //If N !=1, the answer is Impossible
            }
        }
        else{
            if(N%2==0){
                cout<<"Even"<<endl; // If N is even , the answer is also Even
            }
        else{
            cout<<"Odd"<<endl; // Else, the answer is Odd
        }
        }
    }
	return 0;}

The event is a part of our annual tech symposium Exun 2021-22, powered by Athena Education.

6 Likes