PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Prefix sums
PROBLEM:
There are N chambers of water, the i-th has a temperature of a_i. The sum of all a_i equals 0. Adjacent chambers are separated by walls.
Every second, you lift one wall, causing the heat of the hotter side to reduce by 1 and the lower side to increase by 1. The wall is then placed back.
Find the minimum time required for all the chambers to have a temperature of 0.
EXPLANATION:
Consider the two adjacent chambers i and i+1.
There are a_1 + a_2 + \cdots + a_i units of heat till i, and a_{i+1} + a_{i+2} + \cdots + a_n units after it.
Note that since the sum of these values is 0, they must have the same absolute value, i.e.
|a_1 + \cdots + a_i| = |a_{i+1} + \cdots + a_n|
Let r_i denote this absolute value.
If all the elements of a are to be made 0, certainly we need to make at least r_i moves at this position, each one of which is necessary to move heat from one side to the other - a move at any other position won’t change the “balance” of heat across i.
Since we can only move temperatures between adjacent chambers, a natural lower bound on the answer is then r_1 + r_2 + \cdots + r_{n-1}, i.e, the sum of the minimum number of moves needed at every position.
It turns out that this lower bound is always achievable.
Proof
There’s a fairly simple strategy to achieve our goal.
If all the element of a are already 0, nothing needs to be done.
Otherwise, there must exist both a negative element and a positive element in a since its sum is 0.
Let the leftmost positive element be at position x, and the leftmost negative element be at position y.Then, operate on the wall separating \max(x, y)-1 and \max(x, y).
This will always move one unit of heat in the correct direction.
For example, if x \lt y, the prefix till y-1 will have positive sum and also a_{y-1} \geq 0, whereas a_y \lt 0; and the operation will move one unit from y-1 to y which is what we want.Since it’s always possible to make a necessary move when the array isn’t all zeros, the lower bound we found is achievable as claimed.
So, quite simply, the answer is simply \displaystyle\sum_{i=1}^{n-1} r_i, where \displaystyle r_i = \left|\sum_{j=1}^i a_j\right|.
Note that r_i is simply the absolute value of the i-th prefix sum of a, so to compute this quickly, find all prefix sums of a and then just add up their absolute values.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
vector<ll>vec(n);
for(ll&i:vec)cin>>i;
int p=0;
ll ans=0;
for(int i=0;i<n;i++)
{
while(vec[i]<0)
{
while(vec[p]<=0)p++;
ll val=min(vec[p],-vec[i]);
vec[p]-=val;vec[i]+=val;
ans+=val*abs(i-p);
}
}
cout<<ans<<"\n";
}
}
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];
vector<ll> p(n+5);
rep1(i,n) p[i] = p[i-1]+a[i];
ll ans = 0;
rep1(i,n) ans += abs(p[i]);
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
pref = ans = 0
for x in a:
pref += x
ans += abs(pref)
print(ans)