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

×

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

This question is marked "community wiki".

asked 28 Dec '18, 22:08

watcher's gravatar image

7★watcher
37
accept rate: 0%

edited 30 Dec '18, 23:53

admin's gravatar image

0★admin ♦♦
19.8k350498541


link

answered 31 Dec '18, 16:38

ivabby's gravatar image

3★ivabby
11
accept rate: 0%

edited 31 Dec '18, 16:38

video solution's good

link

answered 01 Jan, 12:33

chinmaysama_99's gravatar image

2★chinmaysama_99
11
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++;
    }
}

}

link

answered 03 Jan, 01:14

srvsus's gravatar image

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

}

link

answered 03 Jan, 01:14

srvsus's gravatar image

2★srvsus
1
accept rate: 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

proram's gravatar image

3★proram
1
accept rate: 0%

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

answered 05 Jan, 15:27

gagan352's gravatar image

0★gagan352
1
accept rate: 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*

link

answered 06 Jan, 04:14

cohannan's gravatar image

0★cohannan
11
accept rate: 0%

edited 06 Jan, 04:16

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

link

answered 19 Feb, 22:42

ayush4's gravatar image

3★ayush4
163
accept rate: 10%

edited 19 Feb, 22:45

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,178 times

last updated: 19 Feb, 22:45