Артём Рипатти ripatti

Это имело бы смысл, если бы у меня была машина с 120Гб оперативной памяти.

Ну тогда я буду ускорять потихоньку. Сейчас вот экспериментировал в заменой сортировки с указателями на хэш-таблицу, и… получил двукратное ускорение и решение за O(N^3). Т.е. почти полностью вырезал все то время, который жрал лишний логарифм.

Ну так я свое #5 даже и не пытался ускорять дальше из-за того, что оно квадрат памяти требует. То есть насчет него — я согласен, что может и больше, чем в 10 раз ускорится. Ну а толку от него, если оно в память не лезет?

Совершенно верно, у меня совсем вылетело из головы указать, что я ищу решения только для a,b,c,d,e>0. Сейчас уточню это в статье.

Если я верно понял, но у Вас для n=20 в случае без сортировки после (a=19 b=18) будет идти (a=20 b=1). Но ведь 19^5+18^5 = 4365667 > 3200001 = 20^5+1^5. То есть, если для n=10 оно вроде работает, то потом, с ростом n, при переходе от (a (a-1)) к ((a+1) 1) получаем, что первое число будет где-то в 2 раза больше второго.

С другой стороны — если не будет дополнительных ресурсов — то и оптимизировать особо смысла нет. Не думаю, что там можно более чем в 10 раз ускорить.

А так да, конечно, при возможной ресурсной поддержке — засяду оптимизировать насколько это возможно, опыт подобных расчетов есть (правда, «всего» на 55000 ядрочасов). Ну и не сразу миллион, а шажками: сначала 200000, потом 500000, а потом можно и за 1000000 взяться.

gcd там нужен чисто для отбраковки решений, в которых параметры имеют общий делитель. Поскольку решений, для которых нам нужно сделать такую проверку, очень мало, то сложность gcd можно не учитывать. Но если смотреть с формальной точки зрения — то да, надо везде домножить на логарифм. И решение #10 тогда получается со сложностью O(n⁵log n) (ouch!).

Насколько мне известно — нет.

Конкретно тут вроде неважно в каком порядке идут сравнения, но, скажем, в аналогичных циклах позже нужно будет сначала проверить, что j>=0, а только потом посмотреть что лежит в массиве по индексу j.

&& — это И для типа bool, & — логическое И для целочисленной маски.

Там же происходит j--, поэтому в процессе выполнения цикла условие i < j может нарушиться.
По хорошему, i < j надо вставить еще в следующий if, но когда это не выполняется, будет i=j и, в принципе, индекс массива j остается валидный.

сорян, я немного вклинюсь в ваш диалог
> вектора из модели word2vec — 300 действительных чисел
но ведь слов любого языка всего порядка 50000 и их можно закодировать 16 битами

Интересно. К сожалению, больше информации по этому проекту нагуглить не могу.

Зато я нагуглил информацию по другому проекту. Они другим алгоритмом через BOINC подтвердили результаты, которые я привел в тексте перевода. Вот ссылки: раз два.

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

А можно ссылку на пруф этого утверждения? А то мне известна только ссылка на доказательство оптимизированным брутфорсом (она есть в тексте перевода). И считали они там 7 миллионов ядролет (!) на кластере из 300 серверных машин (через MPI, а не BOINC). Причем программа была написана на ассемблере.

Если этот фильтр применить в видеоиграх, то «мыльное кинцо» превратится просто в «кинцо».

Давайте рассмотрим задачу попроще. Есть квадрат и мы красим его 4 угла в один из двух цветов — итого 16 вариантов. А сколько будет вариантов с учетом поворотов и отражений?

Там проблема в том, что некоторые решения при повороте на 90 градусов переходят друг в друга, а остальные — нет. Т.е. нам нужно все решения как-то разбить на 2 кучи и размер одной из них делить на 4, а размер другой — нет. А теперь представьте как их нужно разделять, если у нас есть кроме поворотов есть перемешивание строк, столбцов, и прочее (а также все их комбинации). И еще нужно понять какую кучу на что делить.

Верно, сначала мы сокращаем число полос 2612736 -> 36288 -> 416 -> 174 -> 71, а потом уже добиваем реальным перебором за 6 часов (вместо 6/71*36288, или сколько там было полос).

У разных решений можно дооткатываться до разного количества начальных задач. Впрочем, их можно разбить на классы, где в каждом классе одно и то же число различных задач (тогда можно откатываться только для одного решения из класса). Насчет этих вот классов — будет расписано во второй части перевода.

Кстати, в данной публикации мы и ищем все решения для пустого поля %) Точнее, их количество.

Проблема в том, что несколько задач могут иметь одно и то же решение. Например, если мы из полной сетки удалим одно из чисел (81 способом), то получим 81 задачу на одно решение, и все эти задачи будут различны.

Тут еще есть такой вопрос: какие полузаполненные сетки считать судоку — которые имеют ровно одно решение, или же просто подходят под Главное Правило. Второй вариант явно легче первого, а первый, вероятно, на сегодняшний день вообще не решаем.

Это уже вопрос терминологии. Можно считать что угодно, но написать «Под судоку мы будем понимать...». В статье авторы как судоку определяют начальную задачу, а конечную — как решение или полностью заполненную сетку. Каюсь, кое-где я заменяю одно другим, но из контекста ясно, о чем идет речь, просто мне в голову не приходило явно разделять эти понятия. Могу дополнительно все прописать более четко, если режет глаз.

Тут авторы считают количество решений, т.е. количество полностью заполненных сеток.

Через теорию групп и лемму Бернсайда.

Последнее число — это количество судоку без учета кучи симметрий вроде отражений, поворотов, перемешиваний троек строк/столбцов по блокам и тп. Т.е. количество действительно уникальных судоку.

Вторая же ссылка из гугла дает число 6670903752021072936960

на Nice Boat

Сразу же вспомнил про эту задачу https://ipsc.ksp.sk/2015/real/problems/m.html.
Правда, оказалось, там были чуть другие 6 символов.

Виноградов доказал не от 1 до N, а от N до бесконечности. Т.е. чтобы доказать тернарную гипотезу полностью, можно было бы просто проверить руками или на компьютере от 1 до N, если бы не астрономическое число N.

upd. Собственно, Хельфготт доказал тернарную гипотезу снизив границу N до не настолько большого числа, а все числа до N добил с помощью компьютера.

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

Автор же написал, что гуманитарий. Так и должно быть.

Не не, причинять можно добро, а пользу надо наносить.

Я заметил, что восприятие того, что на картинке — гора или яма — сильно кореллирует (для меня) с тем, как расположен внешний источник света относительно монитора. Для данной статьи сильно помогает свет от лампочки справа-сверху.

Радиоактивные изотопы электронов, ага.

Речь шла про аниме в жанре hard sci-fi, а не про школиё с экстрасенсорными способностями.

Так, стоп, там второй сезон есть? Ссылочкой не поделитесь? Я в гугле не нашел.

Тут хорошо напрашивается аналогия со слухом, например. Без подготовки сложно отличать ноты друг от друга, по после некоторой тренировки вы сможете отличать "до" от "ре". А после нескольких лет тренировок вы сможете записывать произведения по нотам прослушав только один раз. Хотя, как можно видеть, аппаратная часть не поменялась, только софтовая.