Solution for CONSADD | March Long Challenge 2021

CONSADD.cpp

#include<bits/stdc++.h>

using namespace std;

#define ll long long

void NO() { cout << "No\n"; return; }
void YES() { cout << "Yes\n"; return; }

int r, c; ll k;
#define N 1002

ll int a[N][N];
ll int cm[N][N];


bool check(ll int v){
	
	// sum for CM(i, j) * D(i, j)
	ll int s = 0;
	
	// this is sum of coefficients to account for shifting
	ll int cs = 0;
	for(int i = 0 ; i < r; i ++){
		for(int j = 0; j < c; j ++){
			s += (a[i][j] * cm[i%k][j%k]); 
			cs += cm[i%k][j%k];
		}
	}
	
	// extra value generated after shifting
	ll int extra = v*cs;
		
	// true only if s only has the extra value generated due to shifting
	return s == extra;
}


void solve(){
	cin >> r >> c >> k;
	
	for(int i = 0 ; i < r; i ++){
		for(int j = 0; j < c; j ++){
			cin >> a[i][j];
		}
	}
	
	ll int least = INT_MAX;
	for(int i = 0 ; i < r; i ++){
		for(int j = 0; j < c; j ++){
			ll int y;
			cin >> y; 
			a[i][j] = y - a[i][j];	
			least = min(least, a[i][j]);
		}
	}
	
	ll int shift;
	if(least < 1) {
		shift = 1 - least;
	} else {
		shift  = 0;
	}
	
	for(int i = 0 ; i < r; i ++){
		for(int j = 0; j < c; j ++){
			a[i][j] += shift;
		}
	}
	
	for(int i = 0; i < k; i ++)
		for(int j = 0; j < k; j ++) 
	 		cm[i][j] = 0;
	 		
	 		
	// building CM starts
	for(int i = 0; i < k - 1; i ++){
		ll ii = i+1;
		cm[i][i] = ii*ii;
		cm[i][k-1] -= (ii*ii);
		cm[k-1][i] -= (ii*ii);
	}
	
	for(int i = 0 ; i < k - 1; i ++){
		for(int j = 0; j < i; j ++){
			ll jj = j +1;
			ll ii = i +1;
			ll prod = jj * ii; 
			cm[i][j] = prod;
			cm[j][i] = prod;
			
			// balancing current row and column with last cell in the row and column
			cm[i][k-1] -= (prod);
			cm[k-1][j] -= (prod);
			cm[j][k-1] -= (prod);
			cm[k-1][i] -= (prod);
		}
	}

	// balancing last row / column with CM(K-1, K-1)	
	for(int i = 0; i < k -1; i ++){
		cm[k-1][k-1] -= cm[i][k-1]; 
	}
	
	if(check(shift)) return YES();
	return NO();
	
}

int main(){
	int t;
	cin >> t;
	while(t--) solve();
}