Perfect Team.

PROBLEM STATEMENT

You have been given ‘SKILL’ and ‘AGE’ of ‘N’ players. You want to choose the team with the highest total skill. The total skill is the sum of skills of all players in the team. However, in a team, no two players must exist such that the younger player has greater skill than the older player. In a team, two people of the same age can have different skill levels. Return the highest total skill of the team which is possible.

Example:

Let’s say the age of players is [1,2,6,4] and the skill of players is [1,2,3,4]. We cannot take all players in the team as 3rd player is older than 4th player but 4th player has strictly greater skill than 3rd player. Therefore we can take anyone among them. Therefore the highest total skill of team which is possible is 7.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the number of players.

The second line of each test case contains ‘N’ single space-separated integers representing the age of players.

The third line of each test case contains ‘N’ single space-separated integers representing the skill of players.

Output Format:

For each test case, print a single integer denoting the highest total skill of the team which is possible.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 100
1 <= ‘AGE[i]’ <= 10^3
1 <= ‘SKILL[i]’ <= 10^6

Time Limit: 1 sec

Approach 1

Make an auxiliary vector/list ‘player’ which store age as its first parameter and skill as the second parameter. Sort the list with age as a priority and if age is the same then on basis of skill. Then iterate over all the possible teams recursively.

We will apply the algorithm as follows:-

Declare a global vector/list ‘V’ which stores ‘AGE’ and ‘SKILL’ about players in ‘V’.
Sort the vector/list ‘V’.
Declare ‘ANS = 0’ and initialize it with zero.
Make a recursive function BUILD_TEAM(int IDX, int CURR_IDX, int CURR_TOTAL_SKILL, int N) where ‘IDX’ is the index of the player which was last taken into the team. If no player has been taken into the team yet it is ‘-1’. ‘CURR_IDX’ is the index of the player for which we need to make choice if he can be part of the team and ‘CURR_TOTAL_INDEX' is the skill of the team that has been build till now. We can implement it as follows:-

If ‘CURR_IDX == N’ we have no more players left to make choice.Update ‘ANS’ with max( ‘ANS’ , ‘CURR_TOTAL_SKILL’ ).
Otherwise, there are two cases possible:-
- ‘CURR_IDX’ player is not taken into team. Recursively call BUILD_TEAM(IDX, ‘CURR_IDX’+1, ‘CURR_TOTAL_SKILL’ , ‘N’).
- If ‘IDX’ is -1 i.e no players are into the team or if the skill of ‘CURR_IDX’ player is >= SKILL of ‘IDX’ player then we can take him in the team and recursively call BUILD_TEAM(‘CURR_IDX’, ‘CURR_IDX’+1, ‘CURR_TOTAL_SKILL’ + ‘v[CURR_IDX].second’ , ‘N’).
Return ‘ANS’.

Try Problem

Approach 2

Make an auxiliary vector/list ‘PLAYER’ which store age as its first parameter and skill as the second parameter. Sort the list with age as a priority and if age is the same then on basis of skill. We will also maintain array/list 'DP' where ‘DP[i]’ stores the maximum total skill of the team from ‘i’ players if the ith player was taken in the team.

Following is the algorithm for this approach:

Declare a global vector/list 'V' which stores ‘age’ and ‘skill’ about players in 'V'.
Sort the vector/list 'V'.
Declare a list 'DP' and initialize ‘i-th’ element with the skill of ‘i-th player.
We will calculate DP[i] starting from the beginning. For calculating DP[i] we will iterate 'DP' from the first player to ‘i-1’th player:-
- If ‘V[i].first’ == ‘V[j].first’ then we can add into optimal team whose last player was ‘jth’ player. Update DP[i] with max(‘DP[i]’, ‘DP[j]’ + ‘V[i].second’).
- Else if ‘V[i].second >= V[j].second’ only then we can add ‘i-th’ player into list because skill of older player cannot be smaller than skill of a younger player. Update ‘DP[i]’ with max(‘DP[i]’, ‘DP[j]’ + ‘V[i].second’).
Update ‘ANS’ with max(‘ANS’, ‘DP[i]’).
Return ‘ANS’.

Try Problem