Find two sequences of integers that have sum N but that don't have sub-sequences starting at the head of equal sum

Question

This question arose from a discussion between a friend and I.

$A$ is a sequence of length $T$ where for any $a_i$ in $A$, $a_i \in \left\{{1, 2, 3}\right\}$

$B$ is a sequence of length $U$ where for any $b_i$ in $B$, $b_i \in \left\{{1, 2, 3}\right\}$

---

And the following conditions:

1) They possess equal sum,

$N = \sum_{\forall a \in A} a = \sum_{\forall b \in B} b$

---

2) They don't possess sub-sequences starting at the head of equal sum,

$\sum_{i=1}^c a_i \neq \sum_{i=1}^d b_i$

for any $c < T$ and $d < U$,

where $a_i \in A$ and $b_i \in B$

---

Question: For given $N$, find an algorithm that calculates in polynomial time the number of possible pairs $(A, B)$ that satisfy these conditions.

It's very easy to write an algorithm that satisfies condition 1) using dynamic programming, but I simply cannot figure out how to make it satisfy 2) as well.

Good luck!

Answer 1

You can solve this with dynamic programming as well.

To see this, first realize you can see this problem as splitting the numbers between $0$ and $N$ into two subsets $X$ and $Y$ (the cumulative sums) that cannot overlap except at $0$ and $N$ (and must overlap there), and where the difference between consecutive elements of a subset is at most 3.

Reformulating the problem this way, you can have the state of your dynamic programming be:

"The number of ways of splitting the numbers between $0$ and $i-1$ into two sequences in the fashion described in the second paragraph, where the the numbers in positions (i, i-1, i-2) have assignments (j,k,h)", with $3 \leq i \leq N-1$, and $(j,k,h) \in \{X,Y,None\}$.

Using the states for $i=k$ to compute the states for $i=k+1$, it does take $\Theta(N)$ time to compute this. Let me know if more details are required.

Edit: I had missed in the previous answer the fact that $T$ and $U$ are fixed. You can take care of this by adding in your state how many positions so far have assignment to $X$, and how many have assignments to $Y$. Sadly, this brings the complexity up to $\Theta(T*U*N)$. Also, note that the solution generalizes to a larger number of sequences, and their values being in a larger range $\{1, \ldots, k \}$.

Answer 2

This problem has an algorithm of time complexity that is polynomial in N, T and U (but not in polynomial in the size of N, T and U). This technicality is worth noting since the problem instances can be described by specifying just the integers T, U and N and hence strictly speaking the size of the input to this problem is O(log N + log T + log U). So in order to get a polynomial time algorithm, you should assume that the inputs are given in unary.

One can create an acyclic graph G with O(T*U*N) nodes with source s and sink t such that the number of paths from s to t is exactly the solution.