Atcoder ABC #125 problem D - flipping signs

#1

So i’ve been trying to understand this coded up solution, pasted below (and at the link https://github.com/MathProgrammer/AtCoder/blob/master/Contests/AtCoder%20Beginner%20Contest%20125/Programs/Flipping%20Signs.cpp)

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 1e5 + 5, NO_OF_ENDINGS = 2, WITH_MULTIPLIER = 0, WITHOUT_MULTIPLIER = 1;
long long sum_till[MAX_N][NO_OF_ENDINGS];

int main()
{
    int no_of_elements;
    cin >> no_of_elements;

    vector <long long> A(no_of_elements + 1);
    for(int i = 1; i <= no_of_elements; i++)
        cin >> A[i];

    sum_till[1][WITHOUT_MULTIPLIER] = A[1], sum_till[1][WITH_MULTIPLIER] = A[1];
    sum_till[2][WITH_MULTIPLIER] = -A[1] - A[2], sum_till[2][WITHOUT_MULTIPLIER] = A[1] + A[2];
    for(int i = 3; i <= no_of_elements; i++)
    {
        long long max_without_last_2 = max(sum_till[i - 2][WITHOUT_MULTIPLIER], sum_till[i - 2][WITH_MULTIPLIER]);

        sum_till[i][WITHOUT_MULTIPLIER] = A[i] + max(A[i - 1] + max_without_last_2, sum_till[i - 1][WITH_MULTIPLIER]);

        sum_till[i][WITH_MULTIPLIER] = -A[i] + max(-A[i - 1] + max_without_last_2, sum_till[i - 1][WITH_MULTIPLIER] + 2*A[i - 1]);
    }

    long long answer = max(sum_till[no_of_elements][WITH_MULTIPLIER], sum_till[no_of_elements][WITHOUT_MULTIPLIER]);
    cout << answer;

    return 0;
}

and I have a vague understanding of what’s going on. I get that you kind of look at the best possible sum excluding the last 2 elements, and then see the effect that flipping the last 2 or not has. The code inside the for loop (how the sum_till array is determined) is confusing me however. Any help in understanding it appreciated
Problem is at link D - Flipping Signs

#2

Although I am not going to help you understand the code above, I am going to give you a simpler approach to this problem.

Claim: For every A[i], let C[i] := |A[i]|. Let the sum of all C[i] and the minimum C[i] be \text{sum} and M, respectively. Then, the answer is either \text{sum} or \text{sum}-2M, depending on the situation.

For every i from 1 to N-1 (in that order), apply the operation on (A[i], A[i+1]) if A[i]<0. Notice that in the end, every A[i] will be nonnegative, maybe except for A[N].

If, after the iteration, A[N]\geq 0, then the answer is simplly \text{sum}.

Otherwise, let j be the index such that C[j] is smallest among all C[1...N]. Then, apply the operation on (A[N-1], A[N]), then on (A[N-2], A[N-1]), …, then on (A[j], A[j+1]). Notice now that B[j] will be the only negative number in the array afterwards. Then, the answer is \text{sum} - 2M.

2 Likes
#3

Thanks very much for the explanation and proof; actually this is the way i solved it, but looked for other solutions and found this DP-type solution which i couldn’t get my head around. I feel as if there’s something here of benefit and didn’t want to miss out on it. Is it perhaps at each step storing both the best poss sum until now with a sign on the current element and also without the sign?

#4

I think \texttt{sum\_till}[n][i] is the maximum sum given that:

  1. We only consider the first n elements.
  2. We either have to flip the last two or we don’t- this part is determined by i.

IMHO you aren’t missing out on anything, the complexity and memory complexities are basically the same as the “intended” solution.

1 Like