FINALSALE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: yash_daga
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef knows that his store’s projected sales on the i-th day is A_i.
He can also close down his store on some day, doubling the sales on that day - but this will cause him to lose out on sales of all the following days.

Find the maximum possible sales he can achieve by acting optimally.

EXPLANATION:

If Chef chooses to close down his store on day i, his sales will be exactly

A_1 + A_2 + \ldots + A_{i-1} + 2A_i

Unfortunately, computing this directly using a loop for each i will result in an \mathcal{O}(N^2) algorithm, which is too slow.
To optimize it, notice that for each index, you only need the loop to know the sum of all the elements before it; so instead of recomputing this from scratch each time, it can be computed a bit more cleverly.

Let P_i denote the sum of all the elements before index i, that is P_i = A_1 +A _2 + \ldots + A_{i-1}.
Then,

  • P_1 = 0; and
  • For i\gt 1, we have P_i = P_{i-1} + A_{i-1}, since P_{i-1} includes the sum of all the elements upto index i-2 already!

This allows for the array P to be computed using a single for loop, since it only needs a single loop from 1 to N.

Once array P is computed, the answer is just the maximum value of P_i + 2A_i across all i which is easy to compute, again with a single loop.

Note that the array P computed here is essentially just the prefix sum array of A (shifted by one step), which is something that comes up very often when solving problems.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    before = 0
    for i in range(n):
        ans = max(ans, before + 2*a[i])
        before += a[i]
    print(ans)
2 
 Scanner sc = new Scanner(System.in);
 int t = sc.nextInt();
 while(t-- > 0){
   int n = sc.nextInt();
   int[] sales = new int[n];
   int max = Integer.MIN_VALUE;
   int sum = 0;
   for(int i = 0 ; i < sales.length ; i++){
       sales[i] = sc.nextInt();
	   max = Math.max(sum + sales[i]*2 , max   );
	   sum += sales[i];
   }
   max = Math.max(sum , max);
   System.out.println(max);
}

why this did not pass all testcases. please help someone

3

The answer can exceed the maximum value that int can store, so use long (or whatever 64-bit type Java has).
For reference, int can store values upto about 2\cdot 10^9, while long can store upto about 8\cdot 10^{18} (the exact values are 2^{31}-1 and 2^{63}-1).
In this problem the maximum answer is around 3\cdot 10^5 \times 10^9 \approx 3\cdot 10^{14} so int isn’t enough.

5

@usernametaken0
Because your final loop is printing each time the condition d + 2*b[i] > total is true. Say:

10 1 7 1

Total is 19

d + 2*b[i] is 20
when i = 0

d + 2*b[i] is 25
when i = 2

d + 2*b[i] is 20
when i = 3

You are printing the 3 of them. You should only print the maximal.

Plus, according the constraints, there’s a huge risk your variables overflow.

What you probably meant was:

#include <bits/stdc++.h>

#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define V(x) vector
#define YES cout<<"YES"<<endl
#define NO  cout<<"NO"<<endl
#define SORT(vec) sort(vec.begin(), vec.end())
#define REVERSE(vec) reverse(vec.begin(), vec.end())

using namespace std;

signed main() {
    FASTIO;

    int test;
    cin >> test;
    //cin.ignore();
    while(test--){

        long long a,total=0,d=0,e=0;
        cin>>a;
        long long b[a];

        FOR(i,0,a){
            cin >> b[i];
            total += b[i] ;
        }

    
        FOR(i,0,a){
            if( d + 2*b[i]> total ){
                //cout<<d + 2*b[i]<<endl ;
                total = d + 2*b[i];
            }
            d += b[i];
        }
    
        cout << total << endl;
    }
    return 0;
}
1 Like