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