PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: drishyam_420
Tester: jay_1048576
Editorialist: iceknight1093
DIFFICULTY:
2605
PREREQUISITES:
Greedy/dynamic programming, careful implementation
PROBLEM:
You’re given an array A. Find the minimum number of elements that need to be deleted from it so that the remaining array satisfies
EXPLANATION:
The final array must be such that it can be partitioned into k adjacent pairs, each having the same sum.
So, let’s fix what the final sum is, then try to find the longest array we can form that satisfies the condition.
Suppose we’ve fixed the sum to be S.
Let \text{pairs}_S be a list consisting of all pairs (i, j) such that A_i + A_j = S.
Note that \text{pairs}_S can be precomputed and stored for all S by simply iterating over all pairs of elements in A.
Suppose we choose to keep the pair (i, j) in the final array.
Then, notice that any other pair (i_2, j_2) must satisfy i_2 \gt j or j_2 \lt i.
That is, we must have either i_2 \lt j_2 \lt i \lt j or i\lt j\lt i_2\lt j_2, since we’re pairing i and j and hence can’t have i_2 or j_2 lie between them.
Thinking of it another way, we can consider the pair (i, j) to be the interval [i, j]. The above condition then means that any intervals we pick must be disjoint.
Our problem thus transforms to: given a list of intervals, find the maximum number of disjoint intervals that can be picked from them.
This is a classical problem, and can be solved greedily as follows:
- Sort the intervals in increasing order of their right endpoints.
That is, [l_1, r_1] comes before [l_2, r_2] if r_1 \lt r_2 (doesn’t really matter how ties are broken). - Let R_\text{max} denote the largest right endpoint we’ve encountered so far.
Initially, R_\text{max} = -\infty - Then, for each interval [l, r] in this sorted list:
- If l \leq R_\text{max}, ignore it
- Otherwise, [l, r] is disjoint from all the intervals seen so far, so take it into the answer and set R_\text{max} := r
This greedy strategy is provably optimal.
If \text{pairs}_S has K intervals in it, this algorithm takes \mathcal{O}(K\log K) time, but that’s only because we need to sort the intervals since the greedy part is linear.
In the specific case of this problem, we can in fact create the intervals in sorted form, eliminating the need for sorting entirely.
That can be done by the following pseudocode:
for j in 1...n:
for i in 1...j-1:
pairs[a[i] + a[j]].append((i, j))
That is, by iterating over the right endpoint in increasing order and then iterating over the left endpoint.
The time complexity of this approach is \mathcal{O}\left(\sum_S len(\text{pairs}_S)\right), which is just \mathcal{O}(N^2) since each pair (i, j) appears in exactly one sum.
Since the values of A_i + A_j can be as large as 2\cdot 10^9, \text{pairs} will likely need to be a map of some kind.
Depending on the kind of map used, this adds an \mathcal{O}(\log N) or (expected) \mathcal{O}(1) to the time complexity.
Hashmaps (unordered_map or gp_hash_table in C++, dict in Python) in particular pass well within the time limit.
There are other solutions to this problem, for example using dynamic programming.
However, you’ll need to be reasonably careful when implementing such solutions, since too many map accesses or extra log factors will result in TLE.
TIME COMPLEXITY
\mathcal{O}(N^2 \log N) or expected \mathcal{O}(N^2) per test case.
CODE:
Tester's code (C++)
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007
void solve(int tc)
{
int n;
cin >> n;
int a[n];
for(int i=0;i<n;i++)
cin >> a[i];
unordered_map<int,vector<pair<int,int> > > m;
for(int j=0;j<n;j++)
{
for(int i=0;i<j;i++)
{
m[a[i]+a[j]].push_back({i,j});
}
}
int ans = n;
for(auto z:m)
{
auto v = z.second;
int mx = 0;
map<int,int> dp;
for(auto p:v)
{
dp[p.second] = max(mx,dp[p.second]);
auto it = dp.lower_bound(p.first);
if(it == dp.begin())
dp[p.second]=max(dp[p.second],2ll);
else
dp[p.second]=max(dp[p.second],2+(--it)->second);
mx = max(mx,dp[p.second]);
}
ans = min(ans,n-mx);
}
cout << ans << '\n';
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
pairs = {}
for j in range(n):
for i in range(j):
if a[i] + a[j] not in pairs: pairs[a[i] + a[j]] = []
pairs[a[i] + a[j]].append(i*n + j)
ans = 0
for L in pairs.values():
ct, right = 0, -1
for x in L:
i, j = x//n, x%n
if i > right:
ct += 1
right = j
ans = max(ans, 2*ct)
print(n - ans)
