PROBLEM LINK:
Authors: Vaibhav Tulsyan, Aditya Sarode
Tester: Vaibhav Tulsyan
Editorialist: Vaibhav Tulsyan
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
Given the marks for N questions and the corresponding time to solve, find the maximum marks that can be scored in given time T. Marks for any one particular question can be doubled.
QUICK EXPLANATION:
Maintain two 2D DP arrays, one being solution to the problem without doubling marks, and another being solution with doubling of marks. For a certain state (i,j), choose max between the value with doubling marks for i’th Question and the value without doubling.
EXPLANATION:
Consider two DP arrays dp1[i][j] and dp2[i][j].
dp1[i][j] represents the solution without doubling the marks of any question.
dp2[i][j] represents the solution with exactly one question’s marks doubled will now.
Now, for dp2[i][j]:
We have two options: Either reject the previously doubled marks, because doubling marks for current ‘i’ is more profitable, or continue with previously doubled value.
That is, we choose the maximum between 2 choices -
- Double marks of current i ----> ( dp1 [ i - 1 ] [ j - t [ i ] ] ) + 2 * m [ i ] … ( A )
- Dont double marks of current i ----> max( dp2 [ i - 1 ] [ j ], ( dp2 [ i - 1 ][ j - t [ i ] ] + m [ i ] ) … (B)
Hence, dp2 [ i ][ j ] = max ( A , B )
Therefore, the answer is dp2[ N ][ T ] ( 1 - indexed array ).
Complexity: O( N*T )