PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: dash2199
Testers: iceknight1093, rivalq
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Subset sum dp
PROBLEM:
You’re given an array A containing N integers.
In one move, you can pick 1 \leq i \lt j \leq N and subtract \min(A_i, A_j) from both A_i and A_j.
Find out whether it’s possible to make all the array elements 0.
If it is, also find a way to achieve this using at most N operations.
EXPLANATION:
First, let’s see how to decide whether the answer is Yes or No.
Clearly, performing an operation when \min(A_i, A_j) = 0 is pointless, so let’s not perform such operations.
Suppose a valid sequence of moves exists. For each i, let’s match it with the j that sets it to zero.
In other words, let’s create a graph on N vertices, where for each move (i, j) that we make, we add the edge i \leftrightarrow j.
A bit of observation should tell you that this graph cannot contain cycles, i.e, it’s a forest.
Proof
Let’s build the graph edge-by-edge.
Suppose we’re adding the edge (i, j). This sets at least one of A_i and A_j to zero.
Claim: At any stage, every connected component of our graph contains at most one node with non-zero value.
Proof: The proof is by induction on the number of edges added.
The claim is clearly true for when there are no edges, since each component is a singleton.
Now, look at what happens when we add an edge (i, j).
- If A_i and A_j are in the same component, one of them is zero so we don’t make this move anyway.
- If they’re in different components, these two components join together. However, at least one of A_i and A_j becomes zero, so the new combined component also has at most one non-zero vertex.
This shows that every edge joins two different components together, and hence cannot create a cycle.
This graph being a forest specifically means that it’s bipartite.
Let (X, Y) be two sets forming a bipartition of this graph.
Also, let \displaystyle S_X = \sum_{x\in X} A_x and \displaystyle S_Y = \sum_{y\in Y} A_y be the sums of the respective sets.
Notice that any edge connects some element of X to some element of Y; in other words, every operation subtracts the same value from both S_X and S_Y.
So, S_X = S_Y must hold.
In particular, this means A can be partitioned into two subsets of equal sum.
Of course, this condition is necessary for the answer to be Yes. Is it also sufficient?
Yes, it is!
Suppose X and Y partition A, such that S_X = S_Y.
it’s quite easy to construct a sequence of operations: pick some non-zero element from X, pick some non-zero element from Y, then perform the operation on them.
Since their sums are equal, both sets will become empty at the same time.
So, all we really need to do is to check whether A can be partitioned into two subsets with equal sum.
This is, in fact, an instance of the subset-sum problem. We’re really just looking for a subset of A whose sum equals sum(A)/2.
Notice that if sum(A) is odd then we can never find such a subset.
The subset-sum problem can be solved in \mathcal{O}(N\cdot sum(A)) using dynamic programming.
How?
Let dp(i, x) be \text{True} if we can get a subset with sum x from the first i elements, and \text{False} otherwise.
Then, dp(i, x) is \text{True} if and only if dp(i-1, x) is \text{True}, or if dp(i-1, x-A_i) is \text{True}; otherwise it’s \text{False}.
This gives us \mathcal{O}(N\cdot sum(A)) states and \mathcal{O}(1) transitions each.
Once a bipartition has been found, reconstructing the operations is trivial; as mentioned above, simply keep picking one non-zero element each from the two sets.
This takes at most N-1 steps, since every operation makes one element 0.
This instance of the subset sum problem can be solved even faster: using bitsets for a factor 64 speedup, or even in \mathcal{O}(N\cdot \max(A)) (see this blog if you’re interested).
However, neither are needed to get AC in this task.
TIME COMPLEXITY:
\mathcal{O}(N\cdot sum(A)) per testcase.
CODE:
Setter's code (C++)
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define deb(x) cout<< #x << '=' << x <<endl
#define MOD 1000000007
const int N = 501;
ll n;
ll a[N] , cache[N][N * N];
ll dp(ll i , ll s){
if(s < 0){
return 0;
}
if(i >= n){
if(s == 0){
cache[i][s] = 1;
return 1;
}
cache[i][s] = 0;
return 0;
}
ll &ans = cache[i][s];
if(ans != -1){
return ans;
}
ll res = 0;
res |= dp(i + 1 , s - a[i]);
res |= dp(i + 1 , s);
return ans = res;
}
int main() {
ll t;
cin>>t;
assert(t <= 50 && t >= 1);
ll sumN = 0;
for(int tc = 0; tc < t; tc++){
cin>>n;
sumN += n;
assert(n >= 2 && n <= 300);
ll sum = 0;
for(int i = 0; i < n; i++){
cin>>a[i];
assert(a[i] >= 1 && a[i] <= 300);
sum += a[i];
}
if(sum % 2){
cout<<-1<<"\n";
continue;
}
for(int i = 0; i <= n; i++){
for(int j = 0; j <= sum; j++){
cache[i][j] = -1;
}
}
ll flag = dp(0 , sum/2);
if(flag){
set<ll> s1 , s2;
for(int i = 0; i < n; i++){
s2.insert(i);
}
ll i = 0 , s = sum/2;
while(i < n){
if(cache[i + 1][s - a[i]]){
s -= a[i];
s1.insert(i);
s2.erase(i);
}
i++;
}
vector<pair<ll , ll>> ans;
while(sz(s1)){
ll idx1 = *s1.begin() , idx2 = *s2.begin();
ll mn = min(a[idx1] , a[idx2]);
a[idx1] -= mn;
a[idx2] -= mn;
ans.pb({idx1 + 1 , idx2 + 1});
if(a[idx1] == 0){
s1.erase(idx1);
}
if(a[idx2] == 0){
s2.erase(idx2);
}
}
// assert(sz(ans) >= 0 && sz(ans) <= n);
cout<<sz(ans)<<"\n";
for(auto it : ans){
cout<<it.first<<" "<<it.second<<"\n";
}
}else{
cout<<-1<<"\n";
}
}
assert(sumN <= 600);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
target = sum(a)
if target%2 == 1:
print(-1)
continue
target //= 2
dp = [ [0 for _ in range(target+2)] for _ in range(n+1) ]
dp[0][0] = 1
for i in range(n):
for x in range(target+1):
dp[i+1][x] = dp[i][x]
if x >= a[i]: dp[i+1][x] |= dp[i][x - a[i]]
if dp[n][target] == 0:
print(-1)
continue
mark = [0]*n
cursum, pos = target, n
while pos >= 1:
if dp[pos-1][cursum - a[pos-1]] == 1:
mark[pos-1] = 1
cursum -= a[pos-1]
pos -= 1
ptr1, ptr2 = 0, 0
ops = []
while True:
while ptr1 < n and mark[ptr1] == 0: ptr1 += 1
while ptr2 < n and mark[ptr2] == 1: ptr2 += 1
if ptr1 == n: break
sub = min(a[ptr1], a[ptr2])
a[ptr1] -= sub
a[ptr2] -= sub
ops.append([ptr1+1, ptr2+1])
if a[ptr1] == 0: ptr1 += 1
if a[ptr2] == 0: ptr2 += 1
print(len(ops))
for x, y in ops:
print(x, y)
