1
$\begingroup$

The 3SUM problem is defined as follows. Given an array A[1...n] of numbers, determine whether there exist $i,j,k\in \{1,\cdots, n\}$ so that $A[i] + A[j]+A[k] = 0$.

The 3ARR-ARITH problem is defined as follows. Given three arrays $A[1..n], B[1..n], C[1...n]$ of numbers, determine whether there exist $i,j,k \in \{1,\cdots, n\}$ so that $B[j] - A[i] = C[k] - B[j].$

When reducing from problem P1 to problem P2, you assume you have a subroutine that solves problem P2 and use this subroutine to solve P1.

Determine a linear time reduction from 3SUM to 3ARR-ARTIH.

Determine a linear time reduction from 3ARR-ARITH to 3SUM.

I know a linear time reduction from 3ARR-SUM to 3SUM, where 3ARR-SUM is defined as follows: Given three arrays $A[1...n], B[1...n], C[1...n]$ of numbers, determine whether there exist $i,j,k$ so that $A[i]+B[j]+C[k] = 0$.

The reduction can be described by the following algorithm, where 3SUM is a subroutine that solves the 3SUM problem:

3ARR-SUM(A[1...n], B[1...n], C[1...n]):
for i = 1 to n do
    X[i] = 10 * A[i] + 2
    Y[i] = 10 * B[i] + 4
    Z[i] = 10 * C[i] - 6
let A' be an array of 3n 0's
for i = 1 to 3n do
    if (i <= n)
        A'[i] = X[i]
    else if (i <= 2n)
        A'[i] = Y[i]
    else
        A'[i] = Z[i]
if 3SUM(A'[1...3n]) returns (i,j,k) then
    sort (i,j,k) so that i <= j <= k
    return (i, j - n, k - 2n)

I tried rearranging the expressions for 3SUM and 3ARR-ARITH, but it doesn't seem like that helps. I can't think of something similar to the above either. How would I obtain a single array that 3SUM can solve and for which calling 3SUM on the array will solve 3ARR-ARITH?

Also, I can't seem to figure out how to reduce 3SUM to 3ARR-ARITH. It doesn't seem like defining the arrays A,B,C as follows works: $A[i] = 10A'[i] + 1, B[j] = 10B'[j] + 2, C[k] = 10C'[k] + 3$. I have a single array $A'[1..n]$ and I want to obtain 3 arrays $A[1...n], B[1...n], C[1...n]$ so that if I call 3ARR-ARITH on these 3 arrays, I will get indices $i,j,k$ so that $B[j] - A[i] = C[k] - B[j] $ and $A'[i] + A'[j] + A'[k] = 0.$

$\endgroup$
3
  • $\begingroup$ Where did you encounter this? We require that you attribute the source of all copied material. Please see our guidelines and edit your question accordingly: cs.stackexchange.com/help/referencing. I notice that I've given you this feedback before: cs.stackexchange.com/questions/140827/… $\endgroup$
    – D.W.
    Jan 13 at 7:44
  • $\begingroup$ Please don't delete your question after you have received an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future, and answerers may be answering on that basis, so deleting the question after someone answers can potentially be viewed as impolite to whoever takes time to answer. $\endgroup$
    – D.W.
    Jan 14 at 8:15
  • $\begingroup$ Cross-posted: stackoverflow.com/q/70691591/781723. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Jan 14 at 8:20

1 Answer 1

2
$\begingroup$

Let's rewrite the pattern we're looking for in 3ARR-ARITH: $$ A[i] - 2B[j] + C[k] = 0. $$ This should suggest a simple reduction from 3SUM to 3ARR-ARITH, and another simple reduction from 3ARR-ARITH to 3ARR-SUM, which combined with the reduction you mention, results in a reduction from 3ARR-ARITH to 3SUM.

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