dorasainath955's blog

How to find out upper bound for this problem
By dorasainath955, history, 37 hours ago, In English

Problem

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:

$$$A = [a_1, a_2, ..., a_n]$$$
$$$ans = \sum{A}$$$

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.

$$$A = [a_2-a_1, ..., a_n-a_{n-1}]$$$
$$$\sum{A} = a_{n}-a_{1}$$$

if we were to reverse the original array and did operation-2

$$$A = [a_n, a_{n-1}..., a_1]$$$
$$$A = [a_{n-1}-a_{n}, ..., a_1-a_{2}]$$$
$$$\sum{A} = a_1-a_n$$$
$$$ans = max(sum, -sum, ans)$$$

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}$$$

  • Vote: I like it
  • -14
  • Vote: I do not like it

»
36 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

тебе уже ничего не поможет

→ Reply
»
34 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
29 hours ago, # |
  Vote: I like it +3 Vote: I do not like 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}$$$.

→ Reply