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