QM18B - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester: Harsh Raj
Editorialist: Chandan Boruah

DIFFICULTY:

EASY.

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given a positive integer, and we partition the number into two numbers whose sum is equal to the given integer. We keep partioning the number till we cannot form any more positive integers by partitioning. This way a tree of numbers is formed, find the number of such trees that can be formed by partitioning the numbers.

QUICK EXPLANATION:

We partition the number into two parts in a loop, and multiply both these parts values to get a dp array for each index. We finally return dp[n].

EXPLANATION:

We loop from 2 to n, the given positive integer. And inside the loop we calculate the number of trees that can be formed for the current value in the loop. Which would be dp[i]+=dp[j]*dp[k]. We build this array to get dp[n], in the end.

SOLUTIONS:

Setter's Solution 
using System;
using System.Collections.Generic;
class some
{
	
	public static void Main()
	{	
		int n=int.Parse(Console.ReadLine());
		int sum=0;
		int[]dp=new int[n+1];
		if(n==1 || n==2 || n==3)Console.WriteLine(1);
		else
		{
			dp[1]=1;
			for(int i=2;i<=n;i++)
			{	
				for(int j=1,k=i-1;j<=k;j++,k--)
					dp[i]+=dp[j]*dp[k];
			}
			Console.WriteLine(dp[n]);
		}
	}	
}
/*
dp[1]=1;
dp[2]=dp[1],dp[1]
dp[3]=dp[1],dp[2]
dp[4]=dp[1],dp[3]+dp[2],dp[2]
dp[5]=dp[1],dp[4]+dp[2],dp[3]
dp[6]=dp[1],dp[5]+dp[2],dp[4]+dp[3],dp[3]
dp[7]=dp[1],dp[6]+dp[2],dp[5]+dp[3],dp[4]

, is *.. + is +
*/
Tester's Solution 
    #include<bits/stdc++.h>
    using namespace std;
     
    #define ll long long int
     
    vector<int> v(28,0);
     
    void pre(){
    	v[1] = 1;
    	v[2] = 1;
    	for(int i=3;i<28;i++){
    		for(int j=1;j<=i/2;j++){
    			v[i] += v[j]*v[i-j];
    		}
    	}
    }
     
    void solve(){
    	int n;
    	cin >> n;
    	cout << v[n] << "\n";
    }
     
    int main(){
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);	cout.tie(0);
     
    	pre();
     
    	
    	
    		solve();
    	
    	return 0;
    }