PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sorting
PROBLEM:
You’re given N values X_1, \ldots, X_N.
Use these values to form N points of the form (X_i, Y_i), where Y_i \in \{0, 1, 2\}.
The score of a set of points is twice the maximum area of a triangle whose vertices have different y-coordinates.
Find the minimum possible score if you choose the points appropriately.
EXPLANATION:
The first thing to do is understand what the area of a triangle looks like, given its endpoints.
Our y-coordinates are fixed to being 0, 1, 2 because of how the score is computed, so let’s work with that.
Suppose we have the points (a, 0), (b, 1), (c, 2).
Then, their (doubled) area is given by the expression
This follows from simple coordinate geometry, see here for example.
Our goal is to split points across the three y-coordinates in order to minimize the maximum of this expression across all ways to choose one point from each y-coordinate.
Observe, in particular, that |2b-a-c| is maximized by either having b as large as possible and a, c as small as possible, or vice versa - b as small as possible and a, c as large as possible.
It’s helpful to understand some structure of what can be optimal.
Suppose we’ve already chosen a non-empty subset of points to have y-coordinate 1.
Let this set be denoted B, and let A, C denote the sets that will have y-coordinates 0, 2.
Suppose the remaining values are p_1 < p_2 < \ldots < p_k.
Then, it can be proved that the optimal split of these points into A and C will be one of these two forms:
- A prefix and a suffix, i.e. choose some 1 \le i \lt k such that A = \{p_1, \ldots, p_i\} and C = \{p_{i+1}, \ldots, p_k\}.
- A singleton and everything else, i.e. choose some 1 \le i \le k and let A = \{p_i\} and C = \{p_1, \ldots, p_{i-1}, p_{i+1}, \ldots, p_k\}.
This follows from what we observed about |2b-a-c| being maximized by only the minimum/maximum values of a, b, c.
In particular, note that if both A and C have sizes \ge 2, and we have
then we can simply take all values in C that are in the range [\min(A), \max(A)] and move them into A; and this cannot increase the maximum possible value of |2b-a-c| since \min(C) only increases while everything else stays the same.
Thus, if A and C are both not singletons, then they must contain disjoint ranges of values; which proves our claim.
With the above property in hand, it’s not too hard to solve the problem.
Let’s fix the values of \min(B) and \max(B).
Note that when doing this, it’s optimal to take all values between them into B as well; for similar reasons as above (it can’t worsen the max score.)
After fixing both, there are only \mathcal{O}(N) options for what A and C can be, and the constraints are small enough to allow for just checking all of them.
This gives a solution in \mathcal{O}(N^3), which is fast enough given the constraints on N.
It’s possible to optimize this to \mathcal{O}(N^2 \log N) fairly easily with the help of binary search; or even \mathcal{O}(N \log N) by applying a couple different optimization techniques, if you’d like to try.
However, these were not required to get AC.
TIME COMPLEXITY:
\mathcal{O}(N^3) \sim \mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 10**18
for i in range(n):
for j in range(i, n):
rem = a[:i] + a[j+1:]
if len(rem) < 2: continue
# singleton
# not endpoint, that's handled below anyway
for k in range(1, len(rem)-1):
cur = max(2*a[j] - rem[k] - rem[0], rem[k] + rem[-1] - 2*a[i])
ans = min(ans, cur)
# prefix/suffix
for k in range(len(rem)-1):
cur = max(2*a[j] - rem[0] - rem[k+1], rem[k] + rem[-1] - 2*a[i])
ans = min(ans, cur)
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;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
sort(a.begin()+1,a.begin()+n+1);
auto valid_exists = [](ll m, array<pll,3>& vals) -> bool{
array<ll,3> pos = {0,1,2};
do{
// pos[i] denotes the interval index of the y = i
ll p0 = pos[0], p1 = pos[1], p2 = pos[2];
ll x1_max = abs(2*vals[p1].ss-vals[p0].ff-vals[p2].ff);
ll x1_min = abs(2*vals[p1].ff-vals[p0].ss-vals[p2].ss);
ll mx = max(x1_max, x1_min);
if(mx <= m){
return true;
}
} while(next_permutation(all(pos)));
return false;
};
auto ok = [&](ll m) -> bool {
// 3 non-empty segs
// fix interval of mid seg
for(int l2 = 2; l2 < n; ++l2){
for(int r2 = l2; r2 < n; ++r2){
array<pll,3> vals = {
pll{a[1],a[l2-1]},
{a[l2],a[r2]},
{a[r2+1],a[n]}
};
if(valid_exists(m,vals)){
return true;
}
}
}
// 2 big segs
// pref, suff, single
// fix len of pref, and pos of single
// single CANT be an endpoint (otherwise, covered in previous 3 segs case only)
rep1(pref,n-1){
for(int single = 2; single < n; ++single){
if(single == pref or single == pref+1){
continue;
}
array<pll,3> vals = {
pll{a[1],a[pref]},
{a[pref+1],a[n]},
{a[single],a[single]}
};
if(valid_exists(m,vals)){
return true;
}
}
}
// 1 big seg, 2 singles
// full, single, single
// fix pos of both singles
// no singles on the ends
for(int single1 = 2; single1 < n; ++single1){
for(int single2 = single1+1; single2 < n; ++single2){
array<pll,3> vals = {
pll{a[1],a[n]},
{a[single1],a[single1]},
{a[single2],a[single2]}
};
if(valid_exists(m,vals)){
return true;
}
}
}
return false;
};
ll lo = 0, hi = 2*inf1;
ll ans = -1;
while(lo <= hi){
ll mid = (lo+hi)>>1;
if(ok(mid)){
ans = mid;
hi = mid-1;
}
else{
lo = mid+1;
}
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
cerr << "RUN SUCCESSFUL" << endl;
return 0;
}