Пареальная сумма n чисел в неупорядоченном порядке

Ответ 1

Пусть B - список попарных сумм с B[0] <= B[1] <= ... <= B[m-1] и A - исходный список чисел, который мы пытаемся найти, с A[0] < A[1] < ... < A[n-1], где m = n(n-1)/2.

Учитывая A[0], вычислите A в полиномиальное время

Постройте A от наименьшего элемента к самому большому. Предположим, что мы уже знаем A[0]. Тогда, поскольку B[0] - наименьший элемент в B, он может возникать только как A[0] + A[1]. Аналогично, B[1] должен быть равен A[0] + A[2]. Поэтому, если мы знаем A[0], мы можем вычислить A[1] и A[2].

После этого, однако, этот шаблон распадается. B[2] может быть либо A[0] + A[3], либо A[1] + A[2] и без предварительного знания, мы не можем знать, какой из них он есть. Однако, если мы знаем A[0], мы можем вычислить A[1] и A[2], как описано выше, а затем удалить A[1] + A[2] из B. Тогда следующий наименьший элемент будет A[0] + A[3], что позволяет найти A[3]. Продолжая так, мы можем найти все A, не возвращаясь назад. Алгоритм выглядит примерно так:

for i from 1 to n-1 {
    // REMOVE SEEN SUMS FROM B
    for j from 0 to i-2 {
        remove A[j]+A[i-1] from B
    }
    // SOLVE FOR NEXT TERM
    A[i] = B[0] - A[0]
}
return A

Вот как это работает из вашего примера, где B = [4,5,7,10,12,13], если мы знаем A[0]=1:

start
    B = [4,5,7,10,12,13]
    A[0] = 1

i=1: 
    B = [4,5,7,10,12,13]
    A[1] = 4-1 = 3

i=2:
    Remove 1+3 from B
    B = [5,7,10,12,13]
    A[2] = 5-1 = 4

i=3:
    Remove 1+4 and 3+4 from B
    B = [10,12,13]
    A[3] = 10-1 = 9

end
    Remove 1+9 and 3+9 and 4+9 from B
    B = []
    A = [1,3,4,9]

Итак, все сводится к знанию A[0], из которого мы можем вычислить остальную часть A.

Вычислить A[0] в полиномиальное время

Теперь мы можем просто попробовать любую возможность для A[0]. Поскольку мы знаем B[0] = A[0] + A[1], мы знаем, что A[0] должно быть целым числом между 0 и B[0]/2 - 1. Мы также знаем, что

B[0] = A[0] + A[1]
B[1] = A[0] + A[2]

Кроме того, существует некоторый индекс i с 2 <= i <= n-1 такой, что

B[i] = A[1] + A[2]

Почему? Поскольку единственные записи, потенциально меньшие, чем A[1]+A[2], имеют вид A[0] + A[j] и не более n-1 таких выражений. Поэтому мы также знаем, что

A[0] = (B[0]+B[1] - B[i])/2

для некоторого 2 <= i <= n-1. Это, вместе с тем, что A[0] лежит между 0 и B[0]/2-1, дает лишь несколько возможностей для тестирования A[0].

В качестве примера для A[0] существует две возможности: 0 или 1. Если мы попробуем алгоритм с A[0]=0, вот что получится:

start
    B = [4,5,7,10,12,13]
    A[0] = 0

i=1: 
    B = [4,5,7,10,12,13]
    A[1] = 4-0 = 4

i=2:
    Remove 0+4 from B
    B = [5,7,10,12,13]
    A[2] = 5-0 = 5

i=3:
    Remove 0+5 and 4+5 from B
    B = !!! PROBLEM, THERE IS NO 9 IN B!

end

Ответ 2

Некоторые подсказки:

• Размер ввода - N * (N-1)/2, поэтому вы можете вывести размер вывода (т.е. 6 элементов на входе соответствуют 4 элементам на выходе)

• Сумма ввода - это сумма выхода, деленная на N - 1 (т.е. 1+3+4+9 = (4+5+7+10+12+13) / (4-1))

• Самые младшие входные и самые высокие входы представляют собой сумму двух наименьших и двух наивысших выходов соответственно (т.е. 4 = 1 + 3 и 13 = 4 + 9)

• Следующий самый низкий вход (5) отличается только одним добавлением от первого (1), поэтому вы можете вычислить один из слагаемых, принимая разницу (5-1).

Ответ 3

a + b ≤ a + c
a + b ≤ a + d
a + c ≤ b + c
a + d ≤ b + d
a + d ≤ c + d
b + c ≤ b + d
b + d ≤ c + d

Если бы это был полный порядок, тогда можно было бы узнать каждое из шести значений a + b, a + c, a + d, b + c, b + d и c + d. Затем можно было бы следовать первоначальному плану Фердинанда и легко решить одновременные уравнения.

К сожалению, существует пара (a + d, b + c), которую можно упорядочить в любом случае. Но это достаточно легко справиться: предположим, что a + d < b + c (входные значения различны, поэтому вам не нужно беспокоиться об использовании ≤) и попытайтесь решить одновременные уравнения. Тогда предположим b + c < a + d и повторите. Если обе системы уравнений имеют решение, то исходная задача имеет два ответа. Если ни один из них не имеет решения, выход должен быть -1. В противном случае у вас есть свое (уникальное) решение.

Ответ 4

Подход PengOne к восстановлению A [0] и B хорош, но есть лучший способ вычислить A [0]. Обратите внимание, что два наименьших элемента B:

B[0] = A[0] + A[1]
B[1] = A[0] + A[2]

и

B[i] = A[1] + A[2]

для некоторого i.

Таким образом,

A[0] = (B[0] + B[1] - B[i]) / 2

для некоторого i, и нам просто нужно попробовать возможности O (n ^ {1/2}), так как я ограничено O (n ^ {1/2}) и посмотрим, приводит ли оно к допустимой настройке из оставшихся элементов решения A на PengOne. Общее время работы - O (n ^ {3/2}), где n - количество чисел на входе.

Ответ 5

Недавно я проверял вопросы интервью, и я решил проблему с помощью подсказки @PengOne для поиска первого значения,

Итак, если кто-то нуждается в полном рабочем решении: Это в PHP:

сложность времени: O ((n * (n-2)) + 3 + n) со вспомогательными переменными. космическая сложность: почти такая же, как и во времени.

<?php
function getSublistSize($length)
{
    $i = 2;
    $n = 0;

    while ($i <= $length) {
        if (is_int($length / $i)) {
            if ($length == $i * ($i + 1) / 2) {
                return ($i + 1);
            }
        }

        ++$i;
    }

    return $n;
}

function findSubstractList(array $list)
{
    $length = count($list);

    $n = getSublistSize($length);
    $nth = $n - 1;

    $substractList = [];
    $substractTotal = array_sum($list) / ($length / 2); // A + B + C + D

    /**
     * formula : A = (list[0] + list[1] - list[nth -1]) / 2
     * list[0] = A + B,
     * list[1] = A + C,
     * list[nth - 1] = B + C
     *
     * =>  ((A + B) + (A + C) - (B + C)) / 2
     * => (A + A + (B + C - B - C)) / 2
     * => (2A + 0) / 2 => 2A / 2
     * => A
     */
    $substractList[] = (($list[0] + $list[1]) - $list[$nth]) / 2;

    for ($i = 0; $i < $nth; ++$i) {
        $substractList[] = ($list[$i] - $substractList[0]);
    }

//    $substractList[3] = $substractTotal - ($list[$nth - 1] + $substractList[0]);


    return $substractList;
}


$list = [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];

print_r(findSubstractList($list));

/**
 * P ) [6, 11, 101, 15, 105, 110];
 * S ) [1, 5, 10, 100]
 *
 * P ) [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];
 * S ) [1, 4, 7, 13, 27, 39]
 *
*/

Ответ 6

Я не уверен в самом быстром алгоритме, но я могу объяснить, как это работает.

Первое число o/p, является разницей между первым и вторым i/p

5-4=1

так что теперь у вас есть первый номер o/p.

Второе число o/p - первое i/p минус первое o/p.

4-1=3

третья часть o/p - вторая o/p минус первая i/p

5-1=4