Connection Status:
Competition Arena > SuccessiveSubtraction2

SuccessiveSubtraction2

SRM 654 · 2015-01-29 · by sigma425

SRM 654 · 2015-01-29 · by sigma425 · Brute Force
Class Name: SuccessiveSubtraction2
Return Type: int[]
Method Name: calc
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

One day, Maki found an expression written on the blackboard in her high school. The expression had the following form: "a[0] - a[1] - ... - a[n-1]". You are given the int[] a containing the numbers used in the expression, in order of appearance. Note that some of these numbers may be negative. For example, a={1,-3,5} represents the expression "1-(-3)-5".

Maki noticed she can change the value of the expression by inserting additional parentheses. For example, she can change "1-3-3-4-5" (which equals -14) to "1-(3-3-(4-5))" (which equals 0), or to "1-(3-3-4-5)" (which equals 10).

To keep things simple, Maki decided that she may add at most two pairs of parentheses. Given this rule, Maki wanted to produce a value that would be as large as possible. She quickly found the optimal solution for the above expression. (In this problem we do not care about its value.)

Then, her mischievous friend Niko entered the classroom and she started to alter the expression. Niko applied several consecutive changes. In the i-th change, she erased the number at position p[i] and replaced it by the new value v[i]. (Both changes and positions are numbered starting from 0.) You are given the int[]s p and v, each containing the same number of elements.

After each of Niko's changes, Maki quickly solved her problem for the new sequence. Note that she always solved it in her head, without actually adding any parentheses to the blackboard.

Return a int[] with as many elements as there were changes by Niko. For each i, element i of the return value should be the largest value Mako can produce from the expression after Niko's change number i.

Notes

  • Parentheses can only be used to change the order in which the subtractions are evaluated. For example, "1(-2-3)", ")(1-2-3", and "12(34-56)78" are not valid ways to add parentheses.

Constraints

  • a will contain between 1 and 2000 elements, inclusive.
  • p will contain between 1 and 2000 elements, inclusive.
  • p and v will contain the same number of elements.
  • All numbers in a and v will be between -100 and 100, inclusive.
  • All numbers in p will be between 0 and N-1, inclusive, where N is the number of elements in a.
Examples
0)
{1, 2, 3, 4, 5}
{1, 2, 0, 4, 3}
{3, 9, -10, 5, 1}
Returns: {10, 16, 5, 5, 2 }

This is how the expression looks like after each of Niko's changes: 1 - 3 - 3 - 4 - 5 1 - 3 - 9 - 4 - 5 (-10) - 3 - 9 - 4 - 5 (-10) - 3 - 9 - 4 - 5 (-10) - 3 - 9 - 1 - 5 (fixed) One optimal solution for the first expression is given in the problem statement.

1)
{-100, -100, -100, -100, -100}
{0, 1, 2, 3, 4}
{0, 0, 0, 0, 0}
Returns: {400, 300, 200, 100, 0 }

One optimal solution for the expression "0 - (-100) - (-100) - (-100) - (-100)" is not to add any parentheses at all. Alternately, we can change the expression to "((0 - (-100) - (-100) - (-100) - (-100)))" which still has the same value.

2)
{83, 0, 25, 21}
{0, 3, 2, 1, 3, 1, 2}
{10, -90, 33, 52, -100, 0, 45}
Returns: {56, 125, 133, 81, 91, 143, 155 }
3)
{1}
{0, 0, 0, 0}
{10, -10, 100, -100}
Returns: {10, -10, 100, -100 }

There is only one number. The value of the expression is always equal to this number.

4)
{-11, -4, 28, 38, 21, -29, -45, 11, -58, -39, 92, 35, -56, -6, 29, -2, 61, 10, -29, -63}
{19, 5, 3, 10, 4, 18, 5, 2, 0, 15}
{-19, 21, 7, -66, 38, -39, -22, 24, -32, 13}
Returns: {451, 443, 412, 440, 457, 467, 468, 464, 443, 458 }

Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SuccessiveSubtraction2 with a public method vector<int> calc(vector<int> a, vector<int> p, vector<int> v) · 72 test cases · 2 s / 256 MB per case

Submitting as anonymous