Find the sum of elements after X deletions and Y sign inversions
Two Players A and B are engaged in a game with an array of positive integers arr[] of size N. The game starts with Player A deleting at max X elements from the array arr[]. Then, Player B can select at max Y elements and multiply them with -1. Player A wants to maximize the sum of arr[] after both the players have made their move whereas Player B wants to minimize the sum. The task is to determine the sum of the elements in the array arr[] if both the players have moved optimally.
Examples:
Input: N = 4, arr[] = {3, 1, 2, 4}, X = 1, Y = 1
Output: 2
Explanation: It is optimal for Player A to not delete any element. Player B will then multiply 4 with -1. So, the sum of elements of arr[] = 3 + 1 + 2 – 4 = 2.Input: N = 8, arr[] = {5, 5, 3, 3, 3, 2, 9, 9}, X = 5, Y = 3
Output: -5
Explanation: It is optimal for Player A to delete {9, 9}. Player B will then multiply {5, 5, 3} with -1. So, the sum of elements of arr[] = -5 – 5 – 3 + 3 + 3 + 2 = -5.
Approach: To solve the problem, follow the below idea:
It is optimal for Player B to negate the Y largest elements of the array. Player A will always try to delete the largest elements in the array to prevent Player B to negate them.
To solve the problem, we can sort the array and iterate over i (0 ≤ i ≤ X) where i is the number of elements Player A deletes. For each i, we know that Player A will delete the i largest elements of the array, and Player B will then negate the Y largest remaining elements. So, the sum at the end can be calculated quickly with prefix sums.
Step-by-step algorithm:
- Sort the given array arr[] and modify arr[] to store the prefix sums.
- Iterate i from 0 to X, where i is the number of elements deleted by Player A.
- Find the maximum sum in each of the cases.
- Return the maximum sum among all i from 0 to X.
Below is the implementation of approach:
Java
import java.util.*; public class Main { static final int MOD = 1000000007 ; // Function to solve the problem static void solve( int N, ArrayList<Integer> arr, int X, int Y) { // Sort the array in non-decreasing order Collections.sort(arr, Collections.reverseOrder()); // Calculate prefix sums for ( int i = 1 ; i < N; i++) { arr.set(i, arr.get(i) + arr.get(i - 1 )); } // Initialize answer int ans = -1_000_000_000; // Iterate over possible values of i for ( int i = 0 ; i <= X; i++) { if (i == 0 ) { int curr = arr.get(N - 1 ) - 2 * (arr.get(Math.min(i + Y - 1 , N - 1 ))); ans = Math.max(ans, curr); } else { int curr = arr.get(N - 1 ) - 2 * arr.get(Math.min(i + Y - 1 , N - 1 )) + arr.get(i - 1 ); ans = Math.max(ans, curr); } } // Output the answer System.out.println(ans); } // Main function public static void main(String[] args) { // Input variables: N, X, Y int N = 8 , X = 5 , Y = 3 ; // ArrayList to store array elements ArrayList<Integer> arr = new ArrayList<>(Arrays.asList( 5 , 5 , 3 , 3 , 3 , 2 , 9 , 9 )); solve(N, arr, X, Y); } } // This code is contributed by Ayush Mishra |
C#
using System; using System.Collections.Generic; using System.Linq; public class MainClass { const int MOD = 1000000007; // Function to solve the problem static void Solve( int N, List< int > arr, int X, int Y) { // Sort the array in non-decreasing order arr.Sort((a, b) => b.CompareTo(a)); // Calculate prefix sums for ( int i = 1; i < N; i++) { arr[i] += arr[i - 1]; } // Initialize answer int ans = -1_000_000_000; // Iterate over possible values of i for ( int i = 0; i <= X; i++) { if (i == 0) { int curr = arr[N - 1] - 2 * (arr[Math.Min(i + Y - 1, N - 1)]); ans = Math.Max(ans, curr); } else { int curr = arr[N - 1] - 2 * arr[Math.Min(i + Y - 1, N - 1)] + arr[i - 1]; ans = Math.Max(ans, curr); } } // Output the answer Console.WriteLine(ans); } // Main function public static void Main( string [] args) { // Input variables: N, X, Y int N = 8, X = 5, Y = 3; // List to store array elements List< int > arr = new List< int > { 5, 5, 3, 3, 3, 2, 9, 9 }; Solve(N, arr, X, Y); } } |
Javascript
// Function to solve the problem function solve(N, arr, X, Y) { // Sort the array in non-decreasing order arr.sort((a, b) => b - a); // Calculate prefix sums for (let i = 1; i < N; i++) { arr[i] += arr[i - 1]; } // Initialize answer let ans = -1e9; // Iterate over possible values of i for (let i = 0; i <= X; i++) { if (i === 0) { let curr = arr[N - 1] - 2 * (arr[Math.min(i + Y - 1, N - 1)]); ans = Math.max(ans, curr); } else { let curr = arr[N - 1] - 2 * arr[Math.min(i + Y - 1, N - 1)] + (i > 0 ? arr[i - 1] : 0); ans = Math.max(ans, curr); } } // Output the answer console.log(ans); } // Main function function main() { // Input variables: N, X, Y const N = 8, X = 5, Y = 3; // Array to store elements const arr = [5, 5, 3, 3, 3, 2, 9, 9]; solve(N, arr, X, Y); } // Calling the main function main(); // This code is contributed by Ayush Mishra |
C++14
#include <bits/stdc++.h> using namespace std; #define MOD 1000000007 // Function to solve the problem void solve( int N, vector< int >& arr, int X, int Y) { // Sort the array in non-decreasing order sort(arr.begin(), arr.end(), greater< int >()); // Calculate prefix sums for ( int i = 1; i < N; i++) { arr[i] += arr[i - 1]; } // Initialize answer int ans = -1e9; // Iterate over possible values of i for ( int i = 0; i <= X; i++) { if (i == 0) { int curr = arr[N - 1] - 2 * (arr[min(i + Y - 1, N - 1)]); ans = max(ans, curr); } else { int curr = arr[N - 1] - 2 * arr[min(i + Y - 1, N - 1)] + arr[i - 1]; ans = max(ans, curr); } } // Output the answer cout << ans << "\n" ; } // Main function int main() { // Input variables: N, X, Y int N = 8, X = 5, Y = 3; // Vector to store array elements vector< int > arr = { 5, 5, 3, 3, 3, 2, 9, 9}; solve(N, arr, X, Y); } |
Python3
def solve(N, arr, X, Y): # Sort the array in non-decreasing order arr.sort(reverse = True ) # Calculate prefix sums for i in range ( 1 , N): arr[i] + = arr[i - 1 ] # Initialize answer ans = - 1_000_000_000 # Iterate over possible values of i for i in range (X + 1 ): if i = = 0 : curr = arr[N - 1 ] - 2 * (arr[ min (i + Y - 1 , N - 1 )]) ans = max (ans, curr) else : curr = arr[N - 1 ] - 2 * arr[ min (i + Y - 1 , N - 1 )] + arr[i - 1 ] ans = max (ans, curr) # Output the answer print (ans) # Main function if __name__ = = "__main__" : # Input variables: N, X, Y N, X, Y = 8 , 5 , 3 # List to store array elements arr = [ 5 , 5 , 3 , 3 , 3 , 2 , 9 , 9 ] solve(N, arr, X, Y) #This code is contributed by rohit singh |
-5
Time Complexity: O(NlogN + X), where N is the size of input array arr[] and X is the number of elements Player A can delete.
Auxiliary Space: O(1)