PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Basic implementation
PROBLEM:
Given two square grids A and B with N rows and M columns each, A representing the typical signature and B representing the actual signature. Each signature grid contains ‘1’ to represent black cells while ‘0’ to represent the white cell.
Two signatures are considered the same if it is possible to choose (possibly negative) integers dr and dc such that for each 1 \le i \le N and 1 \le j \le M, A_{i, j} = B_{i + dr, j + dc}. Here, if B_{i + dr, j + dc} does not correspond to a valid cell, it is considered to be ‘0’.
To compare the signatures, the colors of zero or more cells must be flipped in such a way that the signatures become the same (each flipped cell may be in any matrix). The error in the client’s current signature is the minimum number of cells whose colors must be flipped. Find the error in the signature.
QUICK EXPLANATION
- We can try all possible values of dr and dc realizing that checking -N \leq dr \leq N and -M \leq dc \leq M is always sufficient.
- For checking a specific pair (dr, dc), we can iterate over all cells (i, j) in A and find the error for the given pair. If (i+dr, j+dc) doesn’t lie inside A, it is considered a white cell and compared with A_{i, j}.
- The minimum error over all pairs is the required answer.
EXPLANATION
This problem is all about trying all possible pairs of (dr, dc) and finding the error for each pair and taking a minimum. But what’s the range over the values of dr and dc
We can see, if dr > N, then all cells of B have moved outside A. Similarly, if dr < -N, then also all cells of B have moved outside A, so trying any value of dr smaller than -N also doesn’t gain anything. Hence, bounds -N \leq dr \leq N is imposed on dr. We can similarly bound -M \leq dc \leq M
Now, let’s suppose we are checking shift pair (x, y). We need to calculate the error with the current shift.
We can iterate over all positions A_{i, j} and compare it with B_{i+dr, j+dc} and wherever we find different values, we increase error by one. In case B_{i+dr, j+dc} is not a valid position in B, assume it to be ‘0’
We can find error for each shift and print the minimum. Refer implementations if still unclear.
TIME COMPLEXITY
The time complexity is O((N*M)^2) per test case.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,m;
int A[55][55];
int B[55][55];
int main(){
//freopen("00.txt","r",stdin);
//freopen("00o.txt","w",stdout);
T=readIntLn(1,50);
while(T--){
n=readIntSp(1,30);
m=readIntLn(1,30);
for(int i=0;i<n;i++){
string s = readStringLn(m,m);
for(int j=0;j<m;j++){
assert(s[j] =='0' || s[j] == '1');
A[i][j] = s[j]-'0';
}
}
for(int i=0;i<n;i++){
string s = readStringLn(m,m);
for(int j=0;j<m;j++){
assert(s[j] =='0' || s[j] == '1');
B[i][j] = s[j]-'0';
}
}
int sol=1<<30;
for(int si=-n;si<=n;si++){
for(int sj=-m;sj<=m;sj++){
int cur=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i+si < 0 || i+si >=n || j+sj <0 || j+sj >=m){
cur += A[i][j];
} else {
cur += A[i][j] != B[i+si][j+sj];
}
}
}
sol =min(sol,cur);
}
}
cout<<sol<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
string s[123],t[123];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int tt;
cin>>tt;
while(tt--){
int n,m;
cin>>n>>m;
int i,j,dr,dc;
rep(i,n){
cin>>s[i];
}
rep(i,n){
cin>>t[i];
}
int val,cnt=0,mini=inf,val1;
f(dr,-n-1,n+2){
f(dc,-m-1,m+2){
cnt=0;
rep(i,n){
rep(j,m){
if(i+dr<0 || i+dr>=n || j+dc<0 || j+dc>=m){
val=0;
}
else{
val=t[i+dr][j+dc]-'0';
}
val1=s[i][j]-'0';
//cout<<val1<<" "<<val<<endl;
if(val1!=val){
cnt++;
}
}
}
mini=min(mini,cnt);
}
}
cout<<mini<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class SIGNTURE{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), m = ni();
boolean[][] a = new boolean[n][m], b = new boolean[n][m];
for(int i = 0; i< n; i++){
String s = n();
for(int j = 0; j< m; j++)a[i][j] = s.charAt(j) == '1';
}
for(int i = 0; i< n; i++){
String s = n();
for(int j = 0; j< m; j++)b[i][j] = s.charAt(j) == '1';
}
int ans = n*m;
for(int dr = -n; dr <= n; dr++)
for(int dc = -m; dc <= m; dc++){
int cnt = 0;
for(int i = 0; i< n; i++)
for(int j = 0; j< m; j++)
if(i+dr < 0 || i+dr >= n || j+dc < 0 || j+dc >= m){if(a[i][j])cnt++;}
else if(a[i][j] != b[i+dr][j+dc])cnt++;
ans = Math.min(ans, cnt);
}
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new SIGNTURE().run();
}
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. Suggestions are welcomed as always. 