3
$\begingroup$

Two arrays of natural numbers are given of length $n$ and $n - 1$:

e.g.

$A: [a_0, a_1,..., a_{n-1}, a_n]$

$B: [b_0, b_1, ..., b_{n-2}, b_{n-1}]$

All elements of $A$ are unique (can be in $B$), all elements of $B$ are unique (can be in $A$) and every element of $B$ is smaller than the sum of all elements of $A$.

Find a solution $S$ which is a reordering of $A$ (so f.e. for $n=2, S: [a_1,a_0,a_2]$) such that $S_0$ (0th element) is not in $B$, $S_0 + S_1$ is not in $B$, $S_0 + S_1 + S_2$ is not in $B$, etc.

for example:

$A: [1, 2, 3]$

$B: [1, 2]$

Possible solutions: $S: [3, 2, 1] \lor [3,1,2]$

Furthermore, there is always at least one solution (seems logical as $B$ contains one less element and all it's elements are smaller than the sum of $S$, but don't see how to prove this fact).

The algorithm I have right now is simply going through the permutations and backtracking if the solution doesn't work out. This takes too long but I'm having trouble finding an alternative. Is there some mathematical property I'm missing?

$\endgroup$
  • 2
    $\begingroup$ Can you share the source for this problem (where you encountered it)? $\endgroup$ – D.W. Oct 15 '17 at 22:36
  • $\begingroup$ Are the numbers in $A,B$ likely to be not too large? Have you tried applying dynamic programming? $\endgroup$ – D.W. Oct 15 '17 at 22:38
  • $\begingroup$ Thanks for the reply, nothing can be assumed about the size or numbers in $A$ or $B$ other than what was stated above. Also I'm not too familiar with dynamic programming but I think having a solution for $n$ doesn't imply it will also work for $n+1$ as the new element in $B$ could be any element in $A$. Furthermore with backtracking I'm only going through every permutation at most once. $\endgroup$ – user78773 Oct 15 '17 at 23:07
  • $\begingroup$ Seems likely that this comes from some programming contest. It's also on SO although the answer provided is simply backtracking search. $\endgroup$ – rici Oct 16 '17 at 17:39
  • $\begingroup$ Yet I believe it is a fairly interesting question. Actually the existence of at least one solution seems highly likely to be true but non-trivial. $\endgroup$ – Willard Zhan Oct 16 '17 at 19:30

Your Answer

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

Browse other questions tagged or ask your own question.