PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: watoac2001
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Prefix sums
PROBLEM:
You have an array A of length N.
Alice and Bob play a game on this array.
On their turn, a player will do the following:
- If the array has length 1, the game ends.
- If it’s Alice’s turn, she’ll choose (L, R) (1\leq L\leq R\leq |A|) and replace the elements A_L, A_{L+1}, \ldots, A_R by a single occurrence of the absolute value of their sum.
- If it’s Bob’s turn, he’ll choose (L, R) (1\leq L\leq R\leq |A|) and replace the elements A_L, A_{L+1}, \ldots, A_R by a single occurrence of their sum.
Alice wants to maximize the final element, while Bob wants to minimize it.
Under optimal play, who will win?
EXPLANATION:
Alice, on her move, cannot decrease the sum of the array - it will either remain the same (if she chooses a subarray with non-negative sum), or increase (if she chooses a subarray with negative sum).
Bob, on his move, cannot change the sum of the array at all.
Since Bob’s objective is to minimize the final element, it’s optimal for him to just choose the entire array on his very first move - allowing Alice to make further moves (or even making further moves himself) isn’t beneficial to minimizing the final element.
So, Alice has only a single move to work with, with her aim being to maximize the sum of the resulting array.
As noted at the start, the only way for Alice to increase the sum of the array is to choose some subarray with negative sum and perform the operation on it.
In particular, if Alice chooses a subarray with sum S, the overall sum of the array will increase by 2|S| after the operation (since we replace elements that sum to S, by a single instance of -S).
Clearly, to maximize the sum, it’s optimal for Alice to choose the minimum possible subarray sum (while also ensuring the chosen subarray has length \geq 2).
Computing the minimum subarray sum is easily done in linear time, in a variety of ways: Kadane’s algorithm, or even just by looking prefix sums.
Modifying these algorithms to exclude length-1 subarrays isn’t too hard either.
For example, the prefix sum approach to minimum subarray sum, while excluding length-1 subarrays, is as follows:
- Let P_i = A_1 + A_2 + \ldots + A_i denote the prefix sum array of A.
- Let M_i = \max(0, P_1, P_2, \ldots, P_i).
- Then, for each i = 2, 3, 4, \ldots, N, the minimum sum of a subarray ending at index i, whose length is at least 2, is exactly P_i - M_{i-2}.
So, just take the minimum of this across all i.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
ll kitne_cases_hain;
kitne_cases_hain=1;
cin>>kitne_cases_hain;
while(kitne_cases_hain--){
ll n;
cin>>n;
ll a[n];
ll sum=0;
ll best=0;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
ll ans=a[0];
for(int i=1;i<n;i++){
best=min(best,a[i]+ans);
ans=min(ans+a[i],a[i]);
}
ans=sum-2*best;
cout<<ans<<"\n";
}
return 0;
}
Tester's code (C++)
//****************************Template Begins****************************//
// Header Files
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<unordered_set>
#include<list>
#include<iterator>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<map>
#include<unordered_map>
#include<stdio.h>
#include<complex>
#include<math.h>
#include<chrono>
#include<cstring>
#include<string>
// Header Files End
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define umap unordered_map
#define uset unordered_set
#define lb lower_bound
#define ub upper_bound
#define fo(i,a,b) for(i=a;i<b;i++)
#define all(v) (v).begin(),(v).end()
#define all1(v) (v).begin()+1,(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define allr1(v) (v).rbegin()+1,(v).rend()
#define sort0(v) sort(all(v))
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
#define max3(a,b,c) max(max((a),(b)),(c))
#define max4(a,b,c,d) max(max((a),(b)),max((c),(d)))
#define min3(a,b,c) min(min((a),(b)),(c))
#define min4(a,b,c,d) min(min((a),(b)),min((c),(d)))
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define inf 9999999999999
#define endl '\n'
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
template<class key, class value, class cmp = std::less<key>>
// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod1 = 998244353;
const ll mod = 1e9 + 7;
const ll MOD = 1e18 + 1e16;
ll mod_mul(ll a, ll b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;}
ll inv(ll i) {if (i == 1) return 1; return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;}
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
ll pwr(ll a, ll b) {a %= mod; ll res = 1; while (b > 0) {if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;}
//****************************Template Ends*******************************//
//****************************Functions*******************************//
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const auto start_time = chrono::high_resolution_clock::now();
void output_run_time() {
// will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
auto end_time = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end_time - start_time;
cout << "\n\n\nTime Taken : " << diff.count();
#endif
}
int main() {
fio;
ll t;
cin >> t;
while (t--)
{
ll n;
cin>>n;
ll a[n],i,sum=0,min1=0;
vll psum(n+1);
fo(i,0,n)
{
cin>>a[i];
sum+=a[i];
psum[i]=a[i];
if(i)
{
min1=min(min1,a[i]+a[i-1]);
psum[i]+=psum[i-1];
}
}
vll max1(n+1);
max1[n-1]=psum[n-1];
for(i=n-2;i>=0;i--)
{
max1[i]=min(max1[i+1],psum[i]);
}
fo(i,0,n-1)
{
ll g=0;
if(i)
g=psum[i-1];
min1=min(min1,max1[i+1]-g);
}
cout<<sum-2*min1<<endl;
}
// output_run_time();
return 0;
}
//remove #define endl '\n' for lleractive problems
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
# alice can increase the sum, bob can't
# so it's in bob's best interest to not allow more than one move to alice
# alice will choose the minimum sum subarray to replace, if possible
pref = [0]
for x in a: pref.append(pref[-1] + x)
ans, mx = 10**18, 0
for i in range(1, n):
ans = min(ans, pref[i+1] - mx)
mx = max(mx, pref[i])
print(sum(a) - 2*min(0, ans))