Dima and Bad Xor Problem – Codeforces ( Div. 2 )

 

Problem Statement

A matrix  ‘a’ of size n*m is filled with non-negative integers. We have to select exactly one integer from each row such that bitwise exclusive or of all selected integers is greater than zero.

Here x⊕y denotes the bitwise XOR operation of integers x and y.

INPUT

The first line contains integers n and m i.e. number of rows and columns in matrix a.

Next n line contains m integers i.e. elements of n*m matrix.

OUTPUT 




If there is no way to choose one integer from each row so that their bitwise exclusive OR is strictly greater than zero, print “NIE“.

Otherwise print “TAK” in the first line, in the next line print m integers.

Cases for XOR of two numbers to be zero

Xor of two number a^b can only be zero when both the number ( a and b ) are the same in that case bits of both numbers are the same and final result will be zero. Other cases for xor of two numbers to be zero is when both the numbers are 0.

Algorithm: Dima and Bad Xor Problem

  • Take a 2-D array arr[][] of size m*n.
  • Now, take the xor of the first element of each row and store it in variable ans.
  • If ans in not zero means 1st element of each row satisfying for the output then print ‘1’ n times.
  • In other case take another array temp[] of size n initialize each element of temp[] array to zero using memset.
  • Now, fill temp[] array for each row if u find an element in each row starting from 2nd element which is not equal to 1st element.
  • If we are getting ans zero so it may be the case that all 1st element of each row is zero or maybe all elements are same or may be some same and some zero. So, in this case we need to find one element which is different from 1st element in its row and it should not to be zero. Here, we use temp[] array as it already stores element in a row which is different from 1st element in its row.
  • If we are able to find such an element then we push the position of that element in a vector container and for rest row, we push value 1 and print “TIE”. Otherwise, we print “NIE”.

C++ Code to solve Dima and Bad Xor Problem

#include<bits/stdc++.h>

#define Fast  std::ios::sync_with_stdio(false);  cin.tie(NULL);

#define pb  push_back

#define mp  make_pair

#define fi  first

#define se  second

#define all(x) x.begin(),x.end()

#define p pair<ll,ll>

#define pii pair<int,int>

#define mod (int)(1e9+7)

#define PI  (double)(3.14159265358979323846264338327950)
using namespace std;

typedef long long ll;

 ll i,j;    

    int main()
  {
      ll n,m;
       cin>>n>>m;
       
       int arr[n+1][m+1], temp[n+1];
       
       for(i=0;i<n;i++)
         for(j=0;j<m;j++)
           cin>>arr[i][j];
           
           int ans=0;
           
           memset(temp,0,sizeof(temp));
           
             for(i=0;i<n;i++)
           {
               ans=ans^arr[i][0];
               
                 for(j=1;j<m;j++)
               {
                     if(arr[i][0]!=arr[i][j])
                   {
                       temp[i]=j+1;
                   }
               }
           }
           
           if(ans!=0)
           {
               cout<<"TAK"<<endl;
               
               for(i=1;i<=n;i++)
                 cout<<1<<" ";
                 cout<<endl;
                 return 0;
           }
           
           vector<int>v;
           int flag=0;
           
             for(i=0;i<n;i++)
           {
                if(flag==0 && temp[i]!=0)  
              {
                   v.pb(temp[i]);
                    flag=1;
              }
              
                else
                {
                    v.pb(1);
                }
           }
           
           if(flag==0)
           {
               cout<<"NIE"<<endl;
           }
           
           else
           {
               cout<<"TAK"<<endl;
              
                  for(auto i:v)
                    cout<<i<<" ";
                    cout<<endl;
           }
  }

Example 1

3 2

0 0

0 0

0 0

OUTPUT

NIE

Example 2

2 3

7 7 7

7 7 10

OUTPUT

TAK
1 3

Also, learn:


Leave a Reply

Your email address will not be published. Required fields are marked *