ANDOR - Editorial

psychik · October 26, 2020, 10:52pm

PROBLEM LINK:

Practice
Contest

Setter: Mohammed Ehab
Tester: Ramazan Rakhmatullin
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Simple

PREREQUISITES:

Bitwise Operators and Basic Maths

PROBLEM:

Given an integer x, find two non-negative integers a and b such that (a∧b)+(a∨b)=x, where ∧ is the bitwise AND operation and ∨ is the bitwise OR operation.

EXPLANATION:

One simple solution which satisfy this equation is a = 0 and b = x, so (a∧b) = 0 and (a∨b) = x, hence satisfing the equation.
Also, note that x can range between [1, 10^{18}] so use a big enough data type to store it.

TIME COMPLEXITY:

Time complexity per test case will be O(1).

SOLUTIONS:

Setter's Solution

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		long long x;
		scanf("%lld",&x);
		printf("0 %lld\n",x);
	}
}

Tester's Solution

#include <bits/stdc++.h>
 
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wunused-const-variable"
#define popcnt(x) __builtin_popcount(x)
 
#define fr first
 
#define sc second
 
#define m_p make_pair
 
#define low_bo(a, x) lower_bound(a.begin(), a.end(), x) - a.begin()
 
#define up_bo(a, x) upper_bound(a.begin(), a.end(), x) - a.begin()
 
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
 
#define popcnt(x) __builtin_popcount(x)
 
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
 
//gp_hash_table<int, int> table;
 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))
 
/*char memory[(int)1e8];
char memorypos;
 
inline void * operator new(size_t n){
    char * ret = memory + memorypos;
    memorypos += n;
    return (void *)ret;
}
 
inline void operator delete(void *){}
*/
 
using namespace std;
 
typedef long long ll;
 
typedef unsigned long long ull;
 
typedef long double ld;
 
typedef unsigned int uint;
 
template<typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;
 
    constexpr Modular() : value() {}
 
    template<typename U>
    Modular(const U &x) {
        value = normalize(x);
    }
 
    static Type inverse(Type a, Type mod) {
        Type b = mod, x = 0, y = 1;
        while (a != 0) {
            Type t = b / a;
            b -= a * t;
            x -= t * y;
            swap(a, b);
            swap(x, y);
        }
        if (x < 0)
            x += mod;
        return x;
    }
 
    template<typename U>
    static Type normalize(const U &x) {
        Type v;
        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
        else v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
    }
 
    const Type &operator()() const { return value; }
 
    template<typename U>
    explicit operator U() const { return static_cast<U>(value); }
 
    constexpr static Type mod() { return T::value; }
 
    Modular &operator+=(const Modular &other) {
        if ((value += other.value) >= mod()) value -= mod();
        return *this;
    }
 
    Modular &operator-=(const Modular &other) {
        if ((value -= other.value) < 0) value += mod();
        return *this;
    }
 
    template<typename U>
    Modular &operator+=(const U &other) { return *this += Modular(other); }
 
    template<typename U>
    Modular &operator-=(const U &other) { return *this -= Modular(other); }
 
    Modular &operator++() { return *this += 1; }
 
    Modular &operator--() { return *this -= 1; }
 
    Modular operator++(int) {
        Modular result(*this);
        *this += 1;
        return result;
    }
 
    Modular operator--(int) {
        Modular result(*this);
        *this -= 1;
        return result;
    }
 
    Modular operator-() const { return Modular(-value); }
 
    template<typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type &operator*=(const Modular &rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
        uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
        asm(
        "divl %4; \n\t"
        : "=a" (d), "=d" (m)
        : "d" (xh), "a" (xl), "r" (mod())
        );
        value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
    }
 
    template<typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type &
    operator*=(const Modular &rhs) {
        int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
 
    template<typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type &operator*=(const Modular &rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }
 
    Modular &operator/=(const Modular &other) { return *this *= Modular(inverse(other.value, mod())); }
 
    template<typename U>
    friend const Modular<U> &abs(const Modular<U> &v) { return v; }
 
    template<typename U>
    friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);
 
    template<typename U>
    friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
 
    template<typename U>
    friend std::istream &operator>>(std::istream &stream, Modular<U> &number);
 
private:
    Type value;
};
 
template<typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value == rhs.value; }
 
template<typename T, typename U>
bool operator==(const Modular<T> &lhs, U rhs) { return lhs == Modular<T>(rhs); }
 
template<typename T, typename U>
bool operator==(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) == rhs; }
 
template<typename T>
bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) { return !(lhs == rhs); }
 
template<typename T, typename U>
bool operator!=(const Modular<T> &lhs, U rhs) { return !(lhs == rhs); }
 
template<typename T, typename U>
bool operator!=(U lhs, const Modular<T> &rhs) { return !(lhs == rhs); }
 
template<typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) { return lhs.value < rhs.value; }
 
template<typename T>
Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) += rhs; }
 
template<typename T>
Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) -= rhs; }
 
template<typename T>
Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) *= rhs; }
 
template<typename T>
Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T> &rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> power(const Modular<T> &a, const U &b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}
 
template<typename T>
bool IsZero(const Modular<T> &number) {
    return number() == 0;
}
 
template<typename T>
string to_string(const Modular<T> &number) {
    return to_string(number());
}
 
template<typename T>
std::ostream &operator<<(std::ostream &stream, const Modular<T> &number) {
    return stream << number();
}
 
template<typename T>
std::istream &operator>>(std::istream &stream, Modular<T> &number) {
    typename common_type<typename Modular<T>::Type, int64_t>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}
 
const int md = 1e9 + 7;
 
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
 
ll sqr(ll x) {
    return x * x;
}
 
int mysqrt(ll x) {
    int l = 0, r = 1e9 + 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (m * (ll) m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}
 
#ifdef ONPC
mt19937 rnd(513);
mt19937_64 rndll(231);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
    mt19937_64 rndll(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
 
template<typename T>
T gcd(T a, T b) {
    return a ? gcd(b % a, a) : b;
}
 
int gcdex(int a, int b, int &x, int &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    int x1, y1;
    int ret = gcdex(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return ret;
}
 
void setmin(int &x, int y) {
    x = min(x, y);
}
 
void setmax(int &x, int y) {
    x = max(x, y);
}
 
void setmin(ll &x, ll y) {
    x = min(x, y);
}
 
void setmax(ll &x, ll y) {
    x = max(x, y);
}
 
const ll llinf = 4e18 + 100;
 
const ld eps = 1e-9, PI = atan2(0, -1);
 
const int maxn = 2e5 + 100, maxw = 2e6 + 1111, inf = 1e9 + 100, sq = 450, LG = 18, mod = 1e9 + 933, mod1 = 1e9 + 993;
 
int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
    freopen("../a.out", "w", stdout);
#else
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
#endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        ll x;
        cin >> x;
        cout << 0 << ' ' << x << '\n';
    }
}

Editorialist's Solution

#include <bits/stdc++.h>
using namespace std;
 
void Solve() {
	long long x;
	cin >> x;
	cout << 0 << " " << x << "\n";
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int test_case = 1;
	cin >> test_case;
	for(int i = 1; i <= test_case; i ++) {
		Solve();
	}
	
	return 0;
}

VIDEO EDITORIAL (Hindi):

VIDEO EDITORIAL (English):

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed.

sksama · October 31, 2020, 5:14pm

adi96433 · October 31, 2020, 5:21pm

good question , after solving came to the solution that all those pairs which satisfy
a + b =x can be the ans …hence (0,x),(1,x-1),(2,x-2)…so on

anon41069019 · October 31, 2020, 5:55pm

loved tester’s solution.

amb_xyz · October 31, 2020, 6:36pm

As the problem was simple and 3 lines in python so many python coders submitted same 3 lines therefore will codechef penalize all for plagiarism

akshitm16 · October 31, 2020, 6:51pm

You are not penalized for such cases afaik.

pro_001 · October 31, 2020, 6:56pm

i dont understand why my rating got decrease even i haven’t made any wrong submission why?
can any one clarify ?

beginersonu · October 31, 2020, 7:02pm

my simple solution
#include
using namespace std;

define ll unsigned long long

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t–){
ll x;
cin>>x;
ll a=x/2;
ll b=x-a;
cout<<a<<" "<<b<<endl;
}
return 0;
}

tanmay157 · October 31, 2020, 7:44pm

In lunchtime you have to focus on making submissions quickly. It doesn’t matter how many wrong submissions you make (tho it matters in cook off). You can check the rules here

a3000 · November 1, 2020, 5:32am

For even numbers like 8 why isn’t can’t we choose 4 and 4 as A and B, 4 & 4 is 4 and 4 | 4 is 4 they add up to 8. For odd numbers like 11, A is 11/2 and B is ceil(11/2) which is 5 and 6, 5&6=4 and 5|6=7, 7+4=11.
Can anyone tell me where I’m wrong?

aniket_0206 · November 1, 2020, 6:41am

is there any link that provides properties regarding bitwise operations

leo_valdez · November 2, 2020, 2:50am

This was the easiest problem on the test, and also the only one I was able to solve correctly. After 30 minutes of trying to solve the problem, I arrived at the setter’s solution.
Now I wonder why I wasted those 30 minutes, when the answer was so simple.

jahnvi_481 · August 18, 2022, 4:22am

check the constraint ,take x as long , your approach is correct.