You are not logged in. Please login at www.codechef.com to post your questions!

×

# PPATTERN - Editorial

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

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

This question is marked "community wiki".

asked 28 Dec '18, 22:08 7★watcher
37
accept rate: 0% 19.8k350498541

 0 VIDEO SOLUTION : https://m.youtube.com/watch?v=nVJpkCV-tIE&t=3s answered 31 Dec '18, 16:38 3★ivabby 1●1 accept rate: 0%
 0 video solution's good answered 01 Jan, 12:33 1●1 accept rate: 0%

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


}

answered 03 Jan, 01:14 2★srvsus
1
accept rate: 0%

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


}

answered 03 Jan, 01:14 2★srvsus
1
accept rate: 0%

 0 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 }  link This answer is marked "community wiki". answered 05 Jan, 13:18 3★proram 1 accept rate: 0%
 0 I don't know why my solution is Wrong, although it does what is required by the Question? #include 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<
 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
 0 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 answered 19 Feb, 22:42 3★ayush4 16●3 accept rate: 10%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×850
×41

question asked: 28 Dec '18, 22:08

question was seen: 2,158 times

last updated: 19 Feb, 22:45