Lights Out CodeChef Solution

Problem -Lights Out CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Lights Out CodeChef Solution in C++14

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <string>
#include <iomanip>
#include <cmath>
using namespace std;

const double eps = 1e-8;

template <class T>
struct Matrix
{
  static Matrix<T> getNormal(int R) {
    Matrix<T> ret(R,R);
    for (int i = 0; i < R; ++i)
      ret.data[i][i] = 1;
    return ret;
  }

  int R, C;
  vector<vector<T> > data;

  Matrix(int r,int c) 
  {
    R = r;
    C = c;
    data = vector<vector<T> >(R, vector<T>(C, 0));
  }

  Matrix(const Matrix & x) 
  {
    R = x.R;
    C = x.C;
    data = x.data;
  }

  /** swap two row in this matrix */
  void swapRow(int r1, int r2)
  {
    if (r1 == r2 || r1 >= R || r2 >= R) return;
    for (int j = 0; j < C; ++j)
      swap(data[r1][j], data[r2][j]);
  }

  /** swap two column in this matrix */
  void swapCol(int c1, int c2)
  {
    if (c1 == c2 || c1 >= C || c2 >= C) return;
    for (int i = 0; i < R; ++i)
      swap(data[i][c1], data[i][c2]);
  }

  /** subtract row2 = row2 - k * row1 */
  void subtractRowIFromRowJ(int r1, int r2, T k)
  {
    if (r1 == r2 || r1 >= R || r2 >= R) return;
    for (int j = 0; j < C; ++j)
    {
      data[r2][j] -= data[r1][j];
      if (data[r2][j] < 0)
        data[r2][j] = 1;
    }
  }

  bool isZero()
  {
    for (int i = 0; i < R; ++i)
      for (int j = 0; j < C; ++j)
        if (data[i][j] > 0)
          return false;
    return true;
  }

  bool isZeroRow(int r)
  {
    for (int j = 0; j < C; ++j)
      if (data[r][j] > 0)
        return false;
    return true;
  }

  /** merge this matrix with matrix right */
  Matrix<T> rightMergeMatrix(Matrix<T> & right)
  {
    if (right.R != R) 
      return (*this);

    Matrix<T> newMatrix(R, C + right.C);
    for (int i = 0; i < R; ++i)
      for (int j = 0; j < newMatrix.C; ++j)
        if (j < C)
          newMatrix.data[i][j] = data[i][j];
        else
          newMatrix.data[i][j] = right.data[i][j - C];
    return newMatrix;
  }

  /** do Gaussian Elimination on this matrix 
   * As explained above, Gaussian elimination writes a given m × n matrix A 
   * uniquely as a product of an invertible m × m matrix S and a row-echelon matrix T. 
   * Here, S is the product of the matrices corresponding to the row operations performed.
   * The formal algorithm to compute T from A follows. We write A[i,j] for the entry in row i, column j in matrix A. 
   * The transformation is performed in place, 
   * meaning that the original matrix A is lost and successively replaced by T.
   * @side effect matrix will change 
   */
  void gaussianElimination()
  {
    int i = 0;
    int j = 0;
    while (i < R && j < C)
    {
      int maxi = i;
      for (int k = i; k < R; ++k)
        if (data[k][j] > 0)
        {
          maxi = k;
          break;
        }

      if (data[maxi][j] > 0)
      {
        /** swap rows i and maxi, but do not change the value of i 
         * Now A[i,j] will contain the old value of A[maxi,j]. 
         * divide each entry in row i by A[i,j] 
         * Now A[i,j] will have the value 1.  
         */
        swapRow(i, maxi);

        /** subtract A[u,j] * row i from row u 
         * Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0.
         */
        for (int u = i + 1; u < R; ++u)
        {
          if (data[u][j] > 0)
            subtractRowIFromRowJ(i, u, data[u][j]);
        }
                 
        i++;
      }
      j++;
    }
  }

  /** Return the rank of this matrix 
   * @side effect the matrix will change
   */
  int rank()
  {
    gaussianElimination();
    int ret = 0;
    for (int i = 0; i < R; ++i)
      if (!isZeroRow(i))
        ret++;
    return ret;
  }
};

  template <class T>
ostream & operator << (ostream & out , const Matrix<T> & a)
{
  for (int i = 0; i < a.R; ++i) {
    for (int j = 0; j < a.C; ++j)
      out << setprecision(3) << a.data[i][j] << "\t";
    out << endl;
  }
  return out;
}

  template <class T>
Matrix<T> operator + (const Matrix<T> & a , const Matrix<T> & b)
{
  assert(a.R == b.R);
  assert(a.C == b.C);

  Matrix<T> ret(a.R , a.C);
  for (int i = 0; i < ret.R; ++i)
    for (int j = 0; j < ret.C; ++j)
      ret.data[i][j] = a.data[i][j] + b.data[i][j];
  return ret;
}

  template <class T>
Matrix<T> operator - (const Matrix<T> & a , const Matrix<T> & b)
{
  assert(a.R == b.R);
  assert(a.C == b.C);

  Matrix<T> ret(a.R , a.C);
  for (int i = 0; i < ret.R; ++i)
    for (int j = 0; j < ret.C; ++j)
      ret.data[i][j] = a.data[i][j] - b.data[i][j];
  return ret;
}

  template <class T>
Matrix<T> operator * (const Matrix<T> & a , double x)
{
  Matrix<T> ret(a.R , a.C);
  for (int i = 0; i < ret.R; ++i)
    for (int j = 0; j < ret.C; ++j)
      ret.data[i][j] = a.data[i][j] * x;
  return ret;
}

  template <class T>
Matrix<T> operator * (const Matrix<T> & a , const Matrix<T> & b)
{
  assert(a.C == b.R);
  Matrix<T> ret(a.R , b.C);

  for (int i = 0; i < a.R; ++i)
    for (int j = 0; j < b.C; ++j)
      for (int k = 0; k < a.C; ++k)
        ret.data[i][j] += a.data[i][k] * b.data[k][j];
  return ret;
}

  template <class T>
Matrix<T> operator ^ (const Matrix<T> & a , int deg)
{
  if (deg == 0)
    return Matrix<T>::getNormal(a.R);
  if (deg == 1) 
    return a;

  int half = deg / 2;
  int remain = deg - half * 2;
  Matrix<T> tmp = a ^ half;
  if (remain) 
    return tmp * tmp * a;
  else
    return tmp * tmp;
}

/** 
 * Return the inverse of this matrix
 */
template <class T>
bool inverseMatrix(Matrix<T> & a)
{
  vector<int> is(a.R, 0);
  vector<int> js(a.R, 0);
  T t;
  if (a.R != a.C) 
    return false;

  for (int k = 0; k < a.R; k++) 
  {
    t = 0;
    for (int i = k; i < a.R; i++)
      for (int j = k; j < a.R; j++)
        if (fabs(a.data[i][j]) > t)
          t = fabs(a.data[is[k] = i][js[k] = j]);

    if (fabs(t) < eps) return false;

    if (is[k] != k) a.swapRow(k, is[k]);
    if (js[k] != k) a.swapCol(k, js[k]);

    a.data[k][k] = 1 / a.data[k][k];
    for (int j = 0; j < a.R; j++)
      if (j != k) a.data[k][j] *= a.data[k][k];

    for (int i = 0; i < a.R; i++) if (i != k)
      for (int j = 0; j < a.R; j++) if (j != k)
        a.data[i][j] -= a.data[i][k] * a.data[k][j];

    for (int i = 0; i < a.R; i++)
      if (i != k) a.data[i][k] *= -a.data[k][k];
  }

  for (int k = a.R - 1; k >= 0; k--){
    for (int j = 0; j < a.R; j++)
      if (js[k] != k)
        t = a.data[k][j], a.data[k][j] = a.data[js[k]][j], a.data[js[k]][j] = t;
    for (int i = 0; i < a.R; i++)
      if (is[k] != k)
        t = a.data[i][k], a.data[i][k] = a.data[i][is[k]], a.data[i][is[k]] = t;
  }
  return true;
}

/** Solve linear equation
 * A m * n matrix 
 * b m * 1 vector
 * @return n * 1 solution
 */
template <class T>
Matrix<T> solveEquation(Matrix<T> & A, Matrix<T> & b, int & solutions)
{
  Matrix<T> nA = A;
  Matrix<T> zA = A.rightMergeMatrix(b);
  Matrix<T> ret(A.C, 1);

  int rank1 = nA.rank();
  int rank2 = zA.rank();
  //cout << nA << endl;
  //cout << zA << endl;

  //cout << rank1 << "\t" << rank2 << endl;

  if (rank1 != rank2)
  {
    solutions = 0;
    return ret;
  }

  if (rank1 < A.R)
    solutions = 2;
  else
    solutions = 1;


  /** cal the solution */
  for (int i = zA.R - 1; i >= 0; --i)
  {
    if (zA.isZeroRow(i)) continue;
    T nowB = zA.data[i][zA.C - 1];
    for (int j = 0; j < zA.C - 1; ++j)
      if (fabs(zA.data[i][j]) > 0)
      {
        ret.data[j][0] = nowB / zA.data[i][j];
        break;
      }
  }
  
  return ret;
}

/**
double det(const mat& a){
  int i,j,k,sign=0;
  double b[MAXN][MAXN],ret=1,t;
  if (a.n!=a.m)
    return 0;
  for (i=0;i<a.n;i++)
    for (j=0;j<a.m;j++)
      b[i][j]=a.data[i][j];
  for (i=0;i<a.n;i++){
    if (zero(b[i][i])){
      for (j=i+1;j<a.n;j++)
        if (!zero(b[j][i]))
          break;
      if (j==a.n)
        return 0;
      for (k=i;k<a.n;k++)
        t=b[i][k],b[i][k]=b[j][k],b[j][k]=t;
      sign++;
    }
    ret*=b[i][i];
    for (k=i+1;k<a.n;k++)
      b[i][k]/=b[i][i];
    for (j=i+1;j<a.n;j++)
      for (k=i+1;k<a.n;k++)
        b[j][k]-=b[j][i]*b[i][k];
  }
  if (sign&1)
    ret=-ret;
  return ret;
}
*/

int N;
int M;
int ori[300][300];
int temp[300][300];

map<pair<int, int>, int> specialLight;

void getFinalRow(vector<int> & finalRow, vector<int> & buttonOn)
{
  finalRow = vector<int>(N, 0);
  buttonOn = vector<int>(M, 0);

  for (int i = 0; i < N - 1; ++i)
    for (int j = 0; j < N; ++j)
      if (temp[i][j] == 1)
      {
        temp[i][j] = 0;
        temp[i + 1][j] = 1 - temp[i + 1][j];
        if (j > 0)
          temp[i + 1][j - 1] = 1 - temp[i + 1][j - 1];
        if (j < N - 1)
          temp[i + 1][j + 1] = 1 - temp[i + 1][j + 1];
        if (i + 2 < N)
          temp[i + 2][j] = 1 - temp[i + 2][j];

        pair<int, int> light = make_pair(i + 1, j);
        if (specialLight.find(light) != specialLight.end())
        {
          buttonOn[specialLight[light]] = 1;
        }
      }

  for (int i = 0; i < N; ++i)
    finalRow[i] = temp[N - 1][i];
}

void clear()
{
  specialLight.clear();
}

void deal()
{
  scanf("%d%d", &N, &M);

  string line;
  getline(cin, line);
  for (int i = 0; i < N; ++i)
  {
    getline(cin, line);
    for (int j = 0; j < N; ++j)
      ori[i][j] = line[j] - '0';
  }

  for (int i = 0; i < M; ++i)
  {
    int row = 0, col = 0;
    scanf("%d%d", &row, &col);
    specialLight[make_pair(row - 1, col - 1)] = i;
  }

  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      temp[i][j] = ori[i][j];


  vector<int> finalRow;
  vector<int> buttonOn;
  getFinalRow(finalRow, buttonOn);
  Matrix<int> B(N + M, 1);
  for (int i = 0; i < finalRow.size(); ++i)
    B.data[i][0] = finalRow[i];
  for (int i = 0; i < buttonOn.size(); ++i)
    B.data[i + N][0] = buttonOn[i];


  Matrix<int> A(N + M, N);
  for (int k = 0; k < N; ++k)
  {
    for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j)
        temp[i][j] = 0;

    for (int j = 0; j < N; ++j)
        temp[0][j] = 0;
    temp[0][k] = 1;
    temp[1][k] = 1;
    if (k > 0)
      temp[0][k - 1] = 1;
    if (k < N - 1)
      temp[0][k + 1] = 1;


    getFinalRow(finalRow, buttonOn);

    for (int i = 0; i < finalRow.size(); ++i)
      A.data[i][k] = finalRow[i];
    for (int i = 0; i < buttonOn.size(); ++i)
      A.data[i + N][k] = buttonOn[i];
  }

  Matrix<int> C = A.rightMergeMatrix(B);
  
  //int rankA = A.rank();
  int rankC = C.rank();

  bool ans = true;
  for (int i = 0; i < C.R; ++i)
  {
    bool empty = true;
    for (int j = 0; j < C.C - 1; ++j)
      if (C.data[i][j] > 0)
      {
        empty = false;
        break; 
      }
    if (empty && C.data[i][C.C - 1] > 0)
      ans = false;
  }

  if (ans)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--)
  {
    clear();
    deal();
  }

  return 0;
}

Lights Out CodeChef Solution in JAVA

//package codedef;

import java.io.File;

import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	 public static void main (String[] args) throws Exception{
		Main light = new Main();
		light.solve();
	}
	public void add(int [] count, int [] sta, int length)
	{
		for(int j=0;j<length;j++)
			count[ sta[j] ]++;
	}
	public void solve() throws FileNotFoundException
	{
		Scanner cin = new Scanner(System.in);
		//Scanner cin = new Scanner(new File("input.txt"));
		int T = cin.nextInt();
		for(int cas=0;cas<T;cas++)
		{
			int n = cin.nextInt();
			int k = cin.nextInt();
			int [][] lt = new int[n+2][n+2];
			int [][] lb = new int[n+2][n+2];
			int [][] sw = new int[n+2][n+2];
			for(int i=1;i<=n;i++)
			{
				String s = cin.next();
				for(int j=1;j<=n;j++)
				{
					if( s.charAt(j-1)=='0')
						lt[i][j] = 0;
					else
						lt[i][j] = 1;
				}
			}
			
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					sw[i][j] = 1;
			for(int b=0;b<k;b++)
			{
				int r = cin.nextInt();
				int c = cin.nextInt();
				sw[r][c] = 0;
			}
			int [][][] sta = new int [n+2][n+2][7] ;
			
			for(int j=1;j<=n;j++)
			{
				if( sw[1][j]==1 )
				{
					sta[1][j][j/30] = 1<<(j%30);
				}
			}
			boolean result = true;
			for(int i=2;i<=n+1 && result;i++)
			{
				for(int j=1;j<=n && result ;j++) //N*N*N;
				{
					lb[i][j] = lb[i-2][j] ^ lb[i-1][j-1] ^ lb[i-1][j] ^ lb[i-1][j+1] ^ lt[i-1][j];
					for(int s=0;s<7;s++)
					{
						sta[i][j][s] = sta[i-2][j][s] ^ sta[i-1][j-1][s] ^ sta[i-1][j][s] ^ sta[i-1][j+1][s];
					}
				}
				for(int j=1;j<=n;j++)
					if( sw[i][j]==0 )
					{
						int ss =0;
						for(;ss<7;ss++)
							if( sta[i][j][ss]!=0 )
								break;
						if( ss==7 )
						{
							if( lb[i][j]==1 )
								result = false;
						}
						else   //這個過程最多出現N次。
						{
							int last1 = sta[i][j][ss] & ( (sta[i][j][ss]-1)^sta[i][j][ss] );
							for(int l=i-1;l<=i;l++)
								for(k=1;k<=n;k++)   //2*N
								{
									if( l==i && k==j )
										continue;
									if( (sta[l][k][ss] & last1)==last1)
									{
										for(int w=0;w<7;w++)
											sta[l][k][w] ^= sta[i][j][w];
										lb[l][k] ^= lb[i][j];
									}
								}
							lb[i][j] = 0;
							for(int l=0;l<7;l++)
								sta[i][j][l] = 0;
						}
					}
			}
			if( result )
			{
				System.out.println("YES");
			}
			else
				System.out.println("NO");
		}
	}
}

Lights Out CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	tc := readNum(reader)

	var buf bytes.Buffer
	for tc > 0 {
		tc--
		n, k := readTwoNums(reader)
		s := make([]string, n)
		for i := 0; i < n; i++ {
			s[i] = readString(reader)
		}
		blocks := make([][]int, k)
		for i := 0; i < k; i++ {
			blocks[i] = readNNums(reader, 2)
		}
		res := solve(n, s, blocks)
		if res {
			buf.WriteString("YES\n")
		} else {
			buf.WriteString("NO\n")
		}
	}

	fmt.Print(buf.String())
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' {
			return s[:i]
		}
	}
	return s
}

func readNInt64s(reader *bufio.Reader, n int) []int64 {
	res := make([]int64, n)
	s, _ := reader.ReadBytes('\n')

	var pos int

	for i := 0; i < n; i++ {
		pos = readInt64(s, pos, &res[i]) + 1
	}

	return res
}

func readInt64(bytes []byte, from int, val *int64) int {
	i := from
	var sign int64 = 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	var tmp int64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int64(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')

	for len(bs) == 0 || bs[0] == '\n' || bs[0] == '\r' {
		bs, _ = reader.ReadBytes('\n')
	}

	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func solve(n int, s []string, blocks [][]int) bool {
	inv := make([][]bool, n)
	for i := 0; i < n; i++ {
		inv[i] = make([]bool, n)
	}
	for _, block := range blocks {
		a, b := block[0], block[1]
		a--
		b--
		inv[a][b] = true
	}

	equenow := make([]*BitSet, n)
	equepre := make([]*BitSet, n)
	equetmp := make([]*BitSet, n)
	var pro []*BitSet

	for i := 0; i < n; i++ {
		equenow[i] = NewBitSet(256)
		equenow[i].Set(i)

		equepre[i] = NewBitSet(256)
		equetmp[i] = NewBitSet(256)
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			equetmp[j].Copy(equenow[j])
			if i > 0 {
				equetmp[j].Xor(equepre[j])
			}
			if j > 0 {
				equetmp[j].Xor(equenow[j-1])
			}
			if j+1 < n {
				equetmp[j].Xor(equenow[j+1])
			}
			if s[i][j] == '1' {
				equetmp[j].Flip(n)
			}
			if inv[i][j] {
				tmp := NewBitSet(256)
				tmp.Copy(equenow[j])
				pro = append(pro, tmp)
			}
		}
		for j := 0; j < n; j++ {
			equepre[j].Copy(equenow[j])
			equenow[j].Copy(equetmp[j])
		}
	}

	for j := 0; j < n; j++ {
		pro = append(pro, equenow[j])
	}

	return check(pro, n)
}

func check(pro []*BitSet, n int) bool {
	for i := 0; i < n; i++ {
		for j := i + 1; j < len(pro); j++ {
			if !pro[j].IsSet(i) {
				continue
			}
			if !pro[i].IsSet(i) {
				pro[i], pro[j] = pro[j], pro[i]
			} else {
				pro[j].Xor(pro[i])
			}
		}
	}

	for i := 0; i < len(pro); i++ {
		allZero := true
		for j := 0; j < n; j++ {
			if pro[i].IsSet(j) {
				allZero = false
				break
			}
		}
		if allZero && pro[i].IsSet(n) {
			return false
		}
	}
	return true
}

type BitSet struct {
	arr []uint64
	sz  int
}

func NewBitSet(sz int) *BitSet {
	n := sz / 64
	arr := make([]uint64, n)
	return &BitSet{arr, sz}
}

func (this *BitSet) Set(p int) {
	x, y := p/64, p%64
	this.arr[x] |= (1 << uint64(y))
}

func (this *BitSet) Flip(p int) {
	x, y := p/64, p%64
	this.arr[x] ^= (1 << uint64(y))
}

func (this *BitSet) IsSet(p int) bool {
	x, y := p/64, p%64
	return (this.arr[x]>>uint64(y))&1 == 1
}

func (this *BitSet) Xor(that *BitSet) *BitSet {
	for i := 0; i < len(this.arr); i++ {
		this.arr[i] ^= that.arr[i]
	}
	return this
}

func (this *BitSet) Copy(that *BitSet) {
	copy(this.arr, that.arr)
}

Lights Out CodeChef Solution Review:

In our experience, we suggest you solve this Lights Out CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Lights Out CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Lights Out CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn