PROBLEM LINK: Chess and Checkers
Author: prathakgarg
Tester: agarwal_keshav, dragno99
Editorialist: chitranshi351
DIFFICULTY:
MEDIUM-HARD
PROBLEM:
Given a matrix of size n , perform two subtasks
- first find the square submatrix having the maximum xor value of n*p where p represents elements on its south east diagonal and n represents length of side of submatrix(digaonal moving from top left to bottom right)
- In this submatrix, find the number of paths possible to move from one end of diagonal of this submatrix to the other end without crossing the diagonal
Prerequisites:
- knowledge of dynamic programming
- basic understanding of permutation and combination
#QUICK EXPLANATION
This problem firstly asks us to implement a 3D dynamic programming approach to find out thhe submatrix. We create a dp[][][] matrix which stores the values of xor of n*p of all possible square submatrices. Then we apply permutation and combination to find the number of required paths. Take care to eliminate those paths which involve crossing the diagonal.
#EXPLANATION
In a matrix, there can be (2 x n) -1 possible diagonals( one main diagonal, n-1 diagonals above it and n-1 diagonals below it). We create a dp matrix dp[i][j][k] where i indicates the diagonal we are taking, j indicates the length of the portion of this diagonal we are considering and k indicates the length of side of submatrix we have chosen. So basically dp[i][j][k] gives us the value of xor of elements of diagonal indexed i of length j multiplied with k. We start by indexing all possible diagonals with with n-1+(i-j) where (i,j) are the coordinates of starting element of that diagonal. We go on to create this dp matrix in such a way that dp[i][j][k] = k*a[x][y] xor dp[i][j-1][k].
After creating this dp matrix, we move ahead to find the maximum xor value in this dp matrix to get the best square submatrix. Now that we have found the submatrix, we move on to our next step. The total number of monotonic paths in the lattice size of n x n is given by C_{n}^{2n} .Now we count the number of monotonic paths which cross the main diagonal. Consider such paths crossing the main diagonal and find the first edge in it which is above the diagonal. Reflect the path about the diagonal all the way, going after this edge. The result is always a monotonic path in the grid (n-1) x (n+1). On the other hand, any monotonic path in the lattice (n-1) x (n+1) must intersect the diagonal. Hence, we enumerated all monotonic paths crossing the main diagonal in the lattice n x n. The number of monotonic paths in the lattice (n-1) x (n+1) are C_{n-1}^{2n} . Let us call such paths as “bad” paths. As a result, to obtain the number of monotonic paths which do not cross the main diagonal, we subtract the above “bad” paths, and the optimal number of path is equal to C_{n}^{2n} - C_{n-1}^{2n}.
Time complexity: O(N^3)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define nl cout<<"\n";
#define fix(f,n) cout<<fixed<<setprecision(n)<<f
const int mod = 1e9+7;
ll gcd(ll a,ll b){ return a?gcd(b%a,a):b; }
ll minv(ll a,ll b){ return a<b?a:b;}
ll maxv(ll a,ll b){ return a>b?a:b;}
ll dp[202][102][102];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll a[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
// total diagonal = 2n-1
// max length of diagonal = n
for(int i=0;i<(2*n-1);i++){
for(int j=0;j<=n;j++) dp[i][0][j] = 0;
}
// diagonal index is (n-1 + i) if i is the difference of row and column of starting index of that diagonal
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
// index of the diagonal in which a[i][j] belongs to
ll index = (i - j) + (n-1);
ll start_row_index = maxv(0,i-j);
// length of current diagonal
ll l = i - start_row_index + 1;
for(int k=1;k<=n;k++){
dp[index][l][k] = k*a[i][j] xor dp[index][l-1][k];
}
}
}
ll size = 0,mx = -1;
// size is size of final square submatrix
// mx is max xor
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int index = i - j + (n-1);
int start_row_index = maxv(0,i-j);
// length of current diagonal
int l = i - start_row_index;
// max length of sqaure matrix with top left index (i,j)
int max_l = minv(n-i,n-j);
for(int k=1;k<=max_l;k++){
ll new_l = k + l;
ll val = dp[index][new_l][k] xor dp[index][l][k];
if(val > mx){
mx = val;size = k;
}else if(val==mx && k>size){
size = k;
}
}
}
}
// increasing size bcoz player can move only on the boundary of choose square
size = size + 1;
ll ways[size][size];
memset(ways,0,sizeof(ways));
for(int i=0;i<size;i++){
ways[0][i] = 1;
}
for(int i=1;i<size;i++){
for(int j=i;j<size;j++){
ways[i][j] = (ways[i-1][j] + ((j==i)?0:ways[i][j-1]))%mod;
}
}
ll ans = (2*ways[size-1][size-1])%mod;
cout<<mx<<" "<<ans<<"\n";
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define nl cout<<"\n";
#define fix(f,n) cout<<fixed<<setprecision(n)<<f
const int mod = 1e9+7;
template<typename ...T>
void debug(T&&... args){ ((cerr << args << " "), ...);cerr<<"\n";}
ll gcd(ll a,ll b){ return a?gcd(b%a,a):b; }
ll minv(ll a,ll b){ return a<b?a:b;}
ll maxv(ll a,ll b){ return a>b?a:b;}
void swapv(ll &a,ll &b){a=a+b;b=a-b;a=a-b;}
ll power(ll a, ll b, ll m=mod){
if(a==0 || b==1) return a;
if(b==0) return 1;ll ans=1;
while(b>=1){ if(b&1){b--;ans = (ans*a) % m;}a = (a*a)% m;b = b>>1;}return ans;
}
ll logv(ll x){ll ans =-1;while(x){x = x>>1;ans++;}return ans;}
ll inv(ll a,ll m){return power(a,m-2,m);}
int fact(int n);
int nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
int fact(int n)
{
int res = 1;
for (int i = 2; i <= n; i++)
res = res * i;
return res;
}
ll dp[202][102][102];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt","w",stderr);
#endif
ll t=1;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll a[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
// total diagonal = 2n-1
// max length of diagonal = n
for(int i=0;i<(2*n-1);i++){
for(int j=0;j<=n;j++) dp[i][0][j] = 0;
}
// diagonal index is (n-1 + i) if i is the difference of row and column of starting index of that diagonal
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
// index of the diagonal in which a[i][j] belongs to
ll index = (i - j) + (n-1);
ll start_row_index = maxv(0,i-j);
// length of current diagonal
ll l = i - start_row_index + 1;
for(int k=1;k<=n;k++){
dp[index][l][k] = k*a[i][j] xor dp[index][l-1][k];
}
}
}
ll size = 0,mx = -1;
// size is size of final square submatrix
// mx is max xor
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int index = i - j + (n-1);
int start_row_index = maxv(0,i-j);
// length of current diagonal
int l = i - start_row_index;
// max length of sqaure matrix with top left index (i,j)
int max_l = minv(n-i,n-j);
for(int k=1;k<=max_l;k++){
ll new_l = k + l;
ll val = dp[index][new_l][k] xor dp[index][l][k];
if(val > mx){
mx = val;size = k;
}else if(val==mx && k>size){
size = k;
}
}
}
}
// increasing size bcoz player can move only on the boundary of choose square
size = size + 1;
ll ways[size][size];
memset(ways,0,sizeof(ways));
for(int i=0;i<size;i++){
ways[0][i] = 1;
}
for(int i=1;i<size;i++){
for(int j=i;j<size;j++){
ways[i][j] = (ways[i-1][j] + ((j==i)?0:ways[i][j-1]))%mod;
}
}
//total number of monotonic paths in the lattice size of nxn is 2nCn
//number of monotonic paths which cross the main diagonal is 2nC(n-1)
// int W = nCr(2*size, size) - nCr(2*size, size-1);
ll ans = (2*ways[size-1][size-1])%mod;
cout<<mx<<" "<<ans<<"\n";
}
return 0;
}
Java Code
import java.util.*;
public class Main{
static int dp[][][] = new int[220][120][120];
static int mod = (int)1e9+7;
public static void main(String[]args){
Scanner at = new Scanner(System.in);
int t = at.nextInt();
while(t-->0){
int n = at.nextInt();
int[][]a = new int[n+10][n+10];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][j] = at.nextInt();
}
}
for(int i = 0;i<(2*n)-1;i++){
for(int j = 0;j<=n;j++){
dp[i][0][j] = 0;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int index = (i - j) + (n-1);
int start_row_index = Math.max(0,i-j);
// length of current diagonal
int l = i - start_row_index + 1;
for(int k=1;k<=n;k++){
dp[index][l][k] = k*a[i][j]^dp[index][l-1][k];
}
}
}
int size = 0;
int mx = -1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int index = i - j + (n-1);
int start_row_index = Math.max(0,i-j);
// length of current diagonal
int l = i - start_row_index;
// max length of sqaure matrix with top left index (i,j)
int max_l = Math.min(n-i,n-j);
for(int k=1;k<=max_l;k++){
int new_l = k + l;
int val = dp[index][new_l][k]^dp[index][l][k];
if(val > mx){
mx = val;size = k;
}else if(val==mx && k>size){
size = k;
}
}
}
}
size = size + 1;
int temp = size;
int ways[][] = new int[size+50][size+50];
for(int i = 0;i<size;i++){
Arrays.fill(ways[i],0);
}
// System.out.println("YES "+size);
for(int i=0;i<size;i++){
ways[0][i] = 1;
// System.out.println("YES "+ i);
}
for(int i=1;i<size;i++){
for(int j=i;j<size;j++){
ways[i][j] = (ways[i-1][j] + ((j==i)?0:ways[i][j-1]))%mod;
}
}
long ans = (2*(long)ways[temp-1][temp-1])%mod;
System.out.println(mx+" "+ans);
}
}
}
Python Code
def maxv(a,b):
if a>b:
return a
return b
def minv(a,b):
if a<b:
return a
return b
def ThreeD(a, b, c):
lst = [[ [0 for col in range(c)] for col in range(b)] for row in range(a)]
return lst
dp = ThreeD(202,102,102)
mod = (10**9) + 7
def main():
t = int(input())
while(t>0):
t -= 1
n = int(input())
a = []
for x in range(n):
a.append([int(y) for y in input().split()])
for i in range((2*n)-1):
for j in range(n+1):
dp[i][0][j]=0
for i in range(n):
for j in range(n):
index = (i-j) + (n-1)
start_row_index = maxv(0,i-j)
l = i - start_row_index + 1
for k in range(1,n+1):
dp[index][l][k] = (k*a[i][j]) ^ (dp[index][l-1][k])
size = 0
mx = -1
for i in range(n):
for j in range(n):
index = (i-j) + (n-1)
start_row_index = maxv(0,i-j)
l = i - start_row_index
max_l = minv(n-i,n-j)
for k in range(1,max_l+1):
new_l = k + l
val = dp[index][new_l][k] ^ dp[index][l][k]
if(val>mx):
mx = val
size = k
elif val==mx and k>size:
size = k
size+=1
ways = [[0]*size]*size
for i in range(size):
ways[0][i] = 1
for i in range(1,size):
for j in range(i,size):
x = 0
if i!=j:
x = ways[i][j-1]
ways[i][j] = (ways[i-1][j] + x)%mod
ans = (2*ways[size-1][size-1])%mod
print(mx,ans)
main()