SEEDLING - Editorial

dynamic-programming
easy
ltime31
seedling

#1

Problem Link:

Practice

Contest

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


#2

Why did’nt you mention modulo 10^9 + 7 :confused:


#3

Cannot view the problem in Practice section. Would be grateful if the problem is moved to the practice section as fast as possible.


#4

What is wrong in my code?

https://www.codechef.com/viewsolution/9029482

#5

Will Recursive Backtracking with memoization pass, for 52 points?


#6

Can someone point out the case on which my solution is not working.Here is the link. I used the idea of coin change dp . I started at i=0(1st type of seedling) and from there call recursively to all types of seedling from i=0 to i=n-1 , incrementing the ans whenever profit was positive.

https://www.codechef.com/viewsolution/9026308

Thank in advance!


#7

Extremely disappointed with the problem statement. It was nowhere mentioned that the answer should be printed %10^9+7. Either all the solutions should have been rejudged after including test cases where the answer might be >10^18 (so that only those solutions that used bigInt or something similar passed) or the problem should be entirely removed.


#8

Why is it everytime that Setter/Tester’s solution is Access Denied?

Then what is the use of linking them here :frowning:


#9

Yes you can. The number of states in the second subtask is just ( 50 * 50 * 10000) approximately


#10

somebody please comment the correct approach.


#11

@admin @xcwgf666 Give us the access to view the solution of Setter and Tester.