PROBLEM LINK:
Author: Sibasish Ghosh
Tester: Saytabrat Panda
Editorialist: Sibasish Ghosh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
You are given N differnet herbs in a row. You are allowed to divide them into non-empty groups by creating some partitions (possibly zero) between them. Each group is allowed to have no more than M herbs in them. You have to calculate the total number of distinct groupings.
QUICK EXPLANATION:
The only difficulty was to find the recurrence for the DP solution:
Work your brains before you click on this
Let solve(i) be the number of distinct groupings possible using the first i herbs (till now we have already partitioned n-i herbs). So, the following recurrence relation will help us find the answer.
solve(i) += solve(i-x);
for all valid x such that i-x\geq 0.
EXPLANATION:
Let us try to form groups from the beginning of the row. For the first non-empty group, let us choose the first i herbs, where 1\leq i\leq M. So, to form the second non-empty group, we are left with (N-i) herbs. Now, let us choose j herbs for the second non-empty group, where 1\leq j\leq min(M,N-i). So, we are now left with (N-i-j) herbs. We have to repeat this process until we run out of herbs.
Try to think of what could be the recurrence relation to implement the above.
Think first!
solve(i) += solve(i-x);
for all valid x such that i-x\geq 0.
But wait! There’s more. If we form the recurrence tree for the above relation, we will find that many calculations are being done several times. This will lead to an exponential complexity for each test case, which is obviously not good enough for the given constraints.
This is where dynamic programming steps in. We just need to memoize our states to make sure calculations are not repeated. I’ll leave the implementation for you to try. Of course, you can refer to the solutions below if you weren’t able to solve it on your own.
P.S.: Do not forget to apply the modulus operator in the appropriate places.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
typedef long long int ll;
ll n,m;
ll dp[2010];
ll solve(ll x)
{
if(x < 0) // unsuccessful grouping
return 0;
if(x == 0) // successful grouping
return 1;
if(dp[x] != -1) // check if result is already calculated
return dp[x];
ll i,res=0;
for(i=1;i<=m;i++)
{
res+=solve(x-i);
res%=mod;
}
dp[x]=res;
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input3.txt","r",stdin);
// freopen("output3.txt","w",stdout);
ll t=1;
cin>>t;
while(t--)
{
cin>>n>>m;
memset(dp,-1,sizeof(dp));
ll ans=0,i;
ans=solve(n);
cout<<ans<<"\n";
}
return 0;
}
Tester's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
static long partition_from(int i){
if(i==n)
return 1l;
if(dp[i]!=-1)
return dp[i];
long take=0l;
for(int j=i+1;j<=Math.min(i+m, n);j++){
take+=partition_from(j)%mod;
take%=mod;
}
return dp[i]=take;
}
static long dp[];
static int n,m;
public static void process()throws IOException
{
n=ni();m=ni();
dp=new long[n+10];
Arrays.fill(dp,-1);
pn(partition_from(0));
}
static FastReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
out = new PrintWriter(System.out);
sc=new FastReader();
long s = System.currentTimeMillis();
int t=1;
t=ni();
while(t-->0)
process();
out.flush();
System.err.println(System.currentTimeMillis()-s+"ms");
System.out.close();
}
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);System.out.flush();}
static int ni()throws IOException{return Integer.parseInt(sc.next());}
static long nl()throws IOException{return Long.parseLong(sc.next());}
static double nd()throws IOException{return Double.parseDouble(sc.next());}
static String nln()throws IOException{return sc.nextLine();}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
static boolean multipleTC=false;
static long mod=(long)1e9+7l;
static<T> void r_sort(T arr[],int n){
Random r = new Random();
for (int i = n-1; i > 0; i--){
int j = r.nextInt(i+1);
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Arrays.sort(arr);
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next(){
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine() {
String str = "";
try{
str = br.readLine();
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
Feel free to write your approach in the comments 
