algorithms

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

problem.txt (3271B)


      1 C. All-in-one Gun
      2 time limit per test2 seconds
      3 memory limit per test256 megabytes
      4 You are developing a new shooter game, but since there are a lot of shooter games out there, you decide to have something unique in your game.
      5 
      6 You have an all-in-one gun that shoots bullets in a fixed order. There are n
      7  bullets in the magazine, the i
      8 -th of which deals ai
      9  damage. The enemy starts with h
     10  health and dies when its health becomes ≤0
     11 .
     12 
     13 The gun shoots one bullet per second. After firing all n
     14  bullets, it must reload, which takes k
     15  seconds. Reloading always restores the same sequence of bullets [a1,a2,…,an]
     16 . You cannot reload early; you must empty the magazine first. At the start, the magazine is already full.
     17 
     18 Before the fight begins, you may perform at most one swap: pick any indices 1≤i<j≤n
     19  and exchange ai
     20  with aj
     21 .
     22 
     23 Your task is to find the minimum number of seconds needed to kill the enemy, taking into account this optional single swap.
     24 
     25 Input
     26 Each test contains multiple test cases. The first line contains the number of test cases t
     27  (1≤t≤104
     28 ). The description of the test cases follows.
     29 
     30 The first line of each testcase contains three integer n
     31 , h
     32  and k
     33  (2≤n≤2⋅105
     34 , 1≤h,k≤109
     35 ) — the size of magazine, health of your enemy and time required to reload the magazine.
     36 
     37 The second line of each testcase contains n
     38  integers a1,a2,…,an
     39  (1≤ai≤109
     40 ).
     41 
     42 It is guaranteed that the sum of n
     43  does not exceed 2⋅105
     44  over all test cases.
     45 
     46 
     47 ---
     48 
     49 - bullet damage array a
     50 - a_i is damage done by bullet i
     51 - enemy has h health to start
     52 - one bullet per second
     53 - k seconds to reload
     54     - can't reload early
     55 - you may swap two bullets at the start a_i -> a_j a_j -> a_i
     56 
     57 ---
     58 
     59 
     60 5 10 1
     61 4 2 3 5 3
     62 
     63 n,h,k
     64 
     65 5 elements
     66 h = 10 == health start
     67 k = 1 == seconds to reload
     68 
     69 4 2 3 5 3
     70 
     71 swap: 2,5
     72 
     73 4 5 3 2 3
     74 
     75 shoot 1,2,3 that's it.
     76 
     77 3 seconds
     78 
     79 heuristic: find section from start that sums to 10. check each swap with smallest value in section and later values to see if this changes things
     80 
     81 ---
     82 
     83 5 10 1
     84 4 2 3 7 3
     85 
     86 5 elements
     87 10 health
     88 1 second reload
     89 
     90 4 2 3 7 3
     91 
     92 4+2+3+7 = 16
     93 
     94 smallest = 2
     95 
     96 2,3 swap does nothing
     97 2,7 swap decreases by 1
     98 ...
     99 
    100 4 7 3 2 3
    101 
    102 same heuristic as above, but the issue here is that we don't only care about the min value; if we could swap the first with a larger value even 
    103 if first > second and that'd finish the problem we should do that.
    104 
    105 ---
    106 
    107 3 10 2
    108 1 2 3
    109 
    110 two second reload
    111 10 health
    112 
    113 3 2 1
    114 
    115 3, 2, 1, (reload), 3, 2  -> 7
    116 
    117 ---
    118 
    119 2 5 3
    120 2 1
    121 
    122 2 elements, 3 second reload, 5 health
    123 
    124 since descending order do nothing.
    125 
    126 2,1,reload,2 -> 6
    127 
    128 ---
    129 
    130 3 18 5
    131 1 2 3
    132 
    133 3,2,1
    134 
    135 
    136 ---
    137 
    138 4 10 10
    139 1 1 2 2
    140 
    141 2,1,2,1
    142 
    143 ---
    144 
    145 idea:
    146 
    147 - compute sum of array
    148 - compute rem = health % sum
    149     - rem is then the amount of damage to be dealt in the last magazine
    150 - how to compute shortest array ordering that results in sum >= rem
    151     - compute default substring s.t. sum >= rem
    152         - from 0 -> len:
    153             - check if current where we swap smallest on left with largest on right (inclusive of current) would be > target
    154                 - if so, return this idx + (magTime * magsUsed)
    155             - if not continue
    156             - how to make this fast:
    157                 - compute max postfix (exclusive of current) and min prefix (inclusive)