ARMTRN - EDITORIALe

editorial
, ,
1

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 : 1000-A_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 n-r 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 n-r to DEFENSE type.
  • So, Attack points of every soldier of ATTACK type are greater than or equal to attack points of every soldier of DEFENSE 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_{n-r} 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 n-r)

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 n-r). 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 [(1000-B_{r+1})+(1000-B_{r+2})...+(1000-B_{n})]
  • [Sum(r)] \times [(1000*(n-r))-(B_{r+1}+B_{r+2}...+B_{n})]
  • [Sum(r)] \times [(1000*(n-r))-(TotSum-Sum(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(r-1)+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*(n-r))-(TotSum-Sum)));
            Sum += A[r];
        }
      
        cout << finalAnswer << endl;
    }
    return 0;
}

Feel free to share your approach. Suggestions are welcome. :smile:

2

HERE IS MY APPROACH USING A PRIORITY QUEUE

int n;
	cin >> n;
	int a[n];
	priority_queue<int, vector<int>, greater<int>>pq;
	int attack = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		attack += a[i];
		pq.push(a[i]);
	}

	int ans = 0;
	int defense = 0;
	while (!pq.empty()) {
		int x = pq.top();
		pq.pop();
		defense += (1000 - x);
		attack = attack - x;
		ans = max(ans, attack * defense);
	}
	cout << ans << endl;
2 Likes