SQUIDRULE - Editorial

PROBLEM LINK: The Squid Game

Setter: Satyam Garg
Editorialist: Arpan Gupta

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Arrays

PROBLEM:

Given an array of N Players with an amount A_i associated with each. Whenever a player gets eliminated, the amount associated with him gets added to the pool prize. After N-1 eliminations, find the maximum pool prize that can be achieved.

EXPLANATION:

A player i will win maximum prize money only if all other players make up the maximum prize and that will be possible if all other players have prize money greater than or equal to the prize money associated with player i.
Let’s assume that player i has the least prize money associated with him. So, the maximum prize money possible after eliminating N-1 players will be (Total prize money – prize money of the player i)
First, find the total prize by iterating over all players and simultaneously finding the minimum element from the given array.

Time Complexity: O(n)
Space Complexity: O(n)

SOLUTIONS:

Setter's Solution(C++)
#include<bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> v(n);
		int sum = 0;
		int smallest_element = 1e6;
		for (int i = 0; i < n; i++) {
			cin >> v[i];
			sum += v[i];
			smallest_element = min(smallest_element, v[i]);
		}
		cout << sum - smallest_element << "\n";
	}
	return 0;
}

For doubts, please leave them in the comment section, I’ll address them.

2 Likes