TREASURE - EDITORIAL

gauss-elim
march19
medium
taran_1407
treasure

#1

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*[j] denote whether cell is present in position (i,j). If C*[j] = 1, coin is present on the position (i,j), Otherwise C*[j] = 0. So, when we have A*[j] eq 1, we are indirectly given the parity of sum of all four positions adjacent positions to (i,j) in C grid. Formally, If A*[j] = 0, sum of C[i-1][j]+C*[j-1]+C[i+1][j]+C*[j+1] is odd, and if A*[j] = 1, sum of C[i-1][j]+C*[j-1]+C[i+1][j]+C*[j+1] is even.

Considering all equations in modulo two, sum of C[i-1][j]+C*[j-1]+C[i+1][j]+C*[j+1] = A*[j] if A*[j] eq -1.

This gives us a set of modular linear equations in N*M (one equation for every position in grid for which A*[j] eq -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 "

"
#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*^=e.coefficients*;
		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*[j];
				sz+=(a*[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*[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*[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]* == 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]* == 1)
            {
                equations[j] = equations[j] ^ equations[r];
            }
        }
 
        r++;
    }
 
    for (i=r;i<=eL;i++)
    {
        if (equations*[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*[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*[j-1]);
                    if (j < m)
                        equations[eL].set(id*[j+1]);
                }
            }
        }
 
        int choices = countChoices();
 
        if (choices == -1)
            ans = 0;
        else
        {
            for (i=1;i<=choices;i++)
            {
                ans *= 2LL;
                ans %= MOD;
            }
        }
 
        printf("%lld

",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*[j] = ni();
                if(a*[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*[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*[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*^=r.coef*;
            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. :slight_smile:


Coloring Grid
#2

IMHO the described time complexity exceeds the allotted time limits for the problem:
with N=30, M=30, and the constant factor of 1/64 we have:
(30*30)^3/64 \approx 10^7 however a test case may have up to T=100 tests, therefore the total time complexity is a bit above 10^9, and the time limit for the problem is 3 seconds.

How come?

Does it mean that the given test cases were made intentionally or unintentionally weak in order to fit within time limits?


#3

There are a couple of factors, that make the constant smaller, while still being O((N*M)^3) overall:

  1. The set of equations can be split into two independent sets - one for A*[j] with i+j even, and another with i+j odd. It makes the number of equations in each set \frac{N*M}{2} and an additional constant factor of 1/4.
  2. The coefficients matrix is very sparse - initially at most 4 non-zero coefficients in each equation and each coefficient is non-zero in at most 4 equations. It makes elimination process faster. At each elimination loop many rows of the coefficients matrix will have the corresponding coefficient 0 and thus not requiring iterating over that row.

#4

The problem does not state strictly that there is a solution. For example, the 2 x 2 map below is inconsistent (C[0][0] + C[1][1] must be even and odd):

input:
1
2 2
-1 2
1 -1

corresponding to:
? | 2
--+--
1 | ?

So it is necessary to solve the equation with x independent variables, and the final answer is either 0 if there is no solution, or 2 ** (N * M - x) if there is one.


#5

Yeah I also have the same doubt.


#6

Bitsets are far more efficient than the theoretical factor of 64 because of locality and instruction-level parallelism.

You don’t need to add an equation for an indeterminant cell, so you end up with a much smaller matrix.

Also, the matrix is sparse. So, you each equation has eight variables, so the complexity is actually like O((N*M)^2).