Perfect Team.

Hard
0/120
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in companies
SliceUberAspire Systems

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4
1 2 3 4
1 2 3 4  
5
1 2 3 4 5
1 1 2 1 2
Sample Output 1:
10
6

Sample Output 1 Explanation:

Test case 1:

We can take all the players as the player with greater age has greater skill.

Therefore the answer is 10.

Test case 2:

We can either take 3rd or 4th player as both of them cannot be part of the same team as the 3rd player is younger and has a greater skill. We will prefer 3rd player as we need maximum total skill.

Therefore the answer is 6.
Sample Input 2:
2
4
1 2 6 4
1 2 3 4
4
1 2 3 4
4 3 2 1
Sample Output 2:
7
4
Hint

Iterate over all possible teams.

Approaches (2)
Brute Force

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’.
Time Complexity

O(2^N), where ‘N’ denotes the number of players.

 

We are iterating over all the possible teams.

Space Complexity

O(N), where ‘N’ denotes the number of players.

 

We build an auxiliary vector/list to store ‘AGE’ and ‘SKILL’ of the player

Code Solution
(100% EXP penalty)
Perfect Team.
Full screen
Console