PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Jatin Yadav
Tester: Rahul Dugar
Editorialist: Mohammed Ehab
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
None
PROBLEM:
You have N piles of spoons, each containing A_i spoons. In one step, you can move x spoons from pile p to pile q, but if and only if x \le A_p \le A_q. That is, you can only move spoons from a smaller pile to a bigger one. Can you put all the spoons in pile 1? If so, find a way to do it in 2N steps.
EXPLANATION:
We want to understand when it’s possible to answer and when it’s not. Let’s look at the case where we have 2 piles. It’s clear that pile #2 has to be smaller than (or equal to) pile #1. Or in other words, pile 1 has to have at least half the spoons. How about N=3? Suppose pile #1 has less than a quarter of the spoons. Then, notice that moving the spoons from another pile to it can at most double its size. That’s because the other pile has to be smaller or equal. In math, if b \le a, a+b \le 2a. So no matter what you do, after moving another pile to pile #1, you move to the case where you have 2 piles and less than half the spoons, so there’s no solution.
Let the total number of spoons be S. You can see this argument generalizes to the following: at any moment in time, if we have i piles left (other than pile #1,) then the size of pile #1 has to be at least \frac{S}{2^i}. Otherwise, you’d keep doubling it and reducing the number of piles, until you end up with only it and another pile bigger than it, and then you’re stuck.
Now, sort the piles from 2 to N by their size. Let B_i=\frac{S}{2^{N-i+1}}. Then, A_N has to be at most B_N (that is, the greatest pile is limited by half the spoons.) Additionally, A_{N-1}+A_N has to be at most B_{N-1}+B_{N}. This is a little trickier to see. This just means: if you can combine all the piles up to N-2 together into pile #1, then this pile has to have at least a quarter of the spoons, so the remaining 2 piles have 3 quarters. In general, the suffix sums of A_i all have to be limited by the suffix sums of B_i; otherwise, it’s impossible.
I’ll now prove this condition is sufficient! Here’s the goal: we want to move from the state A_i+A_{i+1}+\ldots+A_N \le B_i+B_{i+1}+\ldots+B_N to a stronger state: A_i \le B_i. To do this, let’s iterate over the piles from biggest to smallest. Then, if A_i>B_i, try to move the excessive spoons to pile #N, but just make sure A_N \le B_N remains. If you still have excessive spoons, move them to pile #N-1, and then pile #N-2, and so on. Since the number of spoons in that suffix is less than or equal to B_i+B_{i+1}+\ldots+B_N, you’ll always be able to move the spoons around and make A_i \le B_i!
Now, this is great because it means that for each i, A_i is less than or equal to the number of spoons in the previous piles combined. So you can just add the piles one by one to pile #1, without worrying about the condition.
Alternative Solution
So the objective is to keep making the first pile bigger and bigger as soon as possible, so that it can “swallow” other piles. Since we’re moving spoons from smaller to bigger piles, it makes sense to look at the smallest pile (other than pile 1, of course.)
If it has less (or equal) spoons than pile 1, you can just move all these spoons to pile 1. Otherwise, all piles are strictly bigger than pile 1, and you can’t really move any spoons to it at this step. What you can do instead is: look at the difference in size between pile 1 and the smallest pile. Try to move these spoons from the smallest pile to the other piles. Then, move the rest to pile 1. The question is: how do you distribute these extra spoons exactly? I, and many people, guessed that you should just move them to the second biggest pile, and it passes the test cases. However, we don’t know a proof why this works. Can you provide one?
Bonus task: prove both solutions actually only use N+log(S) operations.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 1e5 + 5;
int n, sum = 0;
int a[N], b[N], sufA[N], sufB[N];
vector<int> p, q, x;
pair<int, int> copyA[N];
bool initialcheck()
{
sufA[n + 1] = 0, sufB[n + 1] = 0;
for(int i = n; i >= 2; i--)
{
sufA[i] = sufA[i + 1] + a[i];
sufB[i] = sufB[i + 1] + b[i];
if(sufA[i] > sufB[i])
return 0;
}
return 1;
}
void work(int i, int &idx, int toAdjust)
{
while(toAdjust > 0 && idx >= 2)
{
while(a[idx] == b[idx] && idx >= 2)
idx--;
int adjust = min(toAdjust, b[idx] - a[idx]);
a[idx] += adjust;
a[i] -= adjust;
p.push_back(copyA[i].second);
q.push_back(copyA[idx].second);
x.push_back(adjust);
toAdjust -= adjust;
}
}
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
sum = 0, p.clear(), q.clear(), x.clear();
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
sum += a[i];
copyA[i].first = a[i];
copyA[i].second = i;
}
int store = sum;
sort(a + 2, a + n + 1); //A[2] <= A[3]..
sort(copyA + 2, copyA + n + 1);
for(int i = n; i >= 1; i--)
{
b[i] = sum / 2;
sum = (sum + 1) / 2;
}
//check if sufBi < SufAi => if yes, print no
if(!initialcheck())
{
cout << -1 << endl;
continue;
}
//now, we first ensure Ai <= Bi for all i
int idx = n;
for(int i = n; i >= 2; i--)
{
if(a[i] > b[i])
work(i, idx, a[i] - b[i]);
}
int ops = 0;
for(int i = 2; i <= n; i++)
{
if(a[i] > 0)
{
ops++;
p.push_back(copyA[i].second), q.push_back(copyA[1].second), x.push_back(a[i]);
a[1] += a[i], a[i] = 0;
}
}
int mx = store, have = 0;
while(mx > 1)
{
have++;
mx = (mx + 1) / 2;
}
assert(ops <= have);
if(a[1] == store)
{
cout << p.size() << endl;
assert(p.size() <= n - 1 + have);;
for(int i = 0; i < p.size(); i++)
cout << p[i] << " " << q[i] << " " << x[i] << endl;
}
else
cout << -1 << endl;
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n;
long long f;
scanf("%d%lld",&n,&f);
set<pair<long long,int> > s;
for (int i=2;i<=n;i++)
{
long long a;
scanf("%lld",&a);
s.insert({a,i});
}
vector<pair<pair<int,int>,long long> > v;
while (!s.empty())
{
auto p=*s.begin(); //the smallest pile
s.erase(s.begin());
if (p.first<=f)
{
v.push_back({{p.second,1},p.first});
f+=p.first;
}
else //it's bigger than pile #1
{
if (s.empty()) //no solution because there's no pile to move the extra spoons to
{
v.clear();
break;
}
auto p2=*s.begin(); //second smallest pile
s.erase(s.begin());
v.push_back({{p.second,p2.second},p.first-f}); //move the extra spoons from smallest to second smallest
s.insert({p2.first+p.first-f,p2.second});
v.push_back({{p.second,1},f}); //move the rest to pile #1
f*=2;
}
}
if (v.empty())
puts("-1");
else
{
printf("%d\n",v.size());
for (auto p:v)
printf("%d %d %lld\n",p.first.first,p.first.second,p.second);
}
}
}
. Hope some one provides a rigorous proof/disproof for this.