I came across this one problem,
There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same.
Write a program that given n1 1s, n2 2s, n3 3s, n4 4s will output the number of such sequences using all these numbers.
Output your answer modulo 1000000007 (10^9 + 7).
I can’t figure out the solution of this. Will this be done with DP or some kind of DFS with backtracking?
2
If I’m correct, the graph traversal solution is pretty straightforward: you may traverse the graph with recursive function memorizing only current “left” symbols and last used one.
- let there be a function
f
ofinput
(key-value pairs, where keys are1
..4
; values aren1
..n4
) andp
– last used number, andp
is initially undefined - in a loop, if
input[i] > 0
andi != p
, wherei
is a key- add 1 to result, because you found another solution, 1 symbol longer
- set
inputUpd := input
(copy for recursive call) - decrement
inputUpd[i]
, because we’ve just used symboli
and there is one such symbol less left - set
p := i
, because we’ve just usedi
- add the value of
f(inputUpd, p)
(recursive call with “smaller” input and last used symbol) to result
I couldn’t help myself, so here is the code in JS. Skip it if you want to figure out the solution yourself.
function f(input, prev) {
var acc = 0;
for (i in input) {
if (i != prev && input[i] > 0) {
var inputUpd = {};
for (j in input) {
inputUpd[j] = (j == i) ? (input[j] - 1) : input[j];
}
acc += 1 + f(inputUpd, i);
}
}
return acc;
}
f({'1': 1, '2': 1}) // -> 4: [1], [2], [1,2], [2,1]
f({'1': 1, '2': 2}) // -> 5: [1], [2], [1,2], [2,1], [2,1,2]
f({'1': 1, '2': 3}) // -> 5: same as before, but single `2` is leftover
f({'1': 1, '2': 1, '3': 2, '4': 2}) // -> 288
0