PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Priority queues
PROBLEM:
There’s an array of size 2N. Alice and Bob play a game on it:
- Alice chooses any element, adds it to her score, and deletes it from A.
- Bob then deletes the leftmost remaining element of A.
Find Alice’s maximum possible score, under optimal play.
EXPLANATION:
Let’s try to analyze which sets of elements Alice can even take.
She definitely can’t take both A_1 and A_2: once she takes one of them, Bob is going to delete the other one.
So, she can take either A_1 or A_2; or skip both.
Next, consider A_3 and A_4.
If Alice chose one of A_1 or A_2, then again she can take at most one of A_3 and A_4, for the same reason.
However, if Alice chose neither A_1 nor A_2, she can now take both A_3 and A_4.
But, observe that there’s no way for Alice to choose three out of the first four elements: at best she can take two of them.
In general, this argument can be extended to any even-length prefix.
That is, among the first 2i elements, Alice can take at most i of them.
It’s easy to see why: by the time Alice takes i elements out of the first 2i, Bob will have deleted the other i of them so there’s nothing left.
This observation leads to a rather simple solution.
Let’s iterate over the the even-length prefixes, i.e. 2i = 2, 4, 6, 8, \ldots
For each 2i, we’ll maintain the best i elements we can take.
This can be done inductively, as follows:
- Include both A_{2i} and A_{2i-1} into the set.
- Now, we have i-1 elements out of the first 2(i-1), along with these two.
That puts us at i+1 elements out of the first 2i.
This means we have to drop one of the elements. - Clearly, it’s best to drop the smallest element, since our aim is to maximize the sum.
Note that dropping an element will never break the condition on any prefix, so we’re indeed free to drop whichever element we please; hence why we can choose the smallest.
To simulate this quickly, we need a data structure that allows for quick insertion, finding the minimum element, and deleting the minimum element.
A priority queue gets the job done, as does a set (in the languages where it’s sorted, like C++ and Java - unfortunately, not Python).
TIME COMPLEXITY:
\mathcal{O}(N \log N) per testcase.
CODE:
Editorialist's code (PyPy3)
import heapq
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
for i in range(0, 2*n, 2):
if a[i] > a[i+1]: a[i], a[i+1] = a[i+1], a[i]
ans = sum(a[1::2])
pq = []
for i in range(0, 2*n, 2):
heapq.heappush(pq, a[i])
ans += a[i] - pq[0]
heapq.heappop(pq)
heapq.heappush(pq, a[i+1])
print(ans)
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
n *= 2;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
priority_queue<ll> pq;
ll ans = 0;
for(int i = n; i >= 1; i -= 2){
pq.push(a[i]);
pq.push(a[i-1]);
ans += pq.top();
pq.pop();
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}