PPATTERN - Editorial

PROBLEM LINK:

Practice
Contest

Author: AmirReza PoorAkhavan
Tester: Danial Erfanian
Editorialist: Michael Nematollahi

PREREQUISITES:

NONE

PROBLEM:

You are given a number N and you are asked to output an N \times N matrix consisting of numbers from 1 to N \times N according to a given pattern.

EXPLANATION:

To solve this problem, let’s first find out what the pattern really is.

By looking at the given matrix, we realize that each anti-diagonal of the matrix consists of some consecutive numbers written from top to bottom. the first anti-diagonal is composed of only number 1, the second is composed of numbers 2 and 3, and the following anti-diagonals are filled similarly.

So it turns out the task is fairly simple. We have to start from the first anti-diagonal, go through all of those diagonals one by one and write the numbers from top to bottom starting from 1.

So all that’s left is to go through anti-diagonals one by one efficiently. Let’s enumerate the rows of the matrix from top to bottom starting from 0. Similarly, let’s enumerate the columns from left to right starting from 0. Now let’s enumerate the anti-diagonals starting from 0. Note that based on our enumeration, the sum of row and column indices of all the cells of the matrix that are on the i^{th} anti-diagonal is equal to i. We can write a neat implementation based on this. We simply iterate over numbers from 0 up to 2 \times (N-1) and deal with the i^{th} anti-diagonal on the i^{th} iteration.

The time complexity of this solution is O(N^2)

Refer to the editorialist’s code to see the implementation of the described solution.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here

Tester’s solution can be found here

Editorialist’s solution can be found here

1 Like

VIDEO SOLUTION : CodeChef December Lunch Time 2018- Print Pattern(PPATTERN) - YouTube

2 Likes

video solution’s good

#include <stdio.h>
int main()
{
int i, j, k, m = 1, p = 1, l, q, n, w, t;
scanf("%d", &t);
while (t–)
{
scanf("%d", &n);
w = n - 1;
for (i = 1; i <= n; i++)
{

		l = i;
		q = 0;

		if (i % 2 == 0)
			k = (i * m) + m;
		else
			k = i * p;
		for (j = 1; j <= n; j++)
		{
			if (i == n)
			{
				printf("%d ", k);
				k = k + w;
				w--;
			}

			else
			{
				printf("%d ", k);

				k = k + l;
				if (l < n - 1 && q == 0)
					l++;
				else
				{
					q = q + 1;
					if (q <= 1)
						l = n - 1;
					else
						l--;
				}
			}
		}
		printf("\n");
		if (i % 2 == 0)
			m++;
		else
			p++;
	}
}

}

#include <stdio.h>
int main()
{
int i, j, k, m = 1, p = 1, l, q, n, w, t;
scanf("%d", &t);
while (t–)
{
scanf("%d", &n);
w = n - 1;
for (i = 1; i <= n; i++)
{

		l = i;
		q = 0;

		if (i % 2 == 0)
			k = (i * m) + m;
		else
			k = i * p;
		for (j = 1; j <= n; j++)
		{
			if (i == n)
			{
				printf("%d ", k);
				k = k + w;
				w--;
			}

			else
			{
				printf("%d ", k);

				k = k + l;
				if (l < n - 1 && q == 0)
					l++;
				else
				{
					q = q + 1;
					if (q <= 1)
						l = n - 1;
					else
						l--;
				}
			}
		}
		printf("\n");
		if (i % 2 == 0)
			m++;
		else
			p++;
	}
}

}

In my answer I have tried to solve this question using a series.
For example if n=5 then we make a series:

l = 1,2,3,4,4,3,2,1 .
Now we take a 2 variables i.e. x=1 & prev.
Now we do this

for ( i = 0 ; i lessthan n ; ++i ) {
    print x
    prev = x
        for ( y = 1 ; y < n ; ++y ) {
            print prev + l[i+y-1]
            prev += l[i+y-1]
        }
    x += i+2
}

I don’t know why my solution is Wrong, although it does what is required by the Question?

#include<iostream>
using namespace std;
int fillArr(int i, int j, int &cnt, int ** arr);
int showArr(int ** arr, int size);
int ppattern(int size);
int main() {
    int size;
    int t;
    cin>>t>>size;
    if( (t >= 1 && t <= 10) && (size >=1 && size <= 100)) {
        while(t != 0) {
                ppattern(size);
                t--;
                cout<<endl;
        }
    }
    return 0;
}
int ppattern(int size) {
    int cnt = 0;
    int ** arr = new int * [size];
    for(int i = 0; i < size; i++) {
	    arr[i] = new int[size];
    }
    for(int j = 0; j < size; j++) { //Upper Diagonal
	    if(j == 0)
		    arr[j][j] = ++cnt;
	    else
		    fillArr(0, j, cnt, arr);
    }
    for(int j = 1; j < size; j++) { //Lower Diagonal
	    if(j == size-1) {
		    arr[j][j] = ++cnt;
	    }
	    else
		    fillArr(size-1, j, cnt, arr);
    }
    showArr(arr, size);
    return 0;
}
int fillArr(int i, int j, int &cnt, int ** arr) {
    int big, small;
    if(i < j) {
	    big = j;
	    small = i;
    }
    else {
	    big = i;
	    small = j;
    }
    int b = big;
    int s = small;
    arr[s][b] = ++cnt;

    while(b != small && s != big) {
	    b--;
	    s++;
            arr[s][b] = ++cnt;
    }
    return 0;
}
int showArr(int ** arr, int size) {
    for(int i = 0; i < size; i++) {
	    for(int j = 0; j < size; j++) {
		    cout<<arr[i][j]<<" ";
	    }
	    cout<<endl;
    }
    return 0;
}

import java.util.*;

class pattern{
public static void main(String[] args) {
Scanner scan= new Scanner(System.in);
System.out.println(“enter the order”);
int n = scan.nextInt();
System.out.println(“enter the initial number”);
int ini=scan.nextInt();
int[][] real=new int [n][n];

                int counting=ini;
				
				for (int i=0;i<n*n-1 ;i++ ) {
					for (int a=0;a<n ;a++ ) {
						for (int b=0;b<n ;b++ ) {
							if (a+b==i) {
								real[a][b]=ini;
								ini++;
							}
						}
					}

}
for (int i=0;i<n ;i++ ) {

				for (int j=0;j<n ;j++ ){
						
						System.out.print(real[i][j]+" \t");		
				}
						System.out.println();

}

}

}

****I still cant figure out why is a wrong solution

My solution, probably the smallest
for i in range(0, n): for j in range(0, n): if i + j < n: arr[i][j] += (j+i)*(j+i+1)//2 + i+1 elif i + j >= n: arr[i][j] += (j+i)*(j+i+1)//2 + i+1 - (i + j + 1 - n) ** 2

another efficient way to solve the code.
#include
using namespace std ;

int main () {
int T;
cin>>T;
for (int k =0;k<T;k++){
int i=0;
int N;
cin>>N;

for (int temp1 =1; temp1<=N; temp1++){
    i = i + temp1;
    int j;
    cout<<i<<" ";
    j =i;
    int temp = temp1;
    for (int temp2 =1;temp2<=(N-temp1);temp2++){     
    j = j + temp;  
    cout<<j<<  " ";
    temp++;
    
    }

    if (temp1<N){
       int temp3 =temp-1;
        for(int temp2 =1; temp2<=(temp1-1); temp2++){
           
            j=j + temp3 ;
            temp3--;
           
            cout<<j<<" ";
            
        }
        
    }
    else if (temp1=N){
         
         int temp3 = temp -1;
        for (int temp2 =1 ;temp2<temp1; temp2++){
            j= j +temp3;
            temp3--;
            cout<<j<<" ";
        }
    } 

    cout<<endl;
}
}
return 0;

}

Can anyone help me, to print the table in a good manner I used -->
cout<<setw(3)<<t;
where t stores the value to be printed which is calculated by i , j the indices of the position and got WA.

But just edited the above statement to–>
cout<<t<<" ";
I got AC .

Can anyone explain why with setw() I’m getting WA ???

The following is my solve() function which works for each test case,

void solve()
{
int n,j,c,t,d;
cin>>n;

for(j=1;j<=n;j++){
t=(j*(j+1))/2;
d=min(j,n-1);
for(c=1;c<=n;c++){
cout<<t<<" ";
// cout<<setw(3)<<t; gives WA
t+=d;
if(j+c<n )d++; else
if(j+c>n ) d–;
}
cout<<endl;
}

}

There’s a pattern to the increments that you can use to make successive rows without making the whole grid. It’s easy to see that the increments across the top row are 1,2,3 ... ,n{-}1 then successive rows shift to lose the first increment (because a diagonal finishes) and add an increment on the end that decreases (shorter diagonals). The upshot is that the increments come from a pattern that looks like (1,2,3,4,4,3,2,1) for a 5 grid for example.

from itertools import accumulate, chain

T = int(input())
for tx in range(T):
    val = int(input())
    # "magic" pattern to reflect ascending/descending increments on rows
    patt = list(accumulate(chain(range(val), reversed(range(val)))))
    for rw in range(val):
        print(*(a+rw+1 for a in patt[rw:rw+val]))

Note that using this kind of obscure trick is a really bad idea in code that you or anyone else might ever have to come back to and update. But it’s pretty satisfying to find it.