algorithms

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

problem.txt (1610B)


      1 - a consists of n integers
      2 - a_i \in 4,8,15,16,23,42
      3 - remove the minimum number of elements to make good
      4 - good:
      5     - length is divisible by 6
      6     - can split into k/6 subsequences 4,8,15,16,23,42
      7 - return number of removals necessary.
      8 
      9 ---
     10 
     11 - how to:
     12     - from left to right:
     13         - mark number of elements not in the correct ordering
     14         - return this number
     15     - issue:
     16         - sometimes we don't finish the sequence
     17             - in such cases, deduct number of elements that have been found that aren't part of a full seq
     18     - nope:
     19         - subsequences can be dis-continuous
     20             - instead of the prior:
     21                 - we basically iterate and create a vector for each of the 4 elements we find
     22                     - (don't allocate full vector in case there's an adverserial 4,4,4,4,4,.... example)
     23                     - as we go, we then try to append a given element to one of the arrays as the next element
     24                         - if this isn't possible increment removal counter
     25                         - if a vector is filled with the 42nd element, clear it from our list of lists
     26             - return removalCounter + numberOfElementsInVectors
     27 ---
     28 
     29 Examples:
     30 
     31 ex1:
     32 4 8 15 16 23
     33 
     34 marked = 0
     35 queue: 4
     36 queue: 4, 8
     37 queue: 4, 8, 15
     38 queue: 4, 8, 15, 16
     39 queue: 4, 8, 16, 16, 23
     40 
     41 return marked + len(queue)
     42 
     43 -> 5
     44 
     45 ---
     46 
     47 ex2:
     48 4 8 4 15 16 8 23 15 16 42 23 42
     49 
     50 target = 4,8,15,16,23,42
     51 
     52 [4]
     53 
     54 [4,8]
     55 
     56 [4,8]
     57 [4]
     58 
     59 [4,8,15,16,23,42] -> []
     60 [4,8,15,16,23,42] -> []
     61 
     62 
     63 ---
     64 
     65 ex3:
     66 
     67 4 8 4 8 15 16 8 16 23 15 16 4 42 23 42
     68 
     69 bad = 2
     70 [4,8,15,16,23,42] -> []
     71 [4,8,15,16,23,42] -> []
     72 [4]
     73 
     74 return 3