Find the sum of consecutive elements efficiently - INOI 2015, Problem 1

Question

I was recently solving this problem from INOI 2015. In this problem, you are given two arrays A and B and a special sum for the given arrays for two indices i and j is A[i]+A[j] plus the sum of the elements in the B array with indices between i and j. If you want to have a detailed explanation, refer here: Link to question paper. The question paper gives some examples and formal formulas to make the question clearer.

So, I went ahead with a O(n^2) time algorithm which follows.

#include <iostream>
#include <cmath>
using namespace std;

#define rep(i,a,b) for(auto (i)=a;i<b;i++)
#define list(i,N) for(auto (i)=0;i<N;i++)

int main(){

    int N; cin >> N;
    int A[N]; list(i,N) cin >> A[i];
    int B[N]; list(i,N) cin >> B[i];
    int prefix[N]; prefix[0] = B[0]; rep(i,1,N) prefix[i] = prefix[i-1]+B[i];

    int maxSum = A[0];
    list(i,N){
        list(j,N){
            if(i == j) maxSum = max(maxSum,A[i]);
            else if(i < j) maxSum = max(maxSum, A[i] + A[j] + prefix[j-1] - prefix[i]);
            else if(i > j) maxSum = max(A[i] + A[j] + prefix[N-1] + prefix[j-1] - prefix[i], maxSum);
        }
    }

    cout << maxSum;

    return 0;
}

Basically I am computing prefix sums for the array B and going through all the pairs of indices i, j.

Now, since this code runs in a O(n^2) time, I get a TLE on the last test cases but I was expecting to atleast solve the problem for the subtask 1. However, to my disappointment, this code even fails the last test case of the first subtask and some other test cases scattered around in the other subtaskes that is a WA (Wrong Answer). It gives the correct answer on the first two test cases and one another though. I get a TLE (Time Limit Exceeded) on the rest. I referred to this discussion: Commonlounge and the O(n^2) algorithm by everybody is the same algorithm which I am using. I also wanted to optimize my code, but unfortunately I am having some trouble understanding how to do it in O(n) time. Which is why I needed some help. What is apparently wrong? Some helpful hints would be nice too :).

Any help would be really appreciated...

Thank you!

You can see this solution: https://www.codechef.com/viewsolution/12372794. It solves the problem in O(n) time. — shubhgkr, Dec 28 '19 at 11:32
You managed to neglect to mention what problem you are solving. You defined the tools (special sum), but not what your goal is. Also, you currently seem to be asking two questions when there should be one question per question; which are you asking here? Why is the answer incorrect, or how to approach the problem in O(n) time? (Sometimes correcting a slow implementation gives insights into writing a faster one.) — JaMiT, Dec 28 '19 at 14:44
@JaMiT I want help to know what is wrong in the code and how to build an efficient solution building up from the inefficient code.Thanks — Vasu090, Jan 02 '20 at 13:18
@Vasu090 That would be two questions. *There should be **one** question per question;* which one would you like answered here, and which are you going to start a new question for? (I'd recommend the "what is wrong" for now and the efficiency question for another question.) — JaMiT, Jan 02 '20 at 18:46
@JaMiT More specifically, then, I want to know what is wrong. Thanks — Vasu090, Jan 03 '20 at 09:42
@Vasu090 Good. Next step: tell us what the goal of your algorithm is. (Presumably the goal involves a "special sum" of some sort, but which *special sum*?) Then give us the input for which your code fails, the expected result, and the actual result. — JaMiT, Jan 04 '20 at 01:34
@JaMiT The algorithm I have implemented is a brute force solution ```O(n^2)``` solution. Note that the special sum can be calculated by fixing an index and then fixing another index *i,j* (two loops). What we want to find is the *special sum* which is the sum of ```A[i]+A[j]``` and the sum of the elements of B between those two indices. Note that we take modulo N that is we move from last element to first element talking of "between". — Vasu090, Jan 04 '20 at 04:20
(limit exceeded) Unfortunately, I can't access the input and thus the expected result and the actual result. I tried this code on the sample test cases provided and some other of my own. Thanks. — Vasu090, Jan 04 '20 at 04:20
@Vasu090 For the third time, **WHAT IS THE PROBLEM THAT YOU ARE SOLVING?** If you were just calculating a special sum for a given `i` and `j`, there would be no reason to consider anything more complex than a straight-forward linear approach. — JaMiT, Jan 04 '20 at 15:56
@JaMiT Sorry for the trouble. I did not get what you meant. The problem I am solving is to find the maximum special sum of two indices. That is, we need to find the maximum possible special segment sum of two indices. The special sum we are talking about is the sum of the array A values of the two indices and the sum of the indices between them in the array B. The indices are cyclic that is i=j,ij all are allowed. The goal of my algorithm is to compute the special sum of all pairs of indices and keeping track of the maximum value. The maximum value after the iterations is the answer. — Vasu090, Jan 04 '20 at 17:35
@Vasu090 That information should be edited into the question, as it is rather key to understanding what you are talking about. *(It might not be enough, though, to re-open the question, as questions asking why code is not working are supposed to provide a reproducible problem -- see [help/on-topic]. You might want to check your calculation of special sums for edge cases: things like negative values in the arrays, huge values in the arrays, indices wrapping around, indices at the extremes of `0` and `N-1`, etc.)* — JaMiT, Jan 04 '20 at 21:57

Find the sum of consecutive elements efficiently - INOI 2015, Problem 1

0 Answers0