Problem Link:
Difficulty:
Easy
Pre-requisites:
Dynamic Programming
Problem:
Find the number of ways to buy seedlings in such a way that the profit from these seedlings exceeds the expenses on these seedlings and the occupied area doesn’t exceed S.
Explanation:
Solution for the subtask 1 (17 points):
It is possible to check every way to buy seedlings with a simple recursive backtrack.
For the more detailed explanation, we provide the following pseudocode. In the pseudocode k is the current type of seedling, space is the amount of occupied square meters and profit is “pure profit”, i.e. profit minus expenses.
Having the state denoted by (k, space, profit), we can do one of the following two things:
- Either to buy one more seedling of the kth kind, moving to the state (k, space + a[k], profit + c[k] - b[k]), where a, b, c have the same meaning as in the statement.
- Don’t buy any more seedlings of this kind, moving to the state (k+1, space, profit).
Summing all this up, we obtain the following backtrack pseudocode:
backtrack (int k, int space, int profit)
if (k + 1 > n)
if (profit > 0)
answer = answer + 1
return
backtrack(k + 1, space, profit)
if (space + a[k] <= s)
backtrack(k, space + a[k], profit + c[k] - b[k]);
}
Which should be called this way:
backtrack(1, 0, 0)
Solution for subtasks 1, 2 (52 points):
As in the previous subtask, we can take (k, space, profit) as a state. Now let’s caculate the number of ways cleverer. Let’s denote by dp[k][space][profit] the number of ways to enter the backtrack routine with the corresponding values of k, space and profit.
Initially, only dp[1][0][0] is equal to one. The rest of values are zero.
When having a state, denoted by (k, space, profit), we can move to
- When we buy one more seedling of the kth kind, we move to the state (k, space + a[k], profit + c[k] - b[k]), where a, b, c have the same meaning as in the statement. So we add dp[k][space][profit] to dp[k][space + a[k]][profit + c[k] - b[k]].
- When we don’t buy any more seedlings of this kind, we move to the state (k+1, space, profit). So we add dp[k][space][profit] to dp[k+1][space][profit].
The answer is then the sum over dp[n+1][x][y] over all possible x and y.
This way we get a solution that runs in O(numberOfStates), where numberOfStates is O(N \cdot S \cdot (S \cdot \max\{B_i, C_i\})) which fits in allocated time.
Solution for all subtasks:
Previously described solution won’t work well at the last subtask because the values of C_i could be very large. But let’s note that in case the value of profit becomes greater than S \cdot max\{B_i\} \leq 10^4, then we can pick any set seedlings. It can be fixed with adding a new additional state, denoting that the sum of C_i-B_i is now greater than 10^4. This reduces the complexity to O(N \cdot S^2 \cdot \max\{B_i\}).
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
