Google Kickstart 2019 Round G Shifts
We need to calculate the number of valid combinations that makes two guards happy. I first tried backtracking but it will have TL problem. In each node, we have three options, so in fact, we will have $3^{20}$ in the hidden set. We need to discard as many options as early as possible. As the max n is 20 less the 32 we can use bit representation for each combination. We first calculate valid a and b guard’s permutations separately. For each valid b guard’s permutation, we find also the number of permutation that can convert to that permutation flipping some zero bit to one. And then for each valid, a guard permutation finds the corresponding b guard’s permutation.
Pay attention that the sum of happiness may exceed 32 bit.