codeforces-scrape

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

2275D.md (3540B)


      1 Source: https://codeforces.com/problemset/problem/2275/D
      2 
      3 D. Precision Alignment
      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 K1o0n volunteered to work as a teaching assistant in the physics department, and he was assigned $n$ training laboratories. In the $i$-th laboratory, there are three instruments; their readings are $a_i$, $b_i$, and $c_i$. The instruments are distinguishable, and the order in this triple is fixed: the first ($a_i$), the second ($b_i$), the third ($c_i$).
     22 
     23 One action is to choose the index of a laboratory $i$ and perform exactly one of the three adjustments:
     24 
     25 * $c_i \mathrel{+}= \operatorname{sgn}(a_i - b_i)$
     26 * $b_i \mathrel{+}= \operatorname{sgn}(a_i - c_i)$
     27 * $a_i \mathrel{+}= \operatorname{sgn}(b_i - c_i)$
     28 
     29 Here $\operatorname{sgn}(x)$ equals $1$ if $x \gt 0$, equals $-1$ if $x \lt 0$, and equals $0$ if $x = 0$.
     30 
     31 In other words, an adjustment shifts the reading of one instrument by one unit, and the direction of the shift is determined by the difference of the readings of the other two, taken in the order they are written: the earlier one minus the later one.
     32 
     33 The actions are performed one after another, and each adjustment looks at the readings that have been obtained by that moment. The same laboratory may be adjusted any number of times, and some may be left untouched altogether; in total, K1o0n is ready to make at most $k$ actions across all laboratories.
     34 
     35 The work will be evaluated by the worst laboratory:
     36 
     37 $$S = \min_{1 \le i \le n} (a_i + b_i + c_i),$$
     38 
     39 where the readings are taken after all actions. K1o0n wants to impress his colleagues, so he asks you to find the maximum $S$ he can achieve.
     40 
     41 Input
     42 
     43 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     44 
     45 The first line of each testcase contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^{18}$) — the number of laboratories and the maximum number of actions.
     46 
     47 The next $n$ lines of each testcase contain three integers $a_i$, $b_i$, and $c_i$ ($-10^9 \le a_i, b_i, c_i \le 10^9$).
     48 
     49 It is guaranteed that the sum of $n$ over all testcases does not exceed $2\cdot10^5$.
     50 
     51 Output
     52 
     53 For each testcase, output one integer — the maximum achievable value of $S$.
     54 
     55 Note that the answer may not fit into a 32-bit integer type. Use a 64-bit integer type (long long in C++, long in Java).
     56 
     57 Example
     58 
     59 Input
     60 
     61 ```
     62 5
     63 
     64 3 4
     65 
     66 -3 -1 -2
     67 
     68 1 3 5
     69 
     70 2 4 6
     71 
     72 3 4
     73 
     74 6 4 2
     75 
     76 6 7 0
     77 
     78 7 6 0
     79 
     80 3 1000000000000000000
     81 
     82 4 4 4
     83 
     84 1 5 9
     85 
     86 -1000000000 0 1000000000
     87 
     88 2 4
     89 
     90 1 2 3
     91 
     92 0 0 5
     93 
     94 4 3
     95 
     96 2 1 0
     97 
     98 4 4 5
     99 
    100 1 5 9
    101 
    102 7 -2 1
    103 ```
    104 
    105 Output
    106 
    107 ```
    108 -2
    109 
    110 14
    111 
    112 12
    113 
    114 6
    115 
    116 6
    117 ```
    118 
    119 Note
    120 
    121 In the first testcase, to obtain a minimum sum of all triples equal to $-2$, you need to add $\operatorname{sgn}(b_1 - c_1) = 1$ to $a_1$ four times. After that, the triplet $(a_1, b_1, c_1)$ will become $(1, -1, -2)$, and the sum of the remaining triplets was originally greater than $-2$. It can be shown that it is impossible to obtain a sum of $-1$ or higher with that many operations.
    122 
    123 In the second testcase, to obtain a minimum sum of all triples equal to $14$, it is necessary to add $\operatorname{sgn}(b_1 - c_1) = 1$ to $a_1$ $2$ times, add $\operatorname{sgn}(a_2 - c_2) = 1$ to $b_2$ once, and add $\operatorname{sgn}(a_3 - b_3) = 1$ to $c_3$.
    124 
    125 In the fourth testcase, it seems that it's impossible to improve the value of the second lab; however, it's not. We can make $b_2 \mathrel{+}= \operatorname{sgn}(a_2 - c_2)$, and we are out of the "stuck" position.