Optimizing Team Formation with Grade and Age Constraints - Coding

Given two arrays, grades[], and ages[], representing the grades and ages of participants in a competition. The goal is to form teams in a way that maximizes the total grade of each team while adhering to specific constraints. The constraints are defined as follows:

Each participant is characterized by a grade and an age.
A team is not allowed to have conflicts, meaning that a younger participant cannot have a higher grade than an older participant. However, conflicts do not occur between participants of the same age.

Examples:

Input: grades = [4, 7, 9, 5, 8] ,ages = [1, 2, 3, 1, 2]
Output: 33
Explanation: In this case we can take all the students , and no conflicting situation occurs, as the conflict would have occurred if an older person with a less grade would be in the team with younger person with more grade, both the students with grades 7 and 9 have ages 2 and 3 respectively, and students with age 5, 8 have ages 1 , 2 respectively, considering a team with all of them would not be a problem.

Input: grades = [1, 2, 3, 4], ages = [4, 3, 2, 1]
Output: 4
Explanation: In this case we can just take student with grade 4 and age 1 as rest all other combinations would result into conflict.

Approach: To solve the problem follow the below idea:

Define a global 2D array dp for memoization.
Implement a recursive function solver that takes i (current student index), and maxage (maximum age in the team), and returns the maximum grade that can be obtained.
Base case:
- If i exceeds the size of grp, return 0 (no more students to consider).
- If the result for the current ‘i‘ and ‘maxage‘ combination is already calculated, return it.
If the age of the current student (grp[i][1]) is greater than or equal to maxage, we have two choices:
- Include the current student and recursively call the solver for the next student with updated maxage and incremented grade.
- Skip the current student and call the solver for the next student with the same maxage.
Return the maximum value between the two choices as the result for this subproblem.
In the main function, create grades and ages vectors and call the bestTeamGrade function with these vectors as arguments. Print the result.

Below is the implementation for the above approach:

C++14

#include <bits/stdc++.h>
using namespace std;
 
// Define a global 2D array for memoization
int dp[10005][1001];
 
// Recursive function to find the maximum grade
// for the best team
int solver(vector<vector<int> >& grp, int i, int maxage)
{
    // Base case: If 'i' exceeds the size of
    // 'grp', return 0
    if (i >= grp.size()) {
        return 0;
    }
 
    // If the result for current 'i' and 'maxage'
    // combination is already calculated, return it
    if (dp[i][maxage] != -1)
        return dp[i][maxage];
 
    // If the age of the current student is
    // greater than or equal to 'maxage', we
    // have two choices:
    // 1. Include the current student and
    // recursively call 'solver' for the next
    // student with updated 'maxage' and
    // incremented grade.
    // 2. Skip the current student and call
    // 'solver' for the next student with
    // the same 'maxage'.
    if (grp[i][1] >= maxage) {
        return dp[i][maxage]
            = max(grp[i][0]
                        + solver(grp, i + 1, grp[i][1]),
                    solver(grp, i + 1, maxage));
    }
 
    // If the age of the current student is less
    // than 'maxage', skip the current student
    return dp[i][maxage] = solver(grp, i + 1, maxage);
}
 
// Function to find the maximum grade
// for the best team
int bestTeamGrade(vector<int>& grades, vector<int>& ages)
{
 
    // Initialize a 2D vector 'grp' where each
    // element is a vector containing the grade
    // and age of a student.
    vector<vector<int> > grp;
    for (int i = 0; i < grades.size(); i++) {
        vector<int> temp;
        temp.push_back(grades[i]);
        temp.push_back(ages[i]);
        grp.push_back(temp);
    }
 
    // Initialize the 'dp' array with -1
    // for memoization
    memset(dp, -1, sizeof(dp));
 
    // Sort the 'grp' vector based on age
    // in ascending order
    sort(grp.begin(), grp.end());
 
    // Call the 'solver' function with
    // initial values
    return solver(grp, 0, 0);
}
 
// Drivers code
int main()
{
    // Example 'grades' and 'ages' vectors
    vector<int> grades = { 1, 2, 3, 4 };
    vector<int> ages = { 4, 3, 2, 1 };
 
    // Call the 'bestTeamGrade' function and
    // print the result
    cout << bestTeamGrade(grades, ages);
    return 0;
}

Java

// Java code for the above approach:
 
import java.util.*;
 
class GFG {
    // Define a global D array for memoization
    static int[][] dp = new int[10005][1001];
 
    // Recursive function to find the maximum grade
    // for the best team
    static int solver(List<List<Integer> > grp, int i,
                      int maxage)
    {
        // Base case: If 'i' exceeds the size of
        // 'grp', return 0
        if (i >= grp.size()) {
            return 0;
        }
 
        // If the result for current 'i' and 'maxage'
        // combination is already calculated, return it
        if (dp[i][maxage] != -1)
            return dp[i][maxage];
 
        // If the age of the current student is
        // greater than or equal to 'maxage', we
        // have two choices:
        // 1. Include the current student and
        // recursively call 'solver' for the next
        // student with updated 'maxage' and
        // incremented grade.
        // 2. Skip the current student and call
        // 'solver' for the next student with
        // the same 'maxage'.
        if (grp.get(i).get(1) >= maxage) {
            return dp[i][maxage]
                = Math.max(grp.get(i).get(0)
                               + solver(grp, i + 1,
                                        grp.get(i).get(1)),
                           solver(grp, i + 1, maxage));
        }
 
        // If the age of the current student is less
        // than 'maxage', skip the current student
        return dp[i][maxage] = solver(grp, i + 1, maxage);
    }
 
    // Function to find the maximum grade
    // for the best team
    static int bestTeamGrade(List<Integer> grades,
                             List<Integer> ages)
    {
 
        // Initialize a 2D list 'grp' where each
        // element is a list containing the grade
        // and age of a student.
        List<List<Integer> > grp = new ArrayList<>();
 
        for (int i = 0; i < grades.size(); i++) {
            List<Integer> temp = new ArrayList<>();
            temp.add(grades.get(i));
            temp.add(ages.get(i));
            grp.add(temp);
        }
 
        // Initialize the 'dp' array with -1
        // for memoization
        Arrays.stream(dp).forEach(
            row -> Arrays.fill(row, -1));
 
        // Sort the 'grp' list based on age
        // in ascending order
        Collections.sort(grp,
                         (a, b) -> a.get(0) - b.get(0));
 
        // Call the 'solver' function with
        // initial values
        return solver(grp, 0, 0);
    }
 
    // Drivers code
    public static void main(String[] args)
    {
        // Example 'grades' and 'ages' lists
        List<Integer> grades = List.of(1, 2, 3, 4);
        List<Integer> ages = List.of(4, 3, 2, 1);
 
        // Call the 'bestTeamGrade' function and
        // print the result
        System.out.println(bestTeamGrade(grades, ages));
    }
}
 
// This code is contributed by ragul21

Python3

# Python code for the above approach
 
# Define a global D array for memoization
dp = [[-1 for _ in range(1001)] for _ in range(10005)]
 
# Recursive function to find the maximum grade
# for the best team
def solver(grp, i, maxage):
    # Base case: If 'i' exceeds the size of
    # 'grp', return 0
    if i >= len(grp):
        return 0
 
    # If the result for the current 'i' and 'maxage'
    # combination is already calculated, return it
    if dp[i][maxage] != -1:
        return dp[i][maxage]
 
    # If the age of the current student is
    # greater than or equal to 'maxage', we
    # have two choices:
    # 1. Include the current student and
    # recursively call 'solver' for the next
    # student with updated 'maxage' and
    # incremented grade.
    # 2. Skip the current student and call
    # 'solver' for the next student with
    # the same 'maxage'.
    if grp[i][1] >= maxage:
        dp[i][maxage] = max(
            grp[i][0] + solver(grp, i + 1, grp[i][1]),
            solver(grp, i + 1, maxage)
        )
        return dp[i][maxage]
 
    # If the age of the current student is less
    # than 'maxage', skip the current student
    dp[i][maxage] = solver(grp, i + 1, maxage)
    return dp[i][maxage]
 
# Function to find the maximum grade
# for the best team
def best_team_grade(grades, ages):
    # Initialize a 2D list 'grp' where each
    # element is a list containing the grade
    # and age of a student.
    grp = [[grades[i], ages[i]] for i in range(len(grades))]
 
    # Initialize the 'dp' array with -1
    # for memoization
    for row in dp:
        for i in range(len(row)):
            row[i] = -1
 
    # Sort the 'grp' list based on age
    # in ascending order
    grp.sort(key=lambda x: x[0])
 
    # Call the 'solver' function with
    # initial values
    return solver(grp, 0, 0)
 
# Driver code
if __name__ == "__main__":
    # Example 'grades' and 'ages' lists
    grades = [1, 2, 3, 4]
    ages = [4, 3, 2, 1]
 
    # Call the 'best_team_grade' function and
    # print the result
    print(best_team_grade(grades, ages))

C#

using System;
using System.Collections.Generic;
 
public class Solution
{
    // Define a global 2D array for memoization
    static int[,] dp = new int[10005, 1001];
 
    // Recursive function to find the maximum grade
    // for the best team
    static int Solver(List<int[]> grp, int i, int maxAge)
    {
        // Base case: If 'i' exceeds the size of 'grp', return 0
        if (i >= grp.Count)
        {
            return 0;
        }
 
        // If the result for current 'i' and 'maxAge'
        // combination is already calculated, return it
        if (dp[i, maxAge] != -1)
        {
            return dp[i, maxAge];
        }
 
        // If the age of the current student is
        // greater than or equal to 'maxAge', we
        // have two choices:
        // 1. Include the current student and
        // recursively call 'Solver' for the next
        // student with updated 'maxAge' and
        // incremented grade.
        // 2. Skip the current student and call
        // 'Solver' for the next student with
        // the same 'maxAge'.
        if (grp[i][1] >= maxAge)
        {
            return (dp[i, maxAge] = Math.Max(
                grp[i][0] + Solver(grp, i + 1, grp[i][1]),
                Solver(grp, i + 1, maxAge)
            ));
        }
 
        // If the age of the current student is less
        // than 'maxAge', skip the current student
        return (dp[i, maxAge] = Solver(grp, i + 1, maxAge));
    }
 
    // Function to find the maximum grade
    // for the best team
    static int BestTeamGrade(int[] grades, int[] ages)
    {
        // Initialize a List 'grp' where each
        // element is an array containing the grade
        // and age of a student.
        List<int[]> grp = new List<int[]>();
        for (int i = 0; i < grades.Length; i++)
        {
            grp.Add(new int[] { grades[i], ages[i] });
        }
 
        // Sort the 'grp' list based on age
        grp.Sort((a, b) => a[0].CompareTo(b[0]));
 
        // Call the 'Solver' function with
        // initial values
        return Solver(grp, 0, 0);
    }
 
    public static void Main(string[] args)
    {
        // Example 'grades' and 'ages' arrays
        int[] grades = { 1, 2, 3, 4 };
        int[] ages = { 4, 3, 2, 1 };
 
        // Initialize dp array with -1
        for (int i = 0; i < 10005; i++)
        {
            for (int j = 0; j < 1001; j++)
            {
                dp[i, j] = -1;
            }
        }
 
        // Call the 'BestTeamGrade' function and
        // print the result
        Console.WriteLine(BestTeamGrade(grades, ages));
    }
}

Javascript

// Define a global 2D array for memoization
 
let dp = new Array(10005).fill().map(() => new Array(1001).fill(-1));
 
// Recursive function to find the maximum grade
 
// for the best team
 
function solver(grp, i, maxage) {
 
    // Base case: If 'i' exceeds the size of
 
    // 'grp', return 0
 
    if (i >= grp.length) {
 
        return 0;
 
    }
 
    // If the result for current 'i' and 'maxage'
 
    // combination is already calculated, return it
 
    if (dp[i][maxage] !== -1) {
 
        return dp[i][maxage];
 
    }
 
    // If the age of the current student is
 
    // greater than or equal to 'maxage', we
 
    // have two choices:
 
    // 1. Include the current student and
 
    // recursively call 'solver' for the next
 
    // student with updated 'maxage' and
 
    // incremented grade.
 
    // 2. Skip the current student and call
 
    // 'solver' for the next student with
 
    // the same 'maxage'.
 
    if (grp[i][1] >= maxage) {
 
        return (dp[i][maxage] = Math.max(
 
            grp[i][0] + solver(grp, i + 1, grp[i][1]),
 
            solver(grp, i + 1, maxage)
 
        ));
 
    }
 
    // If the age of the current student is less
 
    // than 'maxage', skip the current student
 
    return (dp[i][maxage] = solver(grp, i + 1, maxage));
 
}
 
// Function to find the maximum grade
 
// for the best team
 
function bestTeamGrade(grades, ages) {
 
    // Initialize a 2D array 'grp' where each
 
    // element is an array containing the grade
 
    // and age of a student.
 
    let grp = [];
 
    for (let i = 0; i < grades.length; i++) {
 
        grp.push([grades[i], ages[i]]);
 
    }
 
    // Sort the 'grp' array based on age
 
    // in ascending order
 
    grp.sort((a, b) => a[0] - b[0]);
 
    // Call the 'solver' function with
 
    // initial values
 
    return solver(grp, 0, 0);
 
}
 
// Example 'grades' and 'ages' arrays
 
let grades = [1, 2, 3, 4];
 
let ages = [4, 3, 2, 1];
 
// Call the 'bestTeamGrade' function and
 
// print the result
 
console.log(bestTeamGrade(grades, ages));

Output

Time Complexity: O(n^2)
Auxiliary space: O(n*m), for the dp array, where ‘n’ is the number of students and ‘m’ is the maximum age.

Reffered: https://www.geeksforgeeks.org

DSA

Related
Count same Value Pairs with Minimum Separation
Maximizing Merit Points in Training Program
Match path of alphabets
Shortest alternate colored path
Find Winner by emptying the Array by Sum Modulo Array element

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12