algorithms

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

thoughts.txt (2459B)


      1 - bitstring s of size n
      2 - perform exactly one operation consisting of two steps
      3     1. choose 1 or 0 with index 2 to n-1 and replace it with the opposite
      4         - note: may choose 0, first and last are immutable at this stage
      5     2. replace each maximal block of consecutive equal characters with one such character. 
      6         - maximal if it cannot be extended to the left or to the right by adding the same character
      7             - 100111011 -> 10101
      8                 - compress 00 and 111 and 11
      9                 - is that weird way to say runs?
     10         - yes, this is just weird wording to say select runs of the same character to maximally munch them
     11 
     12 ---
     13 
     14 constraints
     15 
     16 - 10000 test cases
     17 - 300000 length strings
     18 - 300000 is the sum of lengths over all tests
     19     - 300_000 ** 2 = 90_000_000_000
     20         - too big
     21 
     22 ---
     23 
     24 001
     25 
     26 we are forced to flip 2 or not so
     27 
     28 011
     29 
     30 can be 
     31 
     32 001
     33 011
     34 
     35 -> 01 
     36 -> 01
     37 
     38 ---
     39 
     40 000
     41 
     42 010
     43 000
     44 
     45 -> 010
     46 -> 0
     47 ret 2
     48 
     49 ---
     50 
     51 010
     52 
     53 000
     54 010
     55 
     56 0
     57 010
     58 
     59 ---
     60 
     61 - idea thus far
     62     - there's something about cases wherein flips can result in more outcomes
     63     - ohh, yeah, if you do a flip where the elements on both sides differ you increase the count
     64         - but then for subsequent turns this isn't the case as they then compress
     65         - this makes me think there's something about playing out the compression and then saying something of the sort that it's that size
     66             - + 1 maybe?
     67                 - not quite in some smaller cases
     68                     - might be related to left and right edges
     69                         - could also be bounded in small cases
     70 ---
     71 
     72 00010
     73 
     74 00010
     75 01010
     76 00110
     77 00000
     78 
     79 (default)
     80 
     81 010
     82 01010
     83 0
     84 
     85 = 3
     86 
     87 ---
     88 
     89 
     90 - baseline perm
     91 - swapping the central '1' in the run of three
     92 - swapping the 0 in between the 1 runs
     93 
     94 100111011
     95 
     96 
     97 (default)
     98 100111011
     99 110111011
    100 101111011
    101 100011011
    102 100101011
    103 100110011
    104 100111111
    105 100111001
    106 
    107 1010101
    108 101
    109 10101
    110 
    111 = 3
    112 
    113 idea:
    114     - just 1 + number of bits surrounded by opposite
    115         - uhh, no because then there are really long runs
    116             - so maybe just like the total number of runs of (length >= 3) + 1
    117 
    118 ---
    119 
    120 001011010
    121 
    122 0101010
    123 01010
    124 
    125 baseline 1
    126 can swap: 1 + 1 + 1 + 1
    127 = 4
    128 
    129 answer is 3 though because swapping the 1 in between the 0's and the 0 in between the ones seems to get compressed?
    130 
    131 001011010
    132 
    133 000011010
    134 001111010
    135 
    136 01010
    137 01010
    138 
    139 - is there some sort of 1010101 thing where we can only use that once?
    140     - actually yeah, it seems like that's exactly it
    141 
    142 ---
    143 
    144 1111
    145 
    146 1
    147 101
    148 = 2