Ребята, помогите мне заснуть... Не получается =(
Проблема в следующем. Есть задача 3-SUM, выбрать в массиве 3 элемента, дающие в сумме 0. https://en.wikipedia.org/wiki/3SUM
И вроде она не решается за O(n^{2-eps}). Но, если все числа целые от 1 до С, то задача решается FFT за O(n + ClogC). Более того: с помощью FFT вроде можно за O(n + ClogC + k) (возможно, тут Clog^2C) найти все тройки, с суммой 0, где k — число таких троек.
Так вот, давайте возьмём случайное простое P порядка n^{1.5}, и найдём все тройки, дающие 0 по модулю P, переберём их, проверим, что какая-то даёт просто 0, уже без модуля. Всего троек n^3, если они распределятся по остаткам более-менее равномерно, мы решили задачу за n^{1.5} на полилог. Неужели, если я буду брать случайное P в диапазоне [n^{1.5} - n ... n^{1.5} + n], всегда будет получаться большой бакет чисел кратных P? Вроде бы, чтобы так было, как минимум исходные числа должны быть длины n....
Помогите найти лажу. Помогите Серёже заснуть.
P.S. Кстати, если троек, дающих ноль, асимптотически хотя бы n^{eps}, то мы с вероятностью 1/n^{1-eps} угадаем первое число, и матожидание времени работы стандартного решения двумя указателями равно n^{2-eps} .
UPD: неужели лажа только в том, что после FFT мы таки не сможем за +k перечислить тройки, только за k*n^{0.5}? интересно, как про неё проверить, известность свойства "3-sum-hardness".
Проблема в следующем. Есть задача 3-SUM, выбрать в массиве 3 элемента, дающие в сумме 0. https://en.wikipedia.org/wiki/3SUM
И вроде она не решается за O(n^{2-eps}). Но, если все числа целые от 1 до С, то задача решается FFT за O(n + ClogC). Более того: с помощью FFT вроде можно за O(n + ClogC + k) (возможно, тут Clog^2C) найти все тройки, с суммой 0, где k — число таких троек.
Так вот, давайте возьмём случайное простое P порядка n^{1.5}, и найдём все тройки, дающие 0 по модулю P, переберём их, проверим, что какая-то даёт просто 0, уже без модуля. Всего троек n^3, если они распределятся по остаткам более-менее равномерно, мы решили задачу за n^{1.5} на полилог. Неужели, если я буду брать случайное P в диапазоне [n^{1.5} - n ... n^{1.5} + n], всегда будет получаться большой бакет чисел кратных P? Вроде бы, чтобы так было, как минимум исходные числа должны быть длины n....
Помогите найти лажу. Помогите Серёже заснуть.
P.S. Кстати, если троек, дающих ноль, асимптотически хотя бы n^{eps}, то мы с вероятностью 1/n^{1-eps} угадаем первое число, и матожидание времени работы стандартного решения двумя указателями равно n^{2-eps} .
UPD: неужели лажа только в том, что после FFT мы таки не сможем за +k перечислить тройки, только за k*n^{0.5}? интересно, как про неё проверить, известность свойства "3-sum-hardness".
Guys, help me fall asleep ... It does not work = (
The problem is as follows. There is a 3-SUM task, select 3 elements in the array, giving a total of 0. https://en.wikipedia.org/wiki/3SUM
And like she does not dare for O (n ^ {2-eps}). But, if all numbers are integers from 1 to C, then the problem is solved by FFT in O (n + ClogC). Moreover: with the help of FFT, it is possible to find all triples in O (n + ClogC + k) (perhaps here Clog ^ 2C), with the sum of 0, where k is the number of such triples.
So, let's take a random prime P of order n ^ {1.5}, and find all triples that give 0 modulo P, iterate over them, check that some one gives just 0, already without a module. Only triples of n ^ 3, if they are distributed over the residues more or less evenly, we solved the problem for n ^ {1.5} on the polylogue. Really, if I take a random P in the range [n ^ {1.5} - n ... n ^ {1.5} + n], will there always be a large bucket of multiples of P? It seems that so it was, at least the source numbers must be of length n ....
Help find get along. Help Sergei to fall asleep.
P.S. By the way, if the triples giving zero are asymptotically at least n ^ {eps}, then with probability 1 / n ^ {1-eps} we guess the first number, and the expectation of the standard solution running time with two pointers is n ^ {2-eps} .
UPD: Is it really just crap that after FFT we still cannot list triples for + k, only for k * n ^ {0.5}? I wonder how to check about it, the popularity of the property "3-sum-hardness".
The problem is as follows. There is a 3-SUM task, select 3 elements in the array, giving a total of 0. https://en.wikipedia.org/wiki/3SUM
And like she does not dare for O (n ^ {2-eps}). But, if all numbers are integers from 1 to C, then the problem is solved by FFT in O (n + ClogC). Moreover: with the help of FFT, it is possible to find all triples in O (n + ClogC + k) (perhaps here Clog ^ 2C), with the sum of 0, where k is the number of such triples.
So, let's take a random prime P of order n ^ {1.5}, and find all triples that give 0 modulo P, iterate over them, check that some one gives just 0, already without a module. Only triples of n ^ 3, if they are distributed over the residues more or less evenly, we solved the problem for n ^ {1.5} on the polylogue. Really, if I take a random P in the range [n ^ {1.5} - n ... n ^ {1.5} + n], will there always be a large bucket of multiples of P? It seems that so it was, at least the source numbers must be of length n ....
Help find get along. Help Sergei to fall asleep.
P.S. By the way, if the triples giving zero are asymptotically at least n ^ {eps}, then with probability 1 / n ^ {1-eps} we guess the first number, and the expectation of the standard solution running time with two pointers is n ^ {2-eps} .
UPD: Is it really just crap that after FFT we still cannot list triples for + k, only for k * n ^ {0.5}? I wonder how to check about it, the popularity of the property "3-sum-hardness".
У записи 14 лайков,
0 репостов.
0 репостов.
Эту запись оставил(а) на своей стене Sergey Kopeliovich
