Пользовательским компаратором. Представьте, что вы пишете обобщенную сортировку для стандартной библиотеки. И потом пользователь сможет ей отсортировать, скажем, строчки, в своем компараторе прописав «сравнивай их лексикографически, предварительно развернув задом наперед».
Практическая задача — вряд ли, я же оговаривался в статье, что интерес чисто академический. Головоломка на пораскинуть мозгами. Впрочем, первый вариант кода можно где-нибудь использовать, лишней O(logn) памяти, думаю, найдется всегда.
Можно менять местами два элемента списка (на которые есть указатели/итераторы).
Т.е. структуру списка ломать нельзя, можно только обменивать пары элементов внутри него.
Да, немного неточно. Подразумевалось, что «и на списках в том числе», и еще «модифицировать список нельзя, только ходить по нему». Попробую эту неточность устранить.
Я использовал 2 прохода: сначала пихаем в начало элементы "<", потом после них элементы "=".
В InPlaceMergeSort я не смог придумать как сортировать подмассивы длиной sqrt(n) друг относительно друга без рандомного доступа к памяти. Причем основная проблема — не обменять массивы, а добежать указателями до их начал.
Кстати, очень хороший вопрос насчет загибания до сферы. Я тоже не до конца понимаю, как это можно сделать. Картинка из статьи в кванте:
По сути мы покрываем плоскость шестиугольниками, стрелочки означают что с какой стороны заклинивает. Но сферу нельзя покрыть шестиугольниками (вроде?) надо еще, например, 12 пятиугольников. Но для пятиугольников, во первых, надо что-то отличное от куба, а во вторых — пятиугольник портит «четность» и в итоге шестиугольники вокруг него потом не состыкуются. Так что цилиндр можно — а как сферу сделать не понятно.
Однако, шестиугольниками можно покрыть тор без вышеописанных спецэффектов и тогда существование самозаклинивающихся структур в 3Д очевидно. Может авторы имели ввиду сферу с ручкой, а не просто сферу…
Ну, я тоже в статье описал сведение задачи для 2 цветов к SAT (и даже выписал формулу для длины прогрессии 3). И я не спорю, что эту задачу можно решить с помощью SAT (причем быстрее и писать в итоге меньше).
В данной статье я скорее преследовал цель рассказать именно об алгоритмах расщепления и использовать вычисление числа Ван дер Вардена в качестве иллюстрации. А SAT там сбоку привязан для еще одной иллюстрации.
Во-первых, не всегда к SAT сводится, а во-вторых, алгоритм собственного написания иногда работает быстрее солверов, потому что можно найти крутые отсечения, свойственные конкретной задаче, которые не ловит солвер, написанный для общего случая.
Ну а вообще да, если к SAT сводится, то свой алгоритм имеет смысл городить только если после сведения чужие SAT солверы работают слишком долго.
Ого, не знал, что bitset работает медленнее, чем vector, если его использовать только как булевый массив. Видимо, bitset дает выигрыш, только если мы с ним еще делаем логические операции. Логично, но раньше мне такая мысль в голову не приходила.
Насчет ускорения — у меня сейчас есть более дикая идея, которая, вероятно, ускорит программу в сотню раз. Только для этого надо все переписать с 0. Если вдруг программа в итоге будет работать меньше 3 секунд (лучше — если сильно меньше) — можно будет потягаться с крутыми дядьками хотя-бы для случая K=6)
Почитал немного, у вас ошибка в определении: не просто сумма, а модуль суммы >C (иначе последовательность, где все элементы равны -1, все портит). И да, справедливость гипотезы для неоднородного случая напрямую следует из теоремы Ван дер Вардена.
Т.е. структуру списка ломать нельзя, можно только обменивать пары элементов внутри него.
В InPlaceMergeSort я не смог придумать как сортировать подмассивы длиной sqrt(n) друг относительно друга без рандомного доступа к памяти. Причем основная проблема — не обменять массивы, а добежать указателями до их начал.
По сути мы покрываем плоскость шестиугольниками, стрелочки означают что с какой стороны заклинивает. Но сферу нельзя покрыть шестиугольниками (вроде?) надо еще, например, 12 пятиугольников. Но для пятиугольников, во первых, надо что-то отличное от куба, а во вторых — пятиугольник портит «четность» и в итоге шестиугольники вокруг него потом не состыкуются. Так что цилиндр можно — а как сферу сделать не понятно.
Однако, шестиугольниками можно покрыть тор без вышеописанных спецэффектов и тогда существование самозаклинивающихся структур в 3Д очевидно. Может авторы имели ввиду сферу с ручкой, а не просто сферу…
Казалось бы
m ^ (m & (m-1)).Зануда во мне говорит, что граф еще должен быть связным.
А вообще спасибо за статью, интересно.
В данной статье я скорее преследовал цель рассказать именно об алгоритмах расщепления и использовать вычисление числа Ван дер Вардена в качестве иллюстрации. А SAT там сбоку привязан для еще одной иллюстрации.
Ну а вообще да, если к SAT сводится, то свой алгоритм имеет смысл городить только если после сведения чужие SAT солверы работают слишком долго.
bitsetработает медленнее, чемvector, если его использовать только как булевый массив. Видимо,bitsetдает выигрыш, только если мы с ним еще делаем логические операции. Логично, но раньше мне такая мысль в голову не приходила.Насчет ускорения — у меня сейчас есть более дикая идея, которая, вероятно, ускорит программу в сотню раз. Только для этого надо все переписать с 0. Если вдруг программа в итоге будет работать меньше 3 секунд (лучше — если сильно меньше) — можно будет потягаться с крутыми дядьками хотя-бы для случая K=6)