DISHDIS - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This was the Easy problem for this month. The problem is a standard combinatorics problem which asks us to find the number of solutions possible for:

x1 + x2 + x3 + … + xm = n
with the constraints ai<=xi<=bi

Though the problem can be solved using combinatorics, the constraints and the time limit of the problem allow a simple O(n3) dp solution to pass. The recurrence is straight-forward. Let dp[x][y] denote the number of ways of preparing y dishes by the first x cooks. Clearly, our answer will be dp[m][n]. The recurrence is as follows:

dp[i][j]=Σdp[i-1][j-k] where x[i]<=k<=y[i]

A lot of people had a problem passing the time limit with a recursive solution. It’s always better to write an iterative code for your solution, especially if the recurrence is simple.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

can anyone explain how this idea come and how it is working