PANSTACK - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This problem can be solved by dynamic programming. Let dp[i][j] represent number of ways of arrangement such that in a stack of i pancakes the maximum radius is j. hence dp[i][j] = dp[i-1][j]*j + dp[i-1][j-1]. The first term is the cases in which you have placed pancakes till size j in the previous position, in those cases you can place any pancake till radius j in the current position. And the second term is the case when you are placing a pancake of radius exactly 1 less than j in all the previous positions and you are allowed to place a pancake of radius j in the current position. For answer of size n, sum over all j <= n for dp[n][j] will be the result.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

4 Likes

Tell me if I am wrong…

The answer of this problem should be Catalan Number

Why it is showing always wrong answer!!!

How to solve it using one D DP?

Can some one explain the solution more clearly?

2 Likes

No, the answer should’nt be the catalan number because when n=4 Cn=14 but the answer is 15 .

`
public class Solution {

public static void main(String[] args) {
	// TODO Auto-generated method stub
	
	int n=5;
	// i'm using n-1 here is because at the bottom of the stack one pankcake of radius 1 is fixed,
	//where as max represents the  maximum radius upto this number
	System.out.println(fun(n-1,1));

}
static long fun(int n, int max) {
	if(n==0) {
		return 1;
	}
	if(n<0) {
		return 0;
	}
	

	long ans=0;
	for(int i=1;i<=max+1;i++) {
	   ans+=fun(n-1,Math.max(i, max));
	}

	return ans;

}
}

A 1-D dp array could also solve the problem.

      #include <bits/stdc++.h>
      using namespace std;
      #define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
      #define mod (ll)1000000007
      #define ll long long
      int main()
      {
          fast;
          int prev=0;
          vector<ll>dp(1001,0);
          dp[1]=1;dp[0]=0;
          vector<int>store(1001,0);
          for(int i=2;i<=1000;i++)
          {
              ll prev=0;
              ll sum=0;
              for(int j=i;j>=1;j--)
              {
                  dp[j]=(dp[j-1]+(j*dp[j])%mod)%mod;
                  store[i]=(store[i]+dp[j])%mod;
              }
          }
          store[1]=1;
          int t;cin>>t;
          while(t--){
              int n;
              cin>>n;
              cout<<store[n]<<endl;
          }
          return 0;
        }

Can anyone help me with this?