PROBLEM LINK:
The Interstellar Problem
iiitv.str()4.0
Author: chitranshi351
Editorialist: chitranshi351
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Cooper is on Dr. Mann’s planet and his spaceship is protected by a special puzzle which needs to be solved within a minute. A binary puzzle is presented before him and each column represents a binary number( the top is the MSB,i.e, most significant bit).
In each move, he can choose any column or row and replace it with its XOR with the largest possible number having the exact same length. The key to the puzzle is the maximum possible sum of the numbers represented by each of the columns. Using any number of moves, help Cooper to rearrange the puzzle to obtain the key of the puzzle.
Prerequisites:
-
knowledge of binary operations like XOR.
-
basic knowledge of binary numbers
EXPLANATION:
In a binary number, the value of MSB is greater than the sum of values of the rest of the bits.
For example, number if we have a binary number 1111. The decimal value of MSB is 8 and the sum of remaining bits is 7(4+2+1). So the main idea here suggested is that, we must toggle the bits in such a way that the MSB must be 1 even if in doing that all other bits become 0.
The other catch is that “XOR with the largest possible number having the exact same length” simply means taking one’s complement of that column.
Using the above ideas, we can find our solution easily now. We toggle the columns such that we can make all values in first row as 1. After this, we simple count the number of ones in each row. If the number of 1s is less than the number of 0s, we toggle that row. And then finally, we find the sum.
SOLUTIONS:
Setter's Solution
/* package codechef;*/
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try
{
Scanner Sc = new Scanner(System.in);
int t = Sc.nextInt();
while((t--)>0)
{
int m = Sc.nextInt();
int n = Sc.nextInt();
int[][] grid = new int[m][n];
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
grid[i][j] = Sc.nextInt();
}
}
int score = 0;
//first making all moves to make 1st column all 1s
score = (1 << (m-1)) * n;
int ones;
for(int i = 1; i < m; i++)
{
ones = 0;
for(int j = 0; j < n; j++)
{
ones += (grid[0][j] == grid[i][j]) ? 1 : 0;
}
int max = (ones > (n-ones)) ? ones : (n-ones);
score += (1 << (m-1-i)) * max;
}
System.out.println(score);
}
} catch(Exception e) {
}
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, m, n;
cin>>t;
while(t-- > 0)
{
cin>>m;
cin>>n;
int grid[m][n];
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
cin>>grid[i][j];
}
}
int score = 0;
//first making all moves to make 1st column all 1s
score = (1 << (m-1)) * n;
int ones;
for(int i = 1; i < m; i++)
{
ones = 0;
for(int j = 0; j < n; j++)
{
ones += (grid[0][j] == grid[i][j]) ? 1 : 0;
}
int max = (ones > (n-ones)) ? ones : (n-ones);
score += (1 << (m-1-i)) * max;
}
cout<<score<<endl;
}
}