algorithms

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

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