ADASCOOL - Editorial

general
, ,
1

PROBLEM LINK:

Div1
Div2
Practice

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 :slight_smile: (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 :slight_smile:

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

Setter

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;
}

Tester

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;
}

Editorialist

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 :smiley:

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 :smiley:

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.
4 Likes
2

1.when we will shuffle the matrix spirally,the row and column would get reduced by a factor of 2 in each operation.when both the row and column are odd a single element is always left out.

2.All the possibilities were covered due to the constraints. If diagonal shuffling is allowed then the answer would always be YES.

2 Likes
3

5.the ans is always YES because shuffling can be done row-wise.

1->2->3->4…->n->1

1 Like
4

  1. Correct.

  2. Can you prove the diagonal shuffling one? Are you talking of the circular shuffling problem I gave?

5

Good try - but theres a corner case!

N=1. For this, we cannot follow above logic :p. Will award you 10 karma for partially correct answer :slight_smile:

1 Like
6

Thanks for the insight.Next time I will do better.

1 Like
7

The tester’s solution doesn’t display properly. Also, clicking on Setter, Tester or Editorialist redirects to campus.codechef.com, instead of their profile page.

8

Why this is not working?

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args)
	{
		// your code goes here
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases -- >0)
        {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            System.out.println(solve(a,b) ? "Yes" : "No");
        }
        scanner.close();
    }

    static boolean solve(int a, int b) {
        return a%2==0 || b%2==0;
    }
}
9

Hey, you need to add import java.util.Scanner; above your code, otherwise it is causing a compilation error.
Also you output string does not matches the specified output string int the problem statement. The problem requires you to print YES/NO strings with each letter capitalised.