PROBLEM LINK:
Setter: Riktam Kundu
Tester 1: Aditya Kumar Shaw
Tester 2: Rashed Mehdi
Editorialist: Bratati Chakraborty
DIFFICULTY:
Easy
PREREQUISITES:
Greedy Algorithm
Strings
Sorting
PROBLEM
There is a dollar note array whose values need to be distributed between Mr. White and Pinkman. If the toss result is H, Mr. White picks a dollar note and then Pinkman. Alternatively, if the toss results in T, Pinkman selects first and then Mr. White. We need to find the person with the maximum amount of money at the end of the sharing procedure and the share he gets.
QUICK EXPLANATION
The dollar note array can be sorted in descending order so that at any point Mr. White or Pinkman make the optimal selection. We have to add the total money accumulated by Mr. White and Mr. Pinkman as the dollar notes get divided between the two. At the end, whoever gets the greater share of money, wins.
EXPLANATION
We have to find the amount of money Mr. White and Mr. Pinkman have accumulated after the sharing procedure. The optimal choice for both of them is to pick the maximum value remaining in the dollar note array. So, for the ease of optimal choice selection, we can sort the dollar note array in descending order.
Now, if toss result is H: Mr. White picks first and the first value in the array (which is the optimal one since we have sorted it in the descending order) gets added under his belt. Then Mr. Pinkman gets to choose and he will get the next highest value.
If toss result is T: Pinkman selects first and the highest value in the array gets transferred to him. Then Mr. White selects and takes the next highest dollar.
Once you have traversed the entire dollar note array, print the name of the person whose share of money is greater. And if both the values are same (in case of a draw), then print -1.
If N (no.\ of\ dollar\ notes = size\ of\ dollar\ note\ array) is odd, then we need to keep extra checking till the last toss. To avoid it, we can always add an extra dollar to our notes array with value 0. So, ultimately whoever gets this, his share remains unchanged (which is equivalent to not getting anything).
TIME COMPLEXITY
O(n)
Setter's Solution
Language: PYTHON 3.6
for i in range(int(input())):
n=int(input())
a=[]
s=[]
a=list(map(int,input().strip().split(" ")))[:n]
s=list(map(str,input().strip().split(" ")))
if n/2!=0:
a.append(0)
a.sort(reverse=True)
w=p=0
for l in range(len(s)):
if s[l]=='H':
w+=a[2*l]
p+=a[2*l+1]
else:
p+=a[2*l]
w+=a[2*l+1]
if w>p:
print("Mr. White",w)
elif p>w:
print("Pinkman",p)
else:
print(-1)
Tester 1's Solution
Language: C++17
#include<bits/stdc++.h>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int T, N;
cin >> T;
while(T--) {
cin >> N;
int size = N;
if(N%2 == 1)
size = N + 1; // make size even
int notes[size];
for(int i=0; i<N; ++i) { // take N elements as input
cin >> notes[i];
}
if(N%2 == 1)
notes[size-1] = 0; // add extra element to make it even
sort(notes, notes+size, greater<int>());
int num_toss = (N+1)/2;
char toss[num_toss];
for(int i=0; i<num_toss; ++i) {
cin >> toss[i];
}
int c = 0, W = 0, P = 0;
for(int i=0; i<num_toss; ++i) {
if(toss[i] == 'H') {
W += notes[c++];
P += notes[c++];
}
if(toss[i] == 'T') {
P += notes[c++];
W += notes[c++];
}
}
if(W>P) cout << "Mr. White " << W << "\n";
else if(W<P) cout << "Pinkman " << P << "\n";
else cout << "-1\n";
}
return 0;
}
Tester 2's Solution
Language: Java
import java.util.*;
class test{
public static void main(String args[]){
int n,i,qq=0,tt;
Scanner sc = new Scanner(System.in);
tt = sc.nextInt();
while(tt-->0){
int w=0,p=0;
qq=0;
n = sc.nextInt();
int arr[] = new int[n+1];
for(i=0;i<n;i++){
arr[i] = sc.nextInt();
}
char ch;
Arrays.sort(arr);
qq=n;
for(i=0;i<(n+1)/2;i++){
ch = sc.next().charAt(0);
if(ch == 'H'){
w+=arr[qq--];
p+=arr[qq--];
}
else{
p+=arr[qq--];
w+=arr[qq--];
}
}
if(p>w){
System.out.println("Pinkman " + p);
}
else if(p<w){
System.out.println("Mr. White " + w);
}
else{
System.out.println("-1");
}
}
}
}