### PROBLEM LINKS

### 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.