Reduction from 3SUM problem to 3ARR-ARITH problem

The 3SUM problem is defined as follows. Given an array A[1...n] of numbers, determine whether there exist i,j,k in {1,..., 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,...s, 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] + 1
    Y[i] = 10 * B[i] + 2
    Z[i] = 10 * C[i] - 3
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 know how to show this algorithm is correct.

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.

How many English words
do you know?
Test your English vocabulary size, and measure
how many words do you know
Online Test
Powered by Examplum