In the editorial it was mentioned that upper bound of this problem will be in the order of $$$1000.2^{50}$$$.
But I am unable to understand why is that the case
1)How would the test case for the $$$sum = 1000.2^{50}$$$ would look like?
This is my understanding of the problem:
Apply operation 2 as operation-1 just reverses the array, which doesn't affect the array sum. Reversing and doing operation-2 will just change the sign of the sum.
if we were to reverse the original array and did operation-2
Keep repeating until we have single element left in $$$A$$$ From my point of view it just doesn't feel intuitive that sum could be the order of $$$1000.2^{50}$$$
тебе уже ничего не поможет
one way you can arrive at the intuition for doubling is the fact that if you have a and -a next to each other then in the difference array you would have -2a.
in this case the magic test case is
1000 -1000 +1000 -1000..... -1000
which in the next round would be
-2000 2000 -2000 2000 ... -2000
and so on where the $$$i^{th}$$$ round would have a factor of $$$2^i$$$ multiplied to it
Denote the maximum absolute value of array after $$$x$$$ operations of the second type as $$$f(x)$$$.
From the input, $$$f(0)=1000$$$.
Suppose we now know $$$f(x)$$$. How do we know an upper bound of $$$f(x+1)$$$? Now for the every two adjacent elements in the array $$$A$$$ operated $$$x$$$ times, $$$A_{i+1}-A_{i}\le f(x)-(-f(x))=2f(x)$$$. In other words, $$$f(x+1)\le 2f(x)$$$. It's easy to see for arbitrary $$$x$$$, $$$f(x)\le 1000\cdot 2^x$$$. In fact, the construction $$$A_i=1000{(-1)}^{i}$$$ reaches the maximum. So $$$f(x)=1000\cdot 2^x$$$
What about the sum? The absolute value of sum after $$$x$$$ operations cannot exceed $$$(n-x)f(x)$$$, which reaches the maximum at $$$x=n-1$$$, which is $$$f(n-1)=1000\cdot 2^{n-1}$$$.