How to find out upper bound for this problem

Revision en1, by dorasainath955, 2025-01-28 20:10:09

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

Tags constructive, brute force, logic, proof, math

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dorasainath955 2025-01-28 20:10:09 1067 Initial revision (published)