thoughts.txt (1065B)
1 - given integers n and k 2 - construct binary string s of length n such that 3 - the difference between the number of 0's and 1's is at most 1 4 - there are k pairs of adjacent equal characters in s 5 - k indices such that s_i = s_{i+1} 6 7 --- 8 9 - sum of n over testcases <= 200_000 10 11 --- 12 13 n = 5, k = 2 14 15 11001 16 17 approach: wrote out long string of 1's to make all of the matches then backtracked to satisfy the property that 18 we may only have k matching adjacent pairs, along with the count constraint. 19 20 this doesn't seem like a sensible approach as we're solving two constraints in the backtrack 21 22 --- 23 24 n = 4, k = 3 25 26 not possible, -1 27 28 --- 29 30 n = 6, k = 1 31 32 100101 33 34 - 1's and 0's are interchangeable in isomorphic sense 35 36 --- 37 38 5 0 39 40 10101 41 42 --- 43 44 7 3 45 46 1110010 47 48 --- 49 50 4 2 51 52 1100 53 54 --- 55 56 3 2 57 58 -1 59 60 61 --- 62 63 7 4 64 65 1110001 66 67 --- 68 69 start from the beginning, fill with 1's until we reach ceil(k / 2), fill with 0's until we reach k total pairs, alternating on the rest 70 71 --- 72 73 74 5 2 75 76 11001 good 77 78 79 4 3 80 81 11100 (-1) 82 83 6 1 84 85 110101 86 87 5 0 88 89 10101 90 91 7 3 92 93 1110010 94 95 4 2 96 97 1100 98 99 3 2 100 101 110 (-1) 102 103 7 4 104 105 1110001