algorithms

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

problem.txt (2351B)


      1 B. Sequence Decreasing
      2 time limit per test1 second
      3 memory limit per test256 megabytes
      4 
      5 Gracie Abrams - That's So True
      6 An array b
      7  of non-negative integers is called good if it can be turned into a non-empty array consisting only of zeros by performing the following operation any number of times (possibly zero):
      8 
      9 choose a non-empty subarray∗
     10  of b
     11  in which all elements are positive;
     12 decrease each element of this subarray by 1
     13 ;
     14 choose one element of this subarray and remove it from b
     15 , without changing the order of the remaining elements.
     16 You are given an array a
     17  of n
     18  non-negative integers. Find the maximum length of a good subsequence†
     19  of a
     20 , or report that a
     21  has no good subsequence.
     22 
     23 ∗
     24 An array c
     25  is a subarray of an array b
     26  if c
     27  can be obtained from b
     28  by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
     29 
     30 †
     31 A sequence c
     32  is a subsequence of a sequence a
     33  if c
     34  can be obtained from a
     35  by the deletion of several (possibly, zero or all) elements from arbitrary positions.
     36 
     37 Input
     38 Each test contains multiple test cases. The first line contains the number of test cases t
     39  (1≤t≤104
     40 ). The description of the test cases follows.
     41 
     42 The first line of each test case contains a single integer n
     43  (1≤n≤2⋅105
     44 ) — the length of the array a
     45 .
     46 
     47 The second line of each test case contains n
     48  integers a1,a2,…,an
     49  (0≤ai≤109
     50 ) — the elements of the array a
     51 .
     52 
     53 It is guaranteed that the sum of n
     54  over all test cases does not exceed 2⋅105
     55 .
     56 ---
     57 
     58 - thoughts:
     59     - good if b -> an array of all zeroes
     60     - operation
     61         - choose non-empty subarray in which all elements are positive
     62         - decrease each element by 1
     63         - remove one of these elements from the subarray
     64 
     65 ---
     66 
     67 1
     68 0
     69 
     70 return 1
     71 
     72 1
     73 1
     74 
     75 return 0
     76 
     77 ---
     78 
     79 3
     80 5 3 4
     81 
     82 5,3 -> 2
     83 
     84 2,4 -> 1
     85 
     86 1 -> 
     87 
     88 0
     89 
     90 ---
     91 
     92 5
     93 2 1 1 0 3
     94 
     95 2 1 1 3 -> 1 0 0 0
     96 
     97 ---
     98 
     99 - so basically can we get to zeroes?
    100     - how the fuck does that work?
    101 
    102 ---
    103 
    104 - can we make zeroes?
    105     - yes
    106         - iteratively select smallest element, matched with one other element and decrement
    107         - specifically, yes is true iff the number of non-zero elements >= lowestValue
    108     - no
    109         - under this case, we know the above conditional is not true
    110             - removing elements won't help us so we return 0