3
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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 \}$.

$\endgroup$
  • $\begingroup$ Hi Abel, Sorry for taking so long to respond to your answer. Can you post the recursive solution to the problem? I'm having trouble understanding how solving the problem for N - 1 helps in solving the problem for N, since at N we know that the cumulative sums will be equal, but at N - 1 they cannot be, so how why is N - 1 a problem instance? $\endgroup$ – Alexandre Mar 13 '13 at 15:47
  • $\begingroup$ The main problem is not one of the subproblems, precisely because we have the extra condition that N is assigned to X and Y. However, the answer to the problem is the number of ways of assigning integers in [1, N-1] as cumulative sums to A and B, in such a way that T-1 of them belong to A, and U-1 belong to B. So, the answer to the problem is the sum over all states with N-1, T-1, L-1. $\endgroup$ – Abel Molina Mar 16 '13 at 19:32
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.