Maximum amount of money that can be collected by a player in a game of coins

0 0 5 minutes read

Given a 2D array Arr[][] consisting of N rows and two persons A and B playing a game of alternate turns based on the following rules:

A row is chosen at random, where A can only take the leftmost remaining coin while B can only take the rightmost remaining coin in the chosen row.
The game ends when there are no coins left.

The task is to determine the maximum amount of money obtained by A.

Examples:

Input: N = 2, Arr[][] = {{ 5, 2, 3, 4 }, { 1, 6 }}
Output: 8
Explanation:
Row 1: 5, 2, 3, 4
Row 2: 1, 6
Operations:

A takes the coin with value 5

B takes the coin with value 4

A takes the coin with value 2

B takes the coin with value 3

A takes the coin with value 1

B takes the coin with value 6

Optimally, money collected by A = 5 + 2 + 1 = 8
Money collected by B = 3 + 4 + 6 = 13

Input: N = 1, Arr[] = {{ 1, 2, 3 }}
Output : 3

Approach: Follow the steps below to solve the problem

In a game played with optimal strategy
Initialize a variable, say amount, to store the money obtained by A.
If N is even, A will collect the first half of the coins
Otherwise, first, (N / 2) coins would be collected by A and last (N / 2) would be collected by B
If N is odd, the coin at the middle can be collected by A or B, depending upon the sequence of moves.
Store the coin at the middle of all odd sized rows in a variable, say mid_odd[].
Sort the array mid_odd[] in descending order.
Optimally, A would collect all coins at even indices of min_odd[]
Finally, print the score of A.

Below is the implementation of the above approach:

C++

// CPP Program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to calculate the
// maximum amount collected by A
void find(int N,  vector<vector<int>>Arr)
{
     
    // Stores the money
    // obtained by A
    int amount = 0;
 
    // Stores mid elements
    // of odd sized rows
    vector<int> mid_odd;
    for(int i = 0; i < N; i++)
    {
 
        // Size of current row
        int siz = Arr[i].size();
 
        // Increase money collected by A
        for (int j = 0; j < siz / 2; j++)
            amount = amount + Arr[i][j];
 
        if(siz % 2 == 1)
            mid_odd.push_back(Arr[i][siz/2]);
    }
 
    // Add coins at even indices
    // to the amount collected by A
    sort(mid_odd.begin(),mid_odd.end());
 
    for(int i = 0; i < mid_odd.size(); i++)
        if (i % 2 == 0)
         amount = amount + mid_odd[i];
 
    // Print the amount
    cout<<amount<<endl;
 
}
 
// Driver Code
int main()
{
   int N = 2;
   vector<vector<int>>Arr{{5, 2, 3, 4}, {1, 6}};
 
   // Function call to calculate the
   // amount of coins collected by A
   find(N, Arr);
}
 
// This code is contributed by ipg2016107.

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
  
// Function to calculate the
// maximum amount collected by A
static void find(int N, int[][] Arr)
{
     
    // Stores the money
    // obtained by A
    int amount = 0;
 
    // Stores mid elements
    // of odd sized rows
    ArrayList<Integer> mid_odd 
            = new ArrayList<Integer>();
    for(int i = 0; i < N; i++)
    {
 
        // Size of current row
        int siz = Arr[i].length;
 
        // Increase money collected by A
        for (int j = 0; j < siz / 2; j++)
            amount = amount + Arr[i][j];
 
        if(siz % 2 == 1)
            mid_odd.add(Arr[i][siz/2]);
    }
 
    // Add coins at even indices
    // to the amount collected by A
    Collections.sort(mid_odd); 
     
    for(int i = 0; i < mid_odd.size(); i++){
        if (i % 2 == 0)
         amount = amount + mid_odd.get(i);
    }
 
    // Print the amount
    System.out.println(amount);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 2;
   int[][] Arr = {{5, 2, 3, 4}, {1, 6}};
 
   // Function call to calculate the
   // amount of coins collected by A
   find(N, Arr);
}
}
  
// This code is contributed by splevel62.

Python3

# Python Program to implement
# the above approach
 
# Function to calculate the
# maximum amount collected by A
 
 
def find(N, Arr):
 
    # Stores the money
    # obtained by A
    amount = 0
 
    # Stores mid elements
    # of odd sized rows
    mid_odd = []
 
    for i in range(N):
 
        # Size of current row
        siz = len(Arr[i])
 
        # Increase money collected by A
        for j in range(0, siz // 2):
            amount = amount + Arr[i][j]
 
        if(siz % 2 == 1):
            mid_odd.append(Arr[i][siz // 2])
 
    # Add coins at even indices
    # to the amount collected by A
    mid_odd.sort(reverse=True)
 
    for i in range(len(mid_odd)):
        if i % 2 == 0:
            amount = amount + mid_odd[i]
 
    # Print the amount
    print(amount)
 
 
# Driver Code
 
N = 2
Arr = [[5, 2, 3, 4], [1, 6]]
 
# Function call to calculate the
# amount of coins collected by A
find(N, Arr)

C#

// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to calculate the
  // maximum amount collected by A
  static void find(int N, List<List<int>> Arr)
  {
 
    // Stores the money
    // obtained by A
    int amount = 0;
 
    // Stores mid elements
    // of odd sized rows
    List<int> mid_odd = new List<int>();
    for(int i = 0; i < N; i++)
    {
 
      // Size of current row
      int siz = Arr[i].Count;
 
      // Increase money collected by A
      for (int j = 0; j < siz / 2; j++)
        amount = amount + Arr[i][j];
 
      if(siz % 2 == 1)
        mid_odd.Add(Arr[i][siz/2]);
    }
 
    // Add coins at even indices
    // to the amount collected by A
    mid_odd.Sort();
 
    for(int i = 0; i < mid_odd.Count; i++)
      if (i % 2 == 0)
        amount = amount + mid_odd[i];
 
    // Print the amount
    Console.WriteLine(amount);
 
  }
 
  // Driver code
  static void Main() 
  {
    int N = 2;
    List<List<int>> Arr = new List<List<int>>();
    Arr.Add(new List<int>());
    Arr[0].Add(5);
    Arr[0].Add(2);
    Arr[0].Add(3);
    Arr[0].Add(4);
    Arr.Add(new List<int>());
    Arr[1].Add(1);
    Arr[1].Add(6);
 
    // Function call to calculate the
    // amount of coins collected by A
    find(N, Arr);
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to calculate the
// maximum amount collected by A
function find(N,  Arr)
{
     
    // Stores the money
    // obtained by A
    var amount = 0;
 
    // Stores mid elements
    // of odd sized rows
    var mid_odd = [];
    for(var i = 0; i < N; i++)
    {
 
        // Size of current row
        var siz = Arr[i].length;
 
        // Increase money collected by A
        for (var j = 0; j < siz / 2; j++)
            amount = amount + Arr[i][j];
 
        if(siz % 2 == 1)
            mid_odd.push(Arr[i][siz/2]);
    }
 
    // Add coins at even indices
    // to the amount collected by A
    mid_odd.sort((a,b)=>a-b)
 
    for(var i = 0; i < mid_odd.length; i++)
        if (i % 2 == 0)
         amount = amount + mid_odd[i];
 
    // Print the amount
    document.write( amount + "<br>");
 
}
 
// Driver Code
var N = 2;
var Arr = [[5, 2, 3, 4], [1, 6]];
 
// Function call to calculate the
// amount of coins collected by A
find(N, Arr);
 
// This code is contributed by importantly.
</script>

Output:

Time Complexity: O(N log N), sort function takes N log N time to execute hence the overall time complexity turns out to be N log N
Auxiliary Space: O(x) where x is the number of mid elements of odd-sized rows pushed into the vector

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!