“Sometimes it pays to stay in bed on Monday, rather than spending the rest of the week debugging Monday’s code.” — Dan Salomon
Hey readers! Hope you all enjoyed and understood the previous blog where we discussed an important DP technique with the Knapsack Problem. Today we will be seeing a slightly tougher version of that technique, so fasten your seat belts and enjoy this awesome DP journey.
Let’s start with the discussion
Before starting with the blog I recommend you all to go through the previous blog since we would be using some ideas from there too.
Today we will be solving an amazing DP problem from CodeForces — “Basketball Exercise ”. It is also based on the take it or leave it principle with something extra to consider ( we’ll discuss that extra thing later ).
The problem statement is as follows — We have 2n students standing in 2-lines with n students in each line. Each student has a certain height ( so, in total we are given heights of all 2n students ). We want to choose a team of some players ( not necessarily n ) such that the sum of heights of all the chosen players is maximum possible, but we are not allowed to choose 2 consecutive players from the same line ( i.e. if we have Line 1 with players having heights 1,2,3…10 and Line 2 with players having heights 11,12,13,….20, we are not allowed to choose 2,3 or 16,17 as both of them are consecutive and belong to the same line ). The first player can be chosen from any of the 2 lines.
Constraint : ( 1 ≤ n ≤ 10⁵ )
For further clarifications, you can read the problem statement from here.
Let’s start solving
STEP 1 — Build a naive recursive solution
Recall from the previous blog, at every step we had 2 options either to put the current item in our bag or leave it. In this problem, we have a similar selection choice which is, either leave the current player or select the current player followed by changing our current selection line( It means if we are currently at index idx and selecting from Line-0, we have 2 options either leave the player at index idx and recurse from the next index without changing the line or select the current player and recurse from the next index followed by changing our current line ).
Now the extra thing which we have to consider is, from which line should we begin our selection. So first, we start selection from Line — 0 and compute the maximum sum of heights similarly we start our selection from Line — 1 and compute the maximum sum of heights and finally print the maximum of both the sum values.
Let’s look at the recursive code made from the above discussions
Time Complexity — O(2^n) ( as in every step we have 2 choices, take the item or leave it. Thus by basic P&C we can very easily prove that the total number of ways will be 2^n ). So in the worst case, it will run 2¹⁰⁰⁰⁰⁰ times.
STEP 2 — Memoize the recursive solution
From the above code snippet, it is very clear that the changing parameters are none other than idx and curr_line. The maximum value of the index can be 10⁵ and for the current line, we have 2 options line 0 or 1.
So we can build a DP matrix of dimension 2 x 10⁵, and that would suffice the need of each and every possible case.
So here is the memoized code.
Time Complexity — O( 2*10⁵ ).
So, you learnt something very useful and interesting. Moreover, you just solved a DP problem rated 1400 on CodeForces, Kudos!
To check your understandings try submitting your code here.
Hope you’re enjoying this DP series, I try my best to keep things as simple as possible. Just stay tuned with us and you might learn something new with each upcoming blog.
For any doubts/queries in the above explanations, you can mail me at — ankitpandeycu@gmail.com
Share this blog with your peers if you find it useful and don’t forget to smash the clap button below.
Hope it helps.
AnkitCode99 here….
