codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2140C.md (2108B)


      1 Source: https://codeforces.com/problemset/problem/2140/C
      2 
      3 C. Ultimate Value
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Let's define a function $f(a)$ for an array $a$ of length $n$ as $$f(a) = \textrm{cost} + (a_1 - a_2 + a_3 - a_4 \cdots a_n)$$ where $\textrm{cost}$ is zero initially.
     22 
     23 Now consider the scenario where Alice and Bob are given an array $a$ of length $n$. They play a game taking at most $10^{100}$ turns alternately with Alice going first.
     24 
     25 In each turn, they must perform any one (only one) of the following operations:
     26 
     27 * End the game for both Alice and Bob.
     28 * Choose two indices $l,r$ with $1 \le l \le r \le n$ and swap $a_l$ and $a_r$; this adds $(r - l)$ to the $\textrm{cost}$.
     29 
     30 Assume that Alice tries to maximize $f(a)$ and Bob tries to minimize it.
     31 
     32 Your task is to determine the final value of $f(a)$ assuming both players play optimally.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     37 
     38 The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of the array $a$.
     39 
     40 The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.
     43 
     44 Output
     45 
     46 For each testcase, output a single integer — the final value of $f(a)$ assuming both players play optimally.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 5
     54 
     55 2
     56 
     57 1000 1
     58 
     59 5
     60 
     61 9 9 9 9 9
     62 
     63 4
     64 
     65 7 1 8 4
     66 
     67 6
     68 
     69 1 14 1 14 1 15
     70 
     71 9
     72 
     73 31 12 14 22 89 6 78 25 91
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 999
     80 13
     81 12
     82 -7
     83 265
     84 ```
     85 
     86 Note
     87 
     88 For the first testcase, it is optimal for Alice to end the game on her first turn.
     89 
     90 So the final value of $\textrm{cost} = 0$ and $f(a) = 0 + 1000 - 1 = 999$.
     91 
     92 For the fourth testcase, it is optimal for Alice to swap $a_1$ and $a_6$, and then it is optimal for Bob to end the game on his first turn.
     93 
     94 So the final value of $\textrm{cost} = 5$ and $f(a) = 5 + 15 - 14 + 1 - 14 + 1 - 1=-7$.