EVENM - Editorial

PROBLEM LINK:

Contest Link

Author:
Tester: Felipe Mota
Editorialist: Rajarshi Basu

DIFFICULTY:

Simple

PREREQUISITES:

Implementation, logic

PROBLEM:

Generate an N \times N matrix such that:

  1. Each cell contains a number from 1 \dots N^2.
  2. No two cells have the same value.
  3. For each square submatrix containing cells in rows r through r+a
    and in columns c through c+a (inclusive) for some valid integers r, c and a≥0:
    • M_{r,c}+M_{r+a,c+a} is even
    • M_{r,c+a}+M_{r+a,c} is even

QUICK EXPLANATION:

Do this Quickly

Alternatingly place odd and even numbers in a checkerboard pattern.

EXPLANATION

Some Advice

It’s always a good idea to draw pictures in constructive problems, even if a 3x3 matrix.

Observation 1

The exact numbers don’t matter so much as their parity, ie, whether it’s odd or even.

Observation 2

When we say the sum of two things is numbers is even, we mean that their parity is the same.

Observation 3

For the following sequence of claims, just consider 2 \times 2 submatrices.

  • Let us just fix M_{1,1} = 1 (because why not).
  • This means that M_{2,2} is also odd.
  • This means that M_{3,3} is also odd
  • We can extend this train of thought and conclude M_{i,i} is also odd \forall i, 1\leq i \leq N.
Observation 4

Let us say the parity of M_{i,j} is odd. Then the parity of M_{i+1,j+1} , M_{i+1,j-1},M_{i-1,j+1},M_{i-1,j-1}, also has to be odd.

Observation 5

The above observations together imply a kind of checkerboard pattern, where all black cells of the checkerboard must be of the same parity, and all white cells also must be of the same parity.

Full Solution

Fill the matrix M in a checkerboard pattern where all black cells have an odd integer and white cells have an even integer (or vice versa). See Setter’s code for implementation. Since we just iterate over all the integers and place them, complexity is simply O(N^2).

SOLUTIONS:

Setter's Code

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll a[1005][1005];
int main()
{
    
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        
        ll j = 1;
        
        for(ll i=0;i<n;i++)
        {
            if (i%2==0)
            for(ll k=0;k<n;k++)
                a[i][k]=j++;
            else
            {
                j+=n-1;
                for(ll k=0;k<n;k++)
                a[i][k]=j--;
                j=a[i][0]+1;
            }
        
        }
 
        for(ll i=0;i<n;i++)
        {
            for(ll j=0;j<n;j++)
                cout<<a[i][j]<<" ";
            cout<<"\n";
        }
    }
}   


Tester's Code
t = int(raw_input())
 
while t > 0:
    n = int(raw_input())
    res = [[0] * n for i in xrange(n)]
    at = [[] for i in xrange(n + n)]
    for i in xrange(n):
        for j in xrange(n):
            at[i + j].append((i, j))
    ptr = 1
    for i in xrange(n + n):
        for pos in at[i]:
            if (pos[0] + pos[1]) % 2 == 0:
                res[pos[0]][pos[1]] = ptr
                ptr += 2
    ptr = 2
    for i in xrange(n + n):
        for pos in at[i]:
            if (pos[0] + pos[1]) % 2 != 0:
                res[pos[0]][pos[1]] = ptr
                ptr += 2
    for i in xrange(n):
        print " ".join(map(str, res[i]))
    t -= 1 

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

3 Likes

This can be solved by simply printing Spiral Matrix :slight_smile:
Here is my solution - https://www.codechef.com/viewsolution/33903045

1 Like

Video Editorial>>>

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(n%2==0 && i%2==1)cout << i*n + n - j;
                else cout << i*n + j + 1;
                cout << (j==n-1 ? '\n' : ' ');
            }
        }
    }
}
1 Like

June long challenge editorial beginner-friendly video explanation with animation and code

Delicious cake (CONTAIN) : https://youtu.be/tXD2yEVA0pM
Tom and jerry (EOEO) : https://youtu.be/ZWI5n0Ogir0
Even matrix (EVENM) : https://youtu.be/KA8WoO7jCg8

Can anyone help me out on why this code is getting TLE ?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Codechef {
	private static BufferedReader br;

	public static void main(String args[]) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while(t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			int odd = 1, even = 2;
			for(int i = 0; i < n; ++i) {
				for(int j = 0; j < n; ++j) {
					if(((i + j)&1) == 0) {
						System.out.print(even + " ");
						even += 2;
					}else {
						System.out.print(odd + " ");
						odd += 2;
					}
				}
				System.out.println();
			}
		}
	}
}

because you have three nested loops…the time complexity is seriously high
OPTIMIZE YOUR CODE

yes I did the same

video Explanation>>>>

1 Like

One for test cases. Two for printing 2D matrix. I think these are bound to be there.

i did the same also

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

/solution/
ll t;
cin>>t;
while (t–)
{
ll n;
cin>>n;

//   for(int i=0;i<n;i++){
//         for(int j=0;j<n;j++){
//             if(n%2==0 && i%2==1)
//             {
//                 cout << i*n + n - j<<" ";
//             }
//             else 
//             {
//                 cout << i*n + j + 1<<" ";
//             }
//         }
//         cout<<el;
//     }  

int a=1,b=2;
for(int i =0;i<n;i++){
    for(int j =0;j<n;j++){
        if((i+j)%2==0){
            cout<<a<<" ";
            a+=2;
        }
        else{
            cout<<b<<" ";
            b+=2;
        }
    }
    cout<<el;
}

}

return 0;
}

what is “a” stands for please tell me
i got confused only because of this…:pensive: