algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (3116B)


      1 D. Lock and Unlock
      2 time limit per test2 seconds
      3 memory limit per test256 megabytes
      4 You are given an integer array [a1,a2,…,an]
      5 . Initially, all the elements are unlocked.
      6 
      7 You may perform the following operation on array a
      8  any number of times (possibly zero):
      9 
     10 Choose an integer k
     11  (1≤k≤n
     12 ) and choose exactly k
     13  distinct indices. The elements at these indices are locked for the current operation. This step incurs a cost equal to k
     14 .
     15 
     16 Choose one of the following two actions:
     17 
     18 Increase every unlocked element by 1
     19 ;
     20 Decrease every unlocked element by 1
     21 .
     22 This step does not incur any additional cost.
     23 
     24 Unlock all the elements. This step does not incur any additional cost.
     25 The total cost is equal to the sum of the individual costs over all the operations performed.
     26 
     27 Determine the minimum possible total cost to make all the elements of the array a
     28  equal. Furthermore, among all the ways to achieve this minimum possible total cost, find the minimum number of operations required.
     29 
     30 Input
     31 The first line of the input contains a single integer t
     32  (1≤t≤2⋅104
     33 ) — the number of test cases. The description of each test case follows.
     34 
     35 The first line of each test case contains a single integer n
     36  (2≤n≤2⋅105
     37 ) — the length of the array a
     38 .
     39 
     40 The second line of each test case contains n
     41  integers a1,a2,…,an
     42  (−109≤ai≤109
     43 ) — the elements of the array a
     44 .
     45 
     46 It is guaranteed that the sum of n
     47  over all the test cases does not exceed 2⋅105
     48 .
     49 
     50 Output
     51 For each test case, print two space-separated integers on a new line — the minimum possible total cost to make all the elements equal, and the minimum number of operations required to make all the elements equal with the minimum possible total cost.
     52 
     53 ---
     54 
     55 [a_1,a_2,...,a_n] where all elements are locked
     56 
     57 can do this any number of times:
     58     - choose a number k >= 1 k <= n and choose k distinct indices all of these elements are locked, with a cost of k
     59     - choose one of the two actions
     60         1. increased every unlocked by 1
     61         2. decrease every unlocked by 1
     62     - unlock all elements
     63 
     64 - find min cost to make all elements equal
     65     - find the minimum number of operations required too, using min cost approach
     66 
     67 - constraints
     68     - 2000 test cases
     69     - 10_000 arr len max
     70     - numbers between -10^9 and 10^9
     71 
     72 - so we must do this in nlogn / linear time
     73 
     74 
     75 3
     76 1 2 3
     77 
     78 1 2 3
     79 
     80 lock 1, decrement
     81 
     82 1 1 2
     83 
     84 lock final element, increment
     85 
     86 2 2 2
     87 
     88 cost: 2
     89 ops: 2
     90 
     91 idea: find highest and lowest. find number of high and low elements and then move towards whichever one has less elements.
     92 sort first(?) order doesn't matter in terms of positions.
     93 
     94 ---
     95 2
     96 -1 -1
     97 
     98 cost: 0
     99 ops:  0
    100 
    101 ---
    102 4
    103 18 -2 9 11
    104 
    105 can start on either end. lock low
    106 
    107 
    108 17 -2 8 10
    109 
    110 16 -2 7 9
    111 
    112 ...
    113 
    114 7 -2 -2 0
    115 
    116 7 -1 -1 1
    117 
    118 7 0 0 2
    119 
    120 7 1 1 3
    121 
    122 7 2 2 4
    123 
    124 7 3 3 5
    125 
    126 7 4 4 6
    127 
    128 7 5 5 7 (cost 2)
    129 
    130 7 6 6 7 (cost 2)
    131 
    132 7 7 7 7 
    133 
    134 cost: 22 (2 additional at the end)
    135 
    136 18 -- 2 = 20
    137 
    138 note: number of operations == max - min or smt like that
    139 note: we can then compute the stepwise deltas between elements, using this as a multiplier for our selections
    140 
    141 ---
    142 9
    143 9 9 8 2 4 4 3 5 3
    144 ---
    145 3
    146 6 67 7
    147 ---