PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Practice
Setter: Utkarsh Darolia
Testers: Nishank Suresh and Abhinav sharma
Editorialist: Utkarsh Darolia
DIFFICULTY
1742
PREREQUISITES
Sorting
PROBLEM
There are N soldiers in an army and the i^{th } soldier has 3 parameters — Attack points : A_i, Defense points : 1000A_i and Soldier type : ATTACK
or DEFENSE
.
For the whole army:

Attack value of the army is defined as the sum of attack points of all
ATTACK
type soldiers. 
Defense value of the army is defined as the sum of defense points of all
DEFENSE
type soldiers.  Rating of the army is defined as the product of Attack value and Defense value of the army.
The task is to assign the soldier type to each of the soldiers to maximize the rating of the army and find out that maximum rating.
EXPLANATION
To solve this problem, let’s first try solving a subproblem, which is to find the maximum achievable rating if you are given the count of soldiers of ATTACK
and DEFENSE
type.
Let’s define rating(r) as the maximum possible rating that can be achieved, given that we can assign any r soldiers to ATTACK
type and the remaining nr soldiers to DEFENSE
type. The solution to this subproblem can be constructed as follows —
 Sort the Attack points array A in descending order.
 Assign first r soldiers to
ATTACK
type and remaining nr toDEFENSE
type.  So, Attack points of every soldier of
ATTACK
type are greater than or equal to attack points of every soldier ofDEFENSE
type.
Proof that the proposed approach gives the assignment with maximum rating
A[i] are Attack points of soldier at index i and D[i] are the Defence points of soldier at index i.
After following the proposed approach, we can divide the soldiers into 2 groups Atk and Def —

Atk_{1}, Atk_{2}, …, Atk_{r} are indexes of the soldiers of
ATTACK
type. 
Def_{1}, Def_{2}, …, Def_{nr} are indexes of the soldiers of
DEFENSE
type.  A[Atk_{i}] \geq A[Def_{j}] and D[Atk_{i}] \leq D[Def_{j}] (1 \leq i \leq r ; 1 \leq j \leq nr)
Let’s assume that the proposed approach is wrong and there is a better value of rating(r) that can be achieved by swapping types of soldiers Atk_{i} and Def_{j} (1 \leq i \leq r ; 1 \leq j \leq nr). Let that the current Attack value and Defense value are Atkval and Defval respectively. Then the new values after swapping the types of soldiers would be —
 New Attack value =Atkval(A[Atk_{i}]A[Def_{j}]). As A[Atk_{i}] \geq A[Def_{j}], New Attack value is lesser than or equal to Atkval.
 New Defense value =Defval(D[Def_{j}]D[Atk_{i}])=. As D[Atk_{i}] \leq D[Def_{j}], New Defense value is lesser than or equal to Defval.
As both New Attack value and New Defense value are lesser than or equal to Atkval and Defval respectively, the New Rating would also be lesser than or equal to the initial rating.
So, we have a contradiction as we couldn’t get a better value of rating(r) and hence the approach that we proposed would always give the maximum value of rating(r).
Let B be the array that we got by sorting Attack points array A in descending order, Sum(r) be the sum of attack points of first r soldiers in array B and TotSum be the total sum of attack points of all soldiers.
We can simplify the expression of rating(r) using the steps below —
 Attack value \times Defense value
 [B_{1}+B_{2}...+B_{r}] \times [(1000B_{r+1})+(1000B_{r+2})...+(1000B_{n})]
 [Sum(r)] \times [(1000*(nr))(B_{r+1}+B_{r+2}...+B_{n})]
 [Sum(r)] \times [(1000*(nr))(TotSumSum(r))]
Our final answer would be maximum value of rating(r) where r ranges from 0 to n. This can be implemented by iterating over array B and finding Sum(r) for every r as Sum(r1)+B_{r} and putting all required values into the expression of rating(r) formulated above.
TIME COMPLEXITY
The overall time complexity is dependent on the sorting technique used. Everything except sorting can be done in O(N). If we use fast sorting techniques, then an overall time complexity O(Nlog(N)) per test case can be achieved.
SOLUTIONS
Editorialist's Solution
// Utkarsh Darolia
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for (int i = 1; i <= t; ++i)
{
int n;
cin >> n;
int TotSum = 0, Sum = 0;
int A[n];
for (int j = 0; j < n; ++j)
{
cin >> A[j];
TotSum += A[j];
}
sort (A, A+n, greater<int>()); //greater<int>() is used for sorting in descending order
long long finalAnswer = 0;
for (int r = 0; r < n; ++r)
{
finalAnswer = max (finalAnswer,(long long)(Sum)*((1000*(nr))(TotSumSum)));
Sum += A[r];
}
cout << finalAnswer << endl;
}
return 0;
}
Feel free to share your approach. Suggestions are welcome.