CMC303 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Newton Per Metre Square

Author: artha6391
Tester: anushka_nagar
Editorialist: anushka_nagar

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

Pascal’s Triangle
Binomial Coefficients
Binomial Theorem

PROBLEM:

The problem describes process of forming a pascal’s triangle. You have to output pascal’s triangle up to Nth row.

QUICK EXPLANATION:

Every entry in a line is value of a Binomial Coefficient.

Hence, we know that the value of ith entry in line number line is C(line, i) and all lines start with value 1.

So C(line, i) can be calculated from C(line, i-1) in O(1) time as follows

C(line, i) = C(line, i-1) * (line - i + 1) / i

EXPLANATION:

Binomial Coefficient C(n,k) is given as n! / k! (n-k)!

Hence,

C(line, i) = line! / ( (line-i)! * i! )

C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! )

We can derive following expression from above two expressions.

C(line, i) = C(line, i-1) * (line - i + 1) / i

So C(line, i) can be calculated from C(line, i-1) in O(1) time

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>

using namespace std;
void printPascal(int n)
{
    for (int line = 1; line <= n; line++){
        for (int i = 1; i <= line; i++){
            cout<< C<<" ";
            C = C * (line - i) / i;
        }
        cout<<"\n";
     }
}

int main()
{
    int t;
    cin>>t;
    while(t--){
	    int n;
	    cin>>n;
	    printPascal(n);
	    cout<<endl;
    }
    return 0;
}
Tester's Solution 
#include <bits/stdc++.h>

using namespace std;
void printPascal(int n)
{
    for (int line = 1; line <= n; line++){
        for (int i = 1; i <= line; i++){
            cout<< C<<" ";
            C = C * (line - i) / i;
        }
        cout<<"\n";
     }
}

int main()
{
    int t;
    cin>>t;
    while(t--){
	    int n;
	    cin>>n;
	    printPascal(n);
	    cout<<endl;
    }
    return 0;
}
Editorialist's Solution 
#include <bits/stdc++.h>

using namespace std;
void printPascal(int n)
{
    for (int line = 1; line <= n; line++){
        for (int i = 1; i <= line; i++){
            cout<< C<<" ";
            C = C * (line - i) / i;
        }
        cout<<"\n";
     }
}

int main()
{
    int t;
    cin>>t;
    while(t--){
	    int n;
	    cin>>n;
	    printPascal(n);
	    cout<<endl;
    }
    return 0;
}