PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Ashish Gupta
Tester: Encho Mishinev
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium
PREREQUISITES:
Modular Linear Equations, Gauss-Jordan Elimination.
PROBLEM:
Given a grid with N rows and M columns. Some of the cells of the grid may contain treasure. For every cell, we know whether the number of cells adjacent to the current position, which contain treasure is odd or even for some cells. A Treasure layout is the set of cells containing the treasure. Find out the number of treasure layouts consistent with the information given.
QUICK EXPLANATION
- Assuming each cell in grid correspond to a variable, the information given in cells is nothing, but Modular System of Linear Equations. So, if the given set of equations does not have a solution, There is no valid treasure layout.
- Otherwise, what we can notice is that for an equation, we indirectly express one variable as a combination of other variables. Hence if we fix values for all but one variable of the equation, the last variable shall have only one valid value.
- This way, the total number of ways to make treasure layout is 2^{(N*M)-x}, where x is the number of dependent variables.
EXPLANATION
Quick Explanation said it all!
Let us suppose C[i][j] denote whether cell is present in position (i,j). If C[i][j] = 1, coin is present on the position (i,j), Otherwise C[i][j] = 0. So, when we have A[i][j] \neq 1, we are indirectly given the parity of sum of all four positions adjacent positions to (i,j) in C grid. Formally, If A[i][j] = 0, sum of C[i-1][j]+C[i][j-1]+C[i+1][j]+C[i][j+1] is odd, and if A[i][j] = 1, sum of C[i-1][j]+C[i][j-1]+C[i+1][j]+C[i][j+1] is even.
Considering all equations in modulo two, sum of C[i-1][j]+C[i][j-1]+C[i+1][j]+C[i][j+1] = A[i][j] if A[i][j] \neq -1.
This gives us a set of modular linear equations in N*M (one equation for every position in grid for which A[i][j] \neq -1.) We have now reduced the problem to linear equation solving for which we resort to Gaussian elimination. We want to find the number of variables which can be assigned any value so that given system of modular equations still holds. (This is called the number of independent variables in a system of linear equations.)
In the coefficient matrix, each row represents a different equation and each column represent the coefficient of the variable in each equation. The last column represents the constant term.
Gaussian Elimination is an algorithm to solve linear equations represented by coefficients in the matrix, using row operations, basically row swapping, multiplying a row with a constant or adding a multiple of one row to another row. A brief explanation of Gauss elimination can be found in the box. You can read it in detail here.
Click to view
We handle variable one by one and try to eliminate the current variable from all the remaining equations by the third row operation, that is, adding a multiple of one equation (current equation assuming it has a non-zero coefficient for current variable) to another equation. Here we choose the multiple which turns the coefficient of the current variable in other equation to zero. If we have all coefficients zero, we have found one independent variable, so we skip on to the next variable.
The number of independent variables is N*M less the number of dependent variables. The number of dependent variables is the number of columns which have at least one non-zero coefficient after considering all previous variables.
In the current problem, we need to solve equations modulo x. We can still apply the same algorithm. In this case, it returns the solutions within the range of modulo.
Now that we have found the number of independent variables, say x, we can assign them any of the two values and the equations would still hold. So, The number of treasure layouts is 2^x. This is the final answer we require here.
Also, if we are working with modulo 2, interestingly, it can also be done much more efficiently using bitset operations by realizing that we can just take the xor of two rows (Equations) also serve our purpose which has been explained in the blog.
About the time complexity, The number of variables is N*M and the number of equations can be up to N*M (If all entry of A are either zero or one). So, Time complexity comes out to be of order ((N*M)^3) with the constant factor being 1/32 or 1/64 depending upon the implementation of BitSets used.
Time Complexity
Time complexity is O((N*M)^3) with constant factor being 1/32 or 1/64 depending upon implementation.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Click to view
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N=35;
const int MOD=1e9+7;
struct Equation
{
static const int blockSize = 63;
int n, blockCnt;
vector<long long> coefficients;
long long output;
Equation() {}
Equation(int _n)
{
n=_n;
blockCnt = (n - 1) / blockSize + 1;
coefficients = vector<long long> (blockCnt);
}
void addCoefficient(int idx)
{
int blockIdx = idx / blockSize;
int curIdx = idx % blockSize;
coefficients[blockIdx] += (1LL << curIdx);
}
bool hasIdx(int idx)
{
int blockIdx = idx / blockSize;
int curIdx = idx % blockSize;
return ((coefficients[blockIdx] >> curIdx & 1LL) == 1LL);
}
void doxor(Equation &e)
{
for(int i=0;i<coefficients.size();i++)
coefficients[i]^=e.coefficients[i];
output ^= e.output;
}
bool isInconsistent()
{
return (output == 1);
}
};
int n, m, sz=0;
int a[N][N];
int unknown;
bool hasSolution(vector<Equation> &eq)
{
int curIdx = 0;
int selected = 0;
for(int i=0;i<n*m && curIdx<eq.size();i++)
{
int swapIdx = -1;
for(int j=curIdx;j<eq.size();j++)
{
if(eq[j].hasIdx(i))
{
swapIdx = j;
break;
}
}
if(swapIdx == -1)
continue;
selected++;
swap(eq[curIdx], eq[swapIdx]);
for(int j=curIdx+1;j<eq.size();j++)
{
if(eq[j].hasIdx(i))
eq[j].doxor(eq[curIdx]);
}
curIdx++;
}
unknown = n * m - selected;
bool ans = true;
for(int j=curIdx;j<eq.size();j++)
{
if(eq[j].isInconsistent())
ans = false;
}
return ans;
}
int pow(int a, int b, int m)
{
int ans=1;
while(b)
{
if(b&1)
ans=(ans*a)%m;
b/=2;
a=(a*a)%m;
}
return ans;
}
int getInd(int x, int y)
{
return m*x + y;
}
int32_t main()
{
IOS;
int t;
cin>>t;
while(t--)
{
sz=0;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
sz+=(a[i][j]!=-1);
}
}
vector<Equation> eq(sz);
int idx=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]==-1)
continue;
eq[idx] = Equation(n * m);
if(i - 1 >= 0)
eq[idx].addCoefficient(getInd(i - 1, j));
if(i + 1 < n)
eq[idx].addCoefficient(getInd(i + 1, j));
if(j - 1 >= 0)
eq[idx].addCoefficient(getInd(i, j - 1));
if(j + 1 < m)
eq[idx].addCoefficient(getInd(i, j + 1));
eq[idx].output = a[i][j];
idx++;
}
}
if(hasSolution(eq))
{
int ans=pow(2LL, unknown, MOD);
cout<<ans<<endl;
}
else
cout<<0<<endl;
}
return 0;
}
Tester’s solution
Click to view
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <bitset>
using namespace std;
typedef long long llong;
const llong MOD = 1000000007LL;
int t;
int n,m;
bitset<901> equations[901];
int eL = 0;
int id[32][32];
int countChoices()
{
int r = 1;
int i,j;
for (i=1;i<=n*m;i++)
{
int firstOne = -1;
for (j=r;j<=eL;j++)
{
if (equations[j][i] == 1)
{
firstOne = j;
break;
}
}
if (firstOne == -1)
continue;
if (firstOne != r)
{
equations[r] = equations[r] ^ equations[firstOne];
}
for (j=r+1;j<=eL;j++)
{
if (equations[j][i] == 1)
{
equations[j] = equations[j] ^ equations[r];
}
}
r++;
}
for (i=r;i<=eL;i++)
{
if (equations[i][0] == 1)
return -1;
}
return n * m - (r - 1);
}
int main()
{
int i,j;
int test;
scanf("%d",&t);
for (test=1;test<=t;test++)
{
llong ans = 1;
eL = 0;
scanf("%d %d",&n,&m);
int ctr = 0;
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
ctr++;
id[i][j] = ctr;
equations[ctr].reset();
}
}
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
int a;
scanf("%d",&a);
if (a != -1)
{
eL++;
equations[eL].set(0, a);
if (i > 1)
equations[eL].set(id[i-1][j]);
if (i < n)
equations[eL].set(id[i+1][j]);
if (j > 1)
equations[eL].set(id[i][j-1]);
if (j < m)
equations[eL].set(id[i][j+1]);
}
}
}
int choices = countChoices();
if (choices == -1)
ans = 0;
else
{
for (i=1;i<=choices;i++)
{
ans *= 2LL;
ans %= MOD;
}
}
printf("%lld\n",ans);
}
return 0;
}
Editorialist’s solution
Click to view
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
//SOLUTION BEGIN
void pre() throws Exception{}
int[][] D = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
void solve(int TC) throws Exception{
int n = ni(), m = ni();
int[][] a = new int[n][m];int c = 0;
for(int i = 0; i< n; i++){
for(int j = 0; j< m; j++){
a[i][j] = ni();
if(a[i][j]!=-1)c++;
}
}
Row[] r = new Row[c];c=0;
for(int i = 0; i< n; i++)
for(int j = 0; j< m; j++){
if(a[i][j]==-1)continue;
r[c] = new Row(n*m);
for(int[] d:D){
int ii = i+d[0], jj = j+d[1];
if(ii<0||ii>=n || jj<0||jj>=m)continue;
r[c].add(ii*m+jj);
}
r[c++].output=a[i][j];
}
int ans = check(r,n*m);
if(ans==-1)pn(0);
else pn(pow(2,ans));
}
long pow(long a, long p){
long o = 1;
while(p>0){
if((p&1)==1)o=(o*a)%mod;
a=(a*a)%mod;
p>>=1;
}
return o;
}
class Row{
long[] coef;
int sz = 60,cnt, n;
int output = 0;
public Row(int n){
this.n=n;
cnt = (n-1)/sz+1;
coef = new long[cnt];
}
void add(int ind){
coef[ind/sz] |= 1l<<(ind%sz);
}
boolean has(int ind){
return ((coef[ind/sz]>>(ind%sz))&1)==1;
}
void xor(Row r){
for(int i =0; i< cnt; i++)coef[i]^=r.coef[i];
output^=r.output;
}
public Row clone(){
Row r = new Row(n);
r.xor(this);
return r;
}
}
int check(Row[] a, int var) throws Exception{
int cur = 0, x = 0;
for(int i= 0; i<var && cur<a.length; i++){
int swapInd = -1;
for(int j = cur; j<a.length; j++)if(a[j].has(i)){
swapInd = j;break;
}
if(swapInd==-1)continue;
x++;
Row tmp = a[cur].clone();
a[cur] = a[swapInd];
a[swapInd] = tmp;
for(int j = cur+1; j<a.length;j++)if(a[j].has(i))a[j].xor(a[cur]);
cur++;
}
while(cur<a.length)if(a[cur++].output!=0)return -1;
return var-x;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e3+1;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 