PROBLEM LINK:
Setter- Alei Reyes
Tester- Pranjal Jain
Editorialist- Abhishek Pandey
DIFFICULTY:
Simple
PRE-REQUISITES:
Logic reasoning, Conditionals
PROBLEM:
You are given a N*M matrix where every element can be swapped by its direct neighbour (up, down, left and right). Is it possible to swap them such that no element is at its original place?
QUICK-EXPLANATION:
Key to AC- Realize that answer is not possible only if N and M both are odd.
We can prove that, if at least one out of N or M is even, then an answer exists (Eg- say, if number of columns are even, then swap elements at column 1 with those at column 2, column 3's elements with column 4's etc.). However, if both N and M are odd, there will be at least 1 student who cannot be fitted anywhere, making the answer as NO.
The implementation for iterating over all cells, checking the condition and updating answer is below-
Click to view
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
if(max(abs(i-r),abs(j-c))<=k)ans++;
}
}
EXPLANATION:
Since this is one of the simpler problems, the editorial will be written in a way as such, how you can think during contest to have solved this problem. We will start with analyzing trivial cases, and then expand them to complex ones , i.e., typical divide and conquer 
(Divide the problem into cases which are easy to conquer :p)
1. Trivial cases-
Lets forget that we have a matrix. Lets say that we only have 1 row and M columns. Lets analyze this scenario.
- If M is even, then we can swap students at column 1 and 2 with each other, elements at column 3 and 4 with each other and so on. Since M is even, every student has been swapped.
- If M is odd, you will find that an answer cannot exist.
Lets analyze case of odd M more deeply. Say, we take example of M=3. Say, the initial seating arrangement is like 1,2,3. We need to make sure no element is at its place. But notice that 1 and 3 both have only 1 option, i.e. 2's table. But only 1 student per table is allowed, hence no answer.
Lets take another, M=5 now. We place 1 at 2's place to get .1... (supposing we are yet to seat rest of them). Now, if we seat 2 at 1's place, we get a case similar to M=3 for 3,4,5 and answer wont be possible. But, if we put 2 at 3's position, it wont be possible to fill 1's place and hence 1 student will still be left.
Nice!! We can extend this logic to claim that if there is only 1 row, no answer exists for odd M. But, whats next?
2. Extending the Answer for 2-D Matrix-
Say now we have N rows. Lets again make cases-
- If M is even, we can follow the pattern discussed earlier for every row and satisfy each row independently. Hence, answer exists.
- If M is odd - Can we claim that an answer wont exist? Or will we have to take N in account??
Hmm, the M being odd case is not so simple. Lets break it down further-
- N is even and M is odd - Recall that we can swap up and down as well!! Hence, lets solve the problem independently for each column, by swapping students up and down. (An alternate way to look at it is, just rotate the matrix by 90 degrees such that rows become columns and vice versa. Now apply our previous procedure.)
- If N is odd and M is odd - In our earlier analysis, when N was 1, the issues we faced were that, either the last element could not go anywhere, or the seat of first element was vacant. We can prove that the answer for such a case will not exist. The proof is below-
Lets use a chess board proof to prove above claim
Label any cell white. Its neighbors must be black. If N and M are both odd, then there are a total of odd number of cells, which means that number of white cells is NOT equal to number of white cells.
Ultimately, the operation asks us to place a white cell to its neighboring black one, and vice versa. But if number of white and black cells are not equal, we can see that there will always be 1 student left out in every configuration. This completes the proof for non-existence of answer for odd M and odd N.
SOLUTION
Click to view
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
string rword(char nxt){
string ans="";
while(true){
char ch=getchar();
if(ch==nxt)break;
ans.push_back(ch);
}
return ans;
}
int main(){
// freopen("secret/0.in","r",stdin);
// freopen("secret/0.out","w",stdout);
int t=rint('\n');
assert(1<=t&&t<=5000);
while(t--){
int n=rint(' ');
int m=rint('\n');
assert(2<=n&&n<=50);
assert(2<=m&&m<=50);
if((n*m)%2==0)puts("YES");
else puts("NO");
}
assert(getchar()==EOF);
return 0;
}
Click to view
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(char ch) {
return string("'")+ch+string("'");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class InputIterator>
string to_string (InputIterator first, InputIterator last) {
bool start = true;
string res = "{";
while (first!=last) {
if (!start) {
res += ", ";
}
start = false;
res += to_string(*first);
++first;
}
res += "}";
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x){
input>>x.F>>x.S;
return input;
}
template <typename A>
istream& operator>>(istream& input,vector<A>& x){
for(auto& i:x)
input>>i;
return input;
}
#ifdef PRINTERS
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
void solve(){
int N,M;
cin>>N>>M;
cout<<(N%2 and M%2?"NO\n":"YES\n");
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
Click to view
/*
*
********************************************************************************************
* AUTHOR : Vijju123 *
* Language: C++14 *
* Purpose: - *
* IDE used: Codechef IDE. *
********************************************************************************************
*
Comments will be included in practice problems if it helps ^^
*/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int mod=pow(10,9)+7;
int fastExpo(long long a,long long n, int mod)
{
a%=mod;
if(n==2)return a*a%mod;
if(n==1)return a;
if(n&1)return a*fastExpo(fastExpo(a,n>>1,mod),2,mod)%mod;
else return fastExpo(fastExpo(a,n>>1,mod),2,mod);
}
inline void add(vector<vector<int> > &a,vector<vector<int> > &b,int mod)
{
for(int i=0;i<a.size();i++)for(int j=0;j<a[0].size();j++)b[i][j]=(b[i][j]+a[i][j])%mod;
}
void multiply(vector<vector<int> > &a, vector<vector<int> > &b,int mod,vector<vector<int> > &temp)
{
assert(a[0].size()==b.size());
int i,j;
for(i=0;i<a.size();i++)
{
for(j=0;j<b[0].size();j++)
{
temp[i][j]=0;
for(int p=0;p<a[0].size();p++)
{
temp[i][j]=(temp[i][j]+1LL*a[i][p]*b[p][j])%mod;
}
}
}
}
void MatExpo(vector<vector<int> > &arr,int power,int mod)
{
int i,j,k;
vector<vector<int> >temp,temp2,temp3;
vector<int> init(arr[0].size());
for(i=0;i<arr.size();i++){temp.push_back(init);}
temp3=temp;
temp2=temp;
for(i=0;i<arr.size();i++)temp3[i][i]=1;
while(power>0)
{
if(power&1)
{
multiply(arr,temp3,mod,temp);
swap(temp3,temp);
}
multiply(arr,arr,mod,temp2);
swap(arr,temp2);
power>>=1;
}
swap(arr,temp3);
}
vector<int> primes;
int isComposite[1000001]={1,1};
void sieve()
{
int i,j;
for(i=2;i<=1000000;i++)
{
if(!isComposite[i])
{
primes.push_back(i);
isComposite[i]=i;
}
for(j=0;j<primes.size() and i*primes[j]<=1000000;j++)
{
isComposite[primes[j]*i]=i;
if(i%primes[j]==0)break;
}
}
}
int main() {
// your code goes here
#ifdef JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
srand(time(NULL));
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int t;
cin>>t;
int n,m;
while(t--)
{
cin>>n>>m;
if(n%2==1 and m%2==1)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
Time Complexity=O(1)
Space Complexity=O(1)
CHEF VIJJU’S CORNER 
1. Prove that filling the matrix spirally wont work. (Hint: The last element becomes the middle element).
2. Prove or disprove that the analysis we did above is exhaustive. Did we leave out any possibility? Or did we cover them all due to the constraints of swapping only with neighbours?
3. If N and M are both \leq 50, is the value of T\leq 5000 reasonable? Can a smaller value suffice? Why/Why not?
4. Notice the spelling of School in Problem Code
5. Solve this alternate version of problem-
The problem is same, except that the rows are now, circularly arranged. Meaning, Row 1 and Row N are adjacent. Give a brief algorithm to solve the problem under this new constraint.
Hints-
Click to view
Is the answer possible always?
Click to view
Take care of case when we have only 1 row!!
6. Similar problems-
- Trace - Based on analysis of 2-D matrices.