Perfect Team.

Posted: 20 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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