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 = 13Input: 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 Avoid 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 Codeint 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 approachimport java.util.*;class GFG{ // Function to calculate the// maximum amount collected by Astatic 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 Codepublic 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 Adef 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 CodeN = 2Arr = [[5, 2, 3, 4], [1, 6]]# Function call to calculate the# amount of coins collected by Afind(N, Arr) |
C#
// C# Program to implement// the above approachusing 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 Afunction 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 Codevar N = 2;var Arr = [[5, 2, 3, 4], [1, 6]];// Function call to calculate the// amount of coins collected by Afind(N, Arr);// This code is contributed by importantly.</script> |
Output:
8
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
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
