Количество отрезков в квадратной решетке

[malphunction]

Мучаюсь с одной олимпиадной задачей, подскажите, в какую сторону копать? Что почитать?

Дана квадратная решетка со стороной N (т.е. множество точек $(x,y)$, таких, что $x,y \in \{0, \ldots, N\}$).
Необходимо найти количество отрезков внутри этой решетки, каждый из которых состоит хотя бы из трёх точек (например, отрезок $\< (5,1), (6,2), (11,7)\>$ подходит).

Можно было бы найти все эти отрезки перебором, но проблема в том, что N -- очень большое, порядка $10^{10}$ степени.

Посоветуйте направление поиска!


Единственное, что я смог придумать, это примерно такое:

Будем искать количество отрезков в прямоугольной решетке $N \times k$ , исходящих из начала координат. Для этого будем переберём все взаимно-простые пары чисел по алгоритму отсюда: https://en.wikipedia.org/wiki/Coprime_integers (раздел "Generating all coprime pairs"). Каждая пара чисел задаёт начало отрезка. Для каждой такой пары $(i,j)$ смотрим, может ли линия $(0,0) - (i,j)$ продолжена дальше до следующих двух, входящей в прямоугольник, точек. Если можно, учитываем эту линию, и считаем количество отрезков на ней.

Теперь, когда мы можем вычислить количество отрезков из начала координат в прямоугольной решетке, можно перейти к общему решению, посчитав количество отрезков в прямоугольнике $(N,1)$, затем $(N, 2)$ и до $(N,N)$.

Проблема, как вы видите, в том, что алгоритм этот кубический, что на больших $N$ сводит всю идею на нет.

Сами отрезки не важны, важно их количество.

Как же решить эту задачу?

[nikvic]

Может, через рациональность тангенсов и несократимость выражающих их дробей?

[venco]

Для каждого подходящего отрезка из начала координат надо просто сразу посчитать количество так же ориентированных отрезков по всему полю - это тривиально.
Не забудьте ещё, что есть отрезки и с другим наклоном, которые нельзя приставить к началу координат.

[Sonic86]

malphunction в сообщении #725455 писал(а):

Необходимо найти количество отрезков внутри этой решетки, каждый из которых состоит хотя бы из трёх точек (например, отрезок $\< (5,1), (6,2), (11,7)\>$ подходит).

Вы считаете именно отрезки или тройки точек, лежащих на одной прямой? Т.е. $\{(5,1), (6,2), (11,7)\}$ и $\{(5,1), (6,2), (7,3)\}$ - это один и тот же отрезок или нет?
И еще, если считаются отрезки, то считаются именно отрезки ненулевой длины? Если 2 из 3-х точек совпадают, то такая тройка задает отрезок? И считаем мы именно отрезки, а не прямые, задаваемые тройкой точек? Т.е. $\{(1,1),(2,2),(3,3)\}$ и $\{(2,2),(3,3),(4,4)\}$ - это разные отрезки?
При $N=2;3;4$ у меня получилось число отрезков $P(N)=6;32;58$. У Вас так?

[nikvic]

nikvic в сообщении #725479 писал(а):

Может, через рациональность тангенсов и несократимость выражающих их дробей?

Отдельно можно разобраться с вертикальными и горизонтальными, чуть сложнее - с наклоном 45 градусов.
В качестве основного блюда - прямые с коэфф-м в виде положительных несократимых дробей, меньших единицы. Вот здесь придётся туго, формировать произведения из ряда простых чисел...

[malphunction]

nikvic в сообщении #725479 писал(а):

Может, через рациональность тангенсов и несократимость выражающих их дробей?

Не понял, как именно? Напишите пример или дайте ссылку, пожалуйста!
Поискал про "рациональность тангенсов", ничего толком не нашел.

-- Ср май 22, 2013 20:59:22 --

venco в сообщении #725484 писал(а):

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

Да, я этого не учёл, но уже исправил. Сейчас буду писать ответ Sonic86, там расскажу текущее положение дел.

-- Ср май 22, 2013 21:26:06 --

Sonic86 в сообщении #725631 писал(а):

malphunction в сообщении #725455 писал(а):

Необходимо найти количество отрезков внутри этой решетки, каждый из которых состоит хотя бы из трёх точек (например, отрезок $\< (5,1), (6,2), (11,7)\>$ подходит).

Вы считаете именно отрезки или тройки точек, лежащих на одной прямой? Т.е. $\{(5,1), (6,2), (11,7)\}$ и $\{(5,1), (6,2), (7,3)\}$ - это один и тот же отрезок или нет?
И еще, если считаются отрезки, то считаются именно отрезки ненулевой длины? Если 2 из 3-х точек совпадают, то такая тройка задает отрезок? И считаем мы именно отрезки, а не прямые, задаваемые тройкой точек? Т.е. $\{(1,1),(2,2),(3,3)\}$ и $\{(2,2),(3,3),(4,4)\}$ - это разные отрезки?
При $N=2;3;4$ у меня получилось число отрезков $P(N)=6;32;58$. У Вас так?

Я считаю именно отрезки. Из Вашего примера отрезки $\{(5,1), (6,2), (11,7)\}$ и $\{(5,1), (6,2), (7,3)\}$ -- разные. Отрезки нулевой длинны не считаются; если совпадают пара точек, то это не подходящий отрезок. $\{(1,1),(2,2),(3,3)\}$ и $\{(2,2),(3,3),(4,4)\}$ - это разные отрезки, верно.

Для $N = 2$ получается $P(N) = 8$: три вертикальных, три горизонтальных отрезка и две диагонали (отдельная координата измеряется от 0 до 2).

На этой неделе совсем не было время толком об этом подумать, но пока наклёвывается такое решение (отличное от того, что в топике):

• Перебираем все взаимнопростые числа (по генератору из википедии).
• Каждая такая пара $(i,j)$ задаёт семейство отрезков.
• Будем перебирать целые числа $k > 1$ и $p > k$, в результате получаем отрезки $(0,0) - (k*i, k*j)$ и $(0,0) - (p * i, p * j)$, лежащие на одной прямой. Каждый такой "большой" отрезок $(0,0) - (p * i, p * j)$ задаёт прямоугольник (этот отрезок является его диагональю).
• Осталось найти количество способов расположения прямоугольника в большом квадрате, это тривиально.

Сложность -- $O(N^4)$ (цикл по парам взаимнопростых, цикл по $k$, цикл по $p$), что неприемлемо. Но, вроде бы, удаётся провести оптимизацию: будем перебирать только по $p$, будут получаться прямоугольники, количество расположений на его диагонали средней точки тривиально, без циклов, вычисляется. Итого сложность уже $O(N^3)$, что чуть лучше... Кажется, можно как-то связать взаимно-простую пару $(i,j)$ и возможные значения $p$, если так, то получится $O(N^2)$, ещё лучше! Но когда $N = 10^{11}$ всё равно не то...

P.S. Вообще, я решаю задачку Проекта Эйлера №415, но всё никак не могу придумать вменяемый алгоритм. Я решал несколько задачек из верхней сотни, открывается доступ к обсужденям -- смотришь, и часто бывает, что народ решал задачу на основании каких-то новых мат.разработок, т.к. частенько дают ссылки на диссертации, где решается сходная задача. Это, конечно, раздражает! Получается, задачи можно решать нагугливанием, но для этого надо разбираться в новейших достижениях... Это хорошо для математиков, но я -- просто развлекающийся программист :)

А ещё возникает вопрос этичности, могу ли я обсуждать решение задачи на форумах? Я считаю, что обсуждать направление поиска -- можно, а вот получить готовое решение -- уже неэтично. Поэтому я прошу направление -- где искать, какая область математики?

[nikvic]

malphunction в сообщении #727037 писал(а):

[*]Перебираем все взаимнопростые числа (по генератору из википедии).
[*]Каждая такая пара $(i,j)$ задаёт семейство отрезков.

Не только пары. Числитель - $2\cdot 2\cdot 11$, знаменатель - $3\cdot 11\cdot 11\cdot 13$. Важна взаимная простота и относительная "малость", чтобы три точки влезли в Ваш квадрат.

Deggial: замечание за неоформление формул. Формулы поправил.

[malphunction]

Sonic86 в сообщении #725631 писал(а):

При $N=2;3;4$ у меня получилось число отрезков $P(N)=6;32;58$. У Вас так?

$P(2) = 8$, я написал выше, почему.

Теперь случай $N = 3$, это квадрат со стороной в $4$ точки. В нём четыре вертикали, четыре горизонтали, две диагонали из 4-ёх точек и 4 "поддиагонали" из трёх точек. Из четырех точек три можно выбрать $C^3_4 = 4$ способами. Итого, вертикали, горизонтали и диагонали задают $(4 + 4 + 2) \cdot 4 = 40$ отрезков, каждая "поддиагональ" -- один отрезок, т.е. поддиагонали задают 4 отрезка. Итого $P(3) = 44$.

Случай $N = 4$, тут уже появляются более пологие отрезки, например, $(0,0) - (2,1) - (4,2)$. Сейчас попробую посчитать, сколько их всего.

Итак, есть пять вертикалей и горизонталей и две главные диагонали, в каждой по пять точек. Три точки можно выбрать $C^3_5 = 10$-ю способами. Итого $(5 + 5 + 2) \cdot 10 = 120$ отрезков. Непосредственно к главным диагоналям прилегают четыре поддиагонали из четырёх точек, $4 \cdot C^3_4 = 16$ отрезков. К этим поддиагоналям прилегают ещё 4 "под-поддиагонали" длиной 3 точки, они задают ещё 4 отрезка. Итого $120 + 16 + 4 = 140$ отрезков. Теперь считаем "косые" отрезки вида $(0,0) - (2,1) - (4,2)$. Такой отрезок можно два раза вверх сдвинуть. Итого 3 отрезка. Отразим по вертикали -- ещё 3 отрезка. Теперь то же самое, но с отрезками вида $(0,0) - (1,2) - (2,4)$, ещё 6. Окончательно, $P(4) = 152$. Вроде, всё посчитал.

[iifat]

Скорее уж, имхо, напрячься и попробовать вывести рекуррентное соотношение. Вот есть квадрат со стороной $N$, в котором $P(N)$ отрезков. Увеличиваем на $1$ — сколько их станет?

[malphunction]

iifat в сообщении #727356 писал(а):

Скорее уж, имхо, напрячься и попробовать вывести рекуррентное соотношение. Вот есть квадрат со стороной $N$, в котором $P(N)$ отрезков. Увеличиваем на $1$ — сколько их станет?

Скорее всего, так и нужно, такая формула даёт шансы на $O(N)$.

Но пока безуспешно...
Пусть мы посчитали $P(N)$, и сохранили с этого рассчёта все отрезки. Считая $P(N + 1)$, мы можем просто продолжить их (точнее, некоторые из них, ведь не все могут быть продолжены). Но, кроме них, с шага $N$ ещё нужно будет захватить пары точек, т.к. на шаге $N + 1$ они могут образовать нужные нам тройки... Ну и т.д., короче, пока рекуррентное соотношение не получается. Ещё я пробовал через удваивание (от $P(N)$ перейти к $P(2\cdot N)$), но тоже глухо...

Видимо, надо рассматривать сразу несколько предшествующих значений, но этим я ещё не успел заниматься.

-- Чт май 23, 2013 08:44:53 --

nikvic в сообщении #727064 писал(а):

malphunction в сообщении #727037 писал(а):

[*]Перебираем все взаимнопростые числа (по генератору из википедии).
[*]Каждая такая пара $(i,j)$ задаёт семейство отрезков.

Не только пары. Числитель - 2*2*11, знаменатель - 3*11*11*13. Важна взаимная простота и относительная "малость", чтобы три точки влезли в Ваш квадрат.

Не очень понял Ваше замечание про эту пару чисел. Если рассмотреть отрезок $(0,0) - (2 \cdot 2 \cdot 11, 3 \cdot 11 \cdot 11 \cdot 13)$, то он проходит через точку $(0,0) - (2 \cdot 2, 3 \cdot 11 \cdot 13)$, поэтому не является "образующим" для моего алгоритма.

Точки перебираем, разумеется, так, чтобы они влезали в квадрат, поэтому перебираем $(i,j)$ так, чтобы $i < N / 2, j < N / 2$, тогда пара отрезков $(0,0) - (i,j) - (2 \cdot i, 2 \cdot j)$ будут внутри квадрата.

[iifat]

Ну, вот так, сходу: в $P(N+1)$ входят отрезки

— входящие в $P(N)$

— входящие в $P(N)$, правый конец лежит на правой границе (их можно сдвинуть вправо)

— входящие в $P(N)$, верхний конец лежит на верхней границе (их можно сдвинуть вверх)

— никак не входящие в $P(N)$ — те, что идут отлевой до правой либо от верхней до нижней границы

Возможно, получится понять систему из двух рекуррентных последовательностей — количество всех отрезков и количество отрезков с правым концом на правой грани.

[malphunction]

iifat в сообщении #727360 писал(а):

Ну, вот так, сходу: в $P(N+1)$ входят отрезки

— входящие в $P(N)$

— входящие в $P(N)$, правый конец лежит на правой границе (их можно сдвинуть вправо)

— входящие в $P(N)$, верхний конец лежит на верхней границе (их можно сдвинуть вверх)

— никак не входящие в $P(N)$ — те, что идут отлевой до правой либо от верхней до нижней границы

Возможно, получится понять систему из двух рекуррентных последовательностей — количество всех отрезков и количество отрезков с правым концом на правой грани.

Я дополню:

Пусть мы получили все отрезки, входящие в $P(N)$. Перейдём теперь к $P(N+1)$. Ясно, что исходный квадратик размера $N$ можно расположить в квадрате $N + 1$ четырьмя способами. Таким образом, $P(N+1) = 4 \cdot P(N) + ?$, где $?$ -- дополнительные отрезки. Эти дополнительные отрезки следующие:

• которые в исходном квадратике состояли из двух точек, а теперь их можно продлить. Например, были две точки $\{(N-1, 0), (N,1)\}$, то в квадратике $N+1$ можно добавить к ним точку $(N+1,2)$, и появится новый отрезок. Заметьте, этот отрезок порождается семейством взаимнопростых чисел $(1,1)$, но таких семейств, получивших возможность расшириться, может быть больше, это надо как-то учитывать, причём так, чтобы два раза не считать одни и те же отрезки.
• в исходном квадратике линия, соответствующая отрезку, включала $m$ точек, а за счёт расширения стало $m + 1$. Например, был у нас квадратик размером 3, и в нём были 3 вертикальных отрезка. Рассмотрим такую вертикальную линию $(0,0)-(0,2)$. На ней в 3-квадратике помещается 1 трёхточечный отрезок. Расширим до 4-х точек. Уже помещается 4 отрезка! (см. мои рассчёты выше). Но не каждый отрезок расширяется при переходе от N к N+1, например, посмотрите мой рассчёт для $N=5$, там фигурировал отрезок $(0,0)-(2,1)-(4,2)$. При расширении квадрата на 1 он не получит продолжения, зато при расширении на 2 -- получит.
• отрезки с новыми углами: например, мы переходим к $N + 1 = 2\cdot p$, где $p$ -- некое простое число. Тогда появится возможность разместить новые отрезки вида $(0,0) - (i,p) - (2 \cdot i, 2\cdot p)$.

Как все такие особенности учитывать в рекуррентном соотношении -- непонятно. Даже не так. Можно такое рекуррентное соотношение составить, пользуясь результатами предыдущих вычислений, и его вычисление вроде даже линейным будет, но тогда потребуется $O(N^2)$ памяти, что неприемлемо.

Видимо, как-то можно упростить эти соотношения, но я ещё не успел придумать, как.

[iifat]

malphunction в сообщении #727363 писал(а):

Например, были две точки $\{(N-1, 0), (N,1)\}$, то в квадратике $N+1$ можно добавить к ним точку $(N+1,2)$,

Это учтено. Либо $N\ge2$ и присутствовал отрезок $\{(N-2, 0), (N,2)\}$, который можно сдвинуть на 1 вправо (п.2 у меня), либо $N=1$ и новый отрезок идёт с левого до правого конца (п.4).

malphunction в сообщении #727363 писал(а):

в исходном квадратике линия, соответствующая отрезку, включала $m$ точек, а за счёт расширения стало $m + 1$

Опять же, учтено: новый отрезок не помещался в $N\times N$, значит, он идёт от левого до правого конца (либо сверху донизу).

malphunction в сообщении #727363 писал(а):

отрезки с новыми углами

Таки аналогично предыдущему: описанный вами отрезок пойдёт от левого до правого конца.
Единственное, что сообразил — не две, а три рекуррентных последовательности: всего отрезков, количество отрезков, идущих до правого края, идущих до верху (совпадает с предыдущим) и отрезки, идущие до правой верхней вершины.

[MrDindows]

malphunction в сообщении #725455 писал(а):

Мучаюсь с одной олимпиадной задачей, подскажите, в какую сторону копать? Что почитать?

Дана квадратная решетка со стороной N (т.е. множество точек $(x,y)$, таких, что $x,y \in \{0, \ldots, N\}$).
Необходимо найти количество отрезков внутри этой решетки, каждый из которых состоит хотя бы из трёх точек (например, отрезок $\< (5,1), (6,2), (11,7)\>$ подходит).

Можно было бы найти все эти отрезки перебором, но проблема в том, что N -- очень большое, порядка $10^{10}$ степени.

Посоветуйте направление поиска!

Как же решить эту задачу?

Можно источник задачи?
Я знаю решение за $O(n\ln{n})$ и вроде как за $O(n)$

[malphunction]

MrDindows в сообщении #728244 писал(а):

Можно источник задачи?
Я знаю решение за $O(n\ln{n})$ и вроде как за $O(n)$

Это задача 415 из Project Euler. А что у Вас за решение?