EVENXOR - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Jeevan Jyot Singh
Tester: Aryan Choudhary
Editorialist: Lavish Gupta

DIFFICULTY:

Simple

PREREQUISITES:

Bitwise Xor

PROBLEM:

A number X is called bad if its binary representation contains odd number of 1 bits. For example, X = 13 = (1101)_2 is bad while X = 3 = (11)_2 is not bad.

Chef calls an array A of length N special if the following conditions hold:

  • For each 1 \le i \le N, 0 \le A_i \lt 2^{20}
  • All the elements of A are distinct
  • There does not exist any non-empty subset of A such that the bitwise XOR of the subset is bad.

For example,

  • A = [2, 3, 4] is not special because the XOR of the subset [2, 3] is 2 \oplus 3 = 1, which is bad. (\oplus denotes the bitwise XOR operation)
  • A = [3, 3] is not special because its elements are not distinct.
  • A = [3, 5] is special because it satisfies all the conditions.

Chef challenges you to construct any special array of length N. Can you complete Chef’s challenge?

Hints:

A number X is called bad if its binary representation contains odd number of 1 bits.
Let the number X be called good if its binary representation contains even number of 1 bits.

Hint 1

When we take XOR of two bits, the total number of 1 bits either remains same, or decreases by 2.

Hint 2

When we take XOR of two numbers, the total number of 1 bits changes by even number.

Hint 3

When we take XOR of set numbers, the total number of 1 bits changes by even number.

Hint 4

Consider any set of good numbers. The XOR of the subset will also be a good number.

EXPLANATION:

Let us use the defined terminology of good and bad elements.

Our aim is to construct a special array of length N. In other words, we want to create an array of length N containing distinct elements, such that there doesn’t exist any non-empty subset such that the bitwise XOR of the subset is bad.

Approach 1

Let us first analyze, what happens when we take XOR of two numbers.

Taking XOR of two 1-bit numbers

We have 4 possible cases:

  • 0 \oplus 0 = 0
  • 0 \oplus 1 = 1
  • 1 \oplus 0 = 1
  • 1 \oplus 1 = 0

An important point to note is, the total number of 1-bits remain same in the first 3 cases, and decreases by 2 in the last case.

Taking XOR of two numbers

We have seen that when we take XOR of two bits, the total number of 1-bits either remains same, or decreases by 2. In other words, the total number of 1-bits changes by even number.

When we take XOR of two K-bit numbers, we can consider the operation as taking XOR of two 1-bit numbers K times. And therefore, we can extend the above argument and say that the total number of 1-bits changes by even number.

Taking XOR of set of numbers

Let the set S = \{ S_1 , S_2 , \cdots , S_K\}.
The XOR of the set S is defined as (((S_1 \oplus S_2) \oplus S_3) \oplus \cdots \oplus S_K)

In other words, it is K-1 successive XORs. We can again extend the same argument as above, and say that when we take XOR of set of numbers, the total number of 1-bits changes by even number.

After making the above observations, let us shift our focus to the subsets.

Each individual element of the array is a valid subset. Let us focus on the subset \{A_i\}.
The XOR of this subset is A_i, and therefore A_i should have even number of 1-bits.
This holds for all i : 1 \leq i \leq N.

Once we have the above property in the array, by using the observation 3 (Taking XOR of set of numbers), we can claim that XOR of any subset is good because the total number of 1-bits in the subset is even (sum of even numbers is even), and after taking XOR, the number of 1-bits changes by even number. Hence, the resulting XOR has even number of set bits.

Finally, we need a list of 1000 good numbers. To get the list of good numbers, we can start iterating from 0, and check if the number is good or not by counting number of set bits.

Can you prove that there are 2^{10} good numbers which are less than 2^{11}?

Approach 2

As we have seen in the first approach, each individual element of the array is a valid subset. Let us focus on the subset \{A_i\}. The XOR of this subset is A_i, and therefore A_i should have even number of 1-bits.
This holds for all i : 1 \leq i \leq N.

We also have to follow the constraint that A_i < 2^{20}. In other words, A_i can be a 20-bit number.
Let us divide these 20-bits in two halves, first 10-bits, and last 10-bits.
Now, consider the numbers where first half is exactly same as the second half. Let’s call such numbers as special numbers. So for example, 1000010000-1000010000 is a special number.

Total count of *special numbers*

Let us fill the first 10 bits. Total number of ways to fill them = 2^{10} = 1024.
Now, we can replicate these first 10 bits in the last 10 bits.
Hence, total count of special numbers = 1024

Parity of number of set-bits in a *special number*

Because the first 10-bits are exactly replicated as the last 10-bits, we can claim that the number of set-bits will always be even.

XOR of two *special numbers*

Consider two special numbers A and B. Let A \oplus B = C.
Analyze first 10-bits and last 10-bits of C. They are exactly same!! (Why?)
And therefore, C is a special number, and has even number of set bits.

Note that any special number can be simply written as (i\cdot 2^{10} + i) where 0 \leq i < 2^{10}.

The above three statements tells us that if each A_i is a distinct special number, all the three conditions are satisfied, and we have solved our problem!!

TIME COMPLEXITY:

We can first create the list of 1000 good numbers by iterating from 0 till 2^{11}.
Then for each test case, we can print first N numbers from the list. Hence time complexity is O(N) per testcase.

SOLUTION:

Setter's Solution
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const double EPS = 1e-9;
const long long INF = 1e18;

const int N = 1e3 + 5; 

vector<int> ans;

int32_t main()
{
    IOS;
    for(int i = 0; sz(ans) < N; i++)
    {
        if(__builtin_popcountll(i) % 2 == 0)
            ans.push_back(i);
    }
    int T; cin >> T;
    while(T--)
    {
        int n; cin >> n;
        for(int i = 0; i < n; i++)
            cout << ans[i] << " ";
        cout << endl;
    }
    return 0;
}
Tester's Solution
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#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) {
            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,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         const lli u=readIntSp(1,n)-1;
//         const lli v=readIntLn(1,n)-1;
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
#define bcnt(x) (__builtin_popcount(x))
    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
const lli maxN = 1e3;
vi a;
for(lli i=0;sz(a)<maxN;++i){
    if(bcnt(i)&1)
        continue;
    a.pb(i);
}
T=readIntLn(1,1e2);
while(T--)
{

    n=readIntLn(1,1e3);
    for(int i=0;i<n;++i)
        cout<<a[i]<<" \n"[i+1==n];
}   aryanc403();
    readEOF();
    return 0;
}

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std ;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    int t ;
    cin >> t ;

    int arr[1000] ;
    int ind = 0 , val = 0 ;

    while(ind < 1000)
    {
        int curr_set_bits = __builtin_popcount(val) ;

        if(curr_set_bits%2 == 0)
        {
            arr[ind] = val ;
            ind++ ;
        }
        val++ ;
    }


    while(t--)
    {
        int n ;
        cin >> n ;
        for(int i = 0 ; i < n ; i++)
        {
            cout << arr[i] << ' ';
        }
        cout << '\n' ;
    }
 
    return 0;
}
6 Likes

can you help me to recognize what are the test cases this code fails…
for _ in range(int(input())):
n=int(input())
nu=3
for i in range(n):
print(nu,end=" “)
nu<<=1
print(end=”\n")

For N \gt 20, the elements you output do not satisfy the constraint A_i \lt 2^{20}.

2 Likes

A good number has an even number of 1's in its binary representation.

Consider the binary representation of numbers less than 2^{11}:

We have 11 places to fill with 0's and 1's, such that the number of 1's is Even.

So, number of good numbers less than 2^{11} is given by:

\binom{11}{0} + \binom{11}{2} + \binom{11}{4} + \dots + \binom{11}{8} + \binom{11}{10} = \cfrac{2^{11}}{2} = 2^{10}.

3 Likes

I havent read the editorial yet but I came up with a observation during the contest

N=1 output=[3]
N=2 output=[3,5]
N=3 output=[3,5,9]

so the output will be 2^i+1 for 1<=i<=N
But this is giving WA

Where am I going wrong? Can anyone give me a test case where this logic fails
My solution

thanks you for your response i understood that this code fails at constrains.

1 Like

This solution was derived from a different solution I came up with to counter TLE. This one prints
out the elements from the pre-made list.
I still get two test cases as wrong and I cant figure out how. I am hoping you would know?
Solution: 56751394 | CodeChef
This is the solution with 1000 elements as the number limit is 1000

Actually this way u are considering numbers with 2 bits in its binary form, so at max u can form
20C2=190 (as A(i) <=2^20 i.e 20 bits but N is upto 1000.

1 Like

You observed correctly, but if you look closer you’ll see that it’s not always 2^i+1, because N can be as large as 1000. So, this approach is correct only till N = 29.

1 Like

Solution
can anyone point out my mistake?

The Binary representation of 1999 has 9 set bits. You should exclude it from the hard-coded list.

Replace if(x == 2 || !x) with if(x % 2 == 0)

Why x == 2 not possible when we can choose 2 setbits in all numbers with max 20 bits
20*19 nos are possible

No, you got it wrong. It is not 20\times 19, it is \binom{20}{2} viz., \cfrac{20\times 19}{2 \times 1} = 190. You can output atmost 191 integers (including 0) in this way.

Edit: LMAO, for a second, even I thought 20\times 19 \gt 1000 :man_facepalming:

Either way, you cannot output a sufficient number of integers.

The size of number was limited to 2^20 , or 20 bits , therefore , your code can only work upto N=18, N can go to 1000

Thanks I thought it would be greater than 1000🤡

MyBrokenCode
Can someone help me what i am doing wrong?

Try increasing j upto 2000. In the worst case, the last number in the answer goes upto 1998.