# PROBLEM LINK:
Contest
Practice
#DIFFICULTY
EASY
# PROBLEM:
You are given a NxN matrix and each cell of the matrix is assigned with one the three colours A,B,C. You need find total no. of GoodPairs for each pair of colours [A-B] , [B-C] and [C-A].
Consider if a pair of cells is removed from the square matrix and then if we are able to cover remaining cells of the matrix by a 1x2 tile placing it either horizontally or verticallly then the pair of cell removed is called GoodPair.
# QUICK EXPLANATION:
The given square matrix can be visualised as a NxN chessboard with cells of black and white colour.
Initially for N being odd answer is zero as remaining N*N-2 cells will be odd which can’t be covered by 1x2 tile in anyway.
For N being even we can observe that whenever we place a tile of 1x2
(horizontally or vertically) on chessboard it always cover a black cell and a white cell. There is no possibility that a tile covers two black or two white cells at a time , So we can say that if one pair of cell with opposite colours is removed then it is always possible to cover the remaining cells of chessboard by 1x2 tiles , which will cover an equal numbers of squares of each colour(black and white).
# EXPLANATION:
For solving above problem consider matrix as chessboard ,
so if address of cell is (i,j) then we can consider cells with (i+j) being odd as black cells and cells with (i+j) being even as white cells(vice versa).
Now for finding all pairs of colour [A-B], [B-C] and [A-C] we can count frequency for each colour(A,B,C) cells with black and white colour and then we can simply find total no. of pairs.
#IDEA OF ALGORITHM
We can iterate for two nested loops and count the frequency of all three coloured cells with black and white colour i.e. cells at even sum indices and at odd sum indices.
so total three types of pair [A-B],[B-C],[A-C] which again have two types of pairs each
A-black B-white
A-white B-black
A-black C-white
A-white C-black
C-black B-white
C-white B-black
# SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define MOD 1000000007
#define dd double
#define vi vector<int>
#define vll vector<ll>
#define forr(i,n) for(ll i=0;i<n;i++)
#define revf(i,n) for(ll i=n-1;i>=0;i--)
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep1(i,b) for(ll i=1;i<=b;i++)
#define inp(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define outp(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" "
#define outp1(a,n) for(ll i=1;i<n;i++)cout<<a[i]<<" "
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (((a)*(b))/gcd((a),(b)))
#define pb push_back
#define mp make_pair
#define mem(x,n) memset(x,n,sizeof(x))
#define BINSC binary_search
#define BITOUT __builtin_popcount
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define test ll t; cin>>t; while(t--)
#define cn cout<<"\n";
int main()
{
fast
test
{
ll n;
cin>>n;
ll ae=0,ao=0,be=0,bo=0,ce=0,co=0;
char inp;
forr(i,n)
{
forr(j,n)
{
cin>>inp;
if(inp=='A')
{
if((i+j)%2==0)
ae++; // A colour cells with indices sum even
else
ao++; // A colour cells with indices sum odd
}
else if(inp=='B')
{
if((i+j)%2==0)
be++; // B colour cells with indices sum even
else
bo++; // B colour cells with indices sum odd
}
else
{
if((i+j)%2==0)
ce++; // C colour cells with indices sum even
else
co++; // C colour cells with indices sum odd
}
}
}
if(n%2!=0) // ans=0 for odd size
cout<<0;
else
{
// ae*bo [A-B] coloured pair with A at even posn and B at odd posn
// be*ao [A-B] coloured pair with B at even posn and A at odd posn
// ae*co [A-C] coloured pair with A at even posn and C at odd posn
// co*ao [A-C] coloured pair with C at even posn and A at odd posn
// be*co [B-C] coloured pair with B at even posn and C at odd posn
// ce*bo [B-C] coloured pair with C at even posn and B at odd posn
// for total pairs add count of all individual pairs.
ll out=ae*bo+ao*be+be*co+bo*ce+ae*co+ao*ce;
cout<<out;
}
cn
}
}