EXAM - Editorial ( NCC 2014 )

PROBLEM LINK:

Contest

Practice

Authors: Vaibhav Tulsyan, Aditya Sarode

Tester: Vaibhav Tulsyan

Editorialist: Vaibhav Tulsyan

DIFFICULTY:

EASY

PREREQUISITES:

Knapsack Problem

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 -

  1. Double marks of current i ----> ( dp1 [ i - 1 ] [ j - t [ i ] ] ) + 2 * m [ i ] … ( A )
  2. 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 )

when will the problem visible in peer section? Make it fast please !

1 Like

Hey, the problems have been put up in the peer section for practice.

Shouldn’t the complexity be O(NT) rather than O(N^2)?

Thanks, I’ve made the changes.