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

этой штуке еще можно вокал скормить как здесь (начало трека со второй минуты)

я, кажется, представляю себе как может появиться Скайнет…

наверно имелся в виду понг

этому блюдечку палец в рот не клади…

А если амбар вообще не красить, то экономии на краске еще больше.

Я помню историю, как один товарищ парсил сайт знакомств. Дело в том, что сайт выдавал только некоторую часть информации по каждому объекту. Поэтому товарищ автоматически регил несколько клонов до тех пор, пока не получал всю информацию. Ну, потом все это в базу данных и сортировка по нужному компаратору. Насколько я помню, он нашел что искал.

режим «сбалансированный» иногда понижает частоту процессора для энергосбережения
надо ставить режим «максимальная производительность»

В этом году требования были. Документ такой на 29 страниц. В прошлых годах, наверняка, тоже были, только я лично их не видел (а может видел, но не помню видел ли).

Вот что я нагуглил: 2012 год, 2015 год.

В 2012 формулировка: собирать на электронные носители, но вместо них можно использовать тестирующую систему. В 2015 же тестирующая система обязательна.

Ну не знаю как было в вашем регионе, у нас лет 5 как участники отправляли решения на сервер через проверяющую систему и она возвращала результат тестирования на тестах из условия (что там было на полных тестах — участникам до конца тура не было известно; первые годы решения проверялись на нашей собственной системе после тура, потом мы прикрутили тестирование на полных тестах параллельно ходу тура, чтобы быстрее получить итоговые результаты, а в 2014 переехали на ejudge с тем же функционалом).

ноутбуки были довольно мощные (4х ядерные core i7)
да и авторские решение более чем с запасом укладывались в 0.5 с
поэтому не меняли

Формат ACM отличается от текущего тем, что проверка решения останавливается на первом же TL. Тут же надо было ловить TL 24 раза на одно решение.

Быль.

может у нее куча одинаковых рубашек, примерно как у Цукерберка

На вики я ничего не трогал, более того — там на текущий момент вроде ничего не изменилось.
А надо было?
На русской вики дан «рецепт» (делайте так-то и так-то и получите то-то), а в английской — некоторые теоретические выкладки почему оно работает (хотя сам алгоритм почему-то толком не описан).

Да я в курсе как она работает. Мне просто фраза

любой алгоритм, решающий задачу сортировки быстрее, чем за O(NlogN) операций, не может работать правильно

в глаза бросилась. Это утверждение справедливо только когда мы не знаем дополнительной информации об элементах и умеем только их попарно сравнивать и обменивать. Товарищ Informatik уже исправился.

А как же тогда сортировка подсчетом?

я подразумеваю под элементами — сами сортируемые данные, без отношения к списку.
то есть сам список — контейнер для элементов, является цепочкой вершин, внутри которых находятся элементы. как-то так.
я мог кое-где ошибиться в обозначениях, ибо четкой терминологии заранее не строил.
но, думаю, мы поняли друг друга верно)

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

Если бы к этой статье был бы еще бесплатный доступ… Или я не туда нажимал?

Пока сути алгоритма я совсем не понял, но сразу пару вопросов: корректно ли он ловит случаи, когда элементов равных pivot несколько? и еще когда первый или третий блок после разделения оказываются пустыми?

хм… замечание-то дельное, перечитал референс по std::list, по сути там можно сортить только так:
some_list.sort();
сортировка заточена под список, она перекидывает указатели, указатели остаются валидны.

я же подразумевал вариант вроде этого, где вместо some_list, в принципе, может быть другой контейнер
sort( some_list.begin(), some_list.end() );
но для list оно что-то даже не компилируется:(

Никогда не храните указатели на элементы внутри контейнеров. Мало ли как оно потом будет само себя модифицировать. Первая же реаллокация того же вектора инвалидирует все все ваши указатели.

Фраза «и на списках в том числе» означает, что я могу запустить свою сортировку не только на списке, но и на массиве, и на векторе и на фиг знает еще какой структуре данных, которая предоставляет мне нужный для этого интерфейс, в котором перевешивание указателей не предусмотрено.

Боюсь, она медленнее сортировки слиянием для любого количества элементов. Даже тесты делать руки опускаются.

Пользовательским компаратором. Представьте, что вы пишете обобщенную сортировку для стандартной библиотеки. И потом пользователь сможет ей отсортировать, скажем, строчки, в своем компараторе прописав «сравнивай их лексикографически, предварительно развернув задом наперед».

Практическая задача — вряд ли, я же оговаривался в статье, что интерес чисто академический. Головоломка на пораскинуть мозгами. Впрочем, первый вариант кода можно где-нибудь использовать, лишней O(logn) памяти, думаю, найдется всегда.

Можно менять местами два элемента списка (на которые есть указатели/итераторы).
Т.е. структуру списка ломать нельзя, можно только обменивать пары элементов внутри него.

Да, немного неточно. Подразумевалось, что «и на списках в том числе», и еще «модифицировать список нельзя, только ходить по нему». Попробую эту неточность устранить.

Мы не знаем природы элементов, может там какие-нибудь строчки или еще какая жесть.

Я использовал 2 прохода: сначала пихаем в начало элементы "<", потом после них элементы "=".
В InPlaceMergeSort я не смог придумать как сортировать подмассивы длиной sqrt(n) друг относительно друга без рандомного доступа к памяти. Причем основная проблема — не обменять массивы, а добежать указателями до их начал.

Увы, пока только на C++

Если еще хорошо поработать с цветом, должно получиться что-то вроде этого

Привет Daemon! Добро пожаловать на Хабр!

офигенная лекция, спасибо

можно купить десяток и играть в конструктор

Не совсем понял суть вопроса, если честно. Можете переформулировать?

Кстати, очень хороший вопрос насчет загибания до сферы. Я тоже не до конца понимаю, как это можно сделать. Картинка из статьи в кванте:

По сути мы покрываем плоскость шестиугольниками, стрелочки означают что с какой стороны заклинивает. Но сферу нельзя покрыть шестиугольниками (вроде?) надо еще, например, 12 пятиугольников. Но для пятиугольников, во первых, надо что-то отличное от куба, а во вторых — пятиугольник портит «четность» и в итоге шестиугольники вокруг него потом не состыкуются. Так что цилиндр можно — а как сферу сделать не понятно.

Однако, шестиугольниками можно покрыть тор без вышеописанных спецэффектов и тогда существование самозаклинивающихся структур в 3Д очевидно. Может авторы имели ввиду сферу с ручкой, а не просто сферу…

Оу, так, конечно, красивее, а мой способ работает и для unsigned.

найти по числу m его максимальный делитель вида 2^n за время O(1)

Казалось бы m ^ (m & (m-1)).

В таком графе, в каждую вершину входит два ребра и выходит два ребра, а значит существует Эйлеров цикл

Зануда во мне говорит, что граф еще должен быть связным.

А вообще спасибо за статью, интересно.

Ну, я тоже в статье описал сведение задачи для 2 цветов к SAT (и даже выписал формулу для длины прогрессии 3). И я не спорю, что эту задачу можно решить с помощью SAT (причем быстрее и писать в итоге меньше).

В данной статье я скорее преследовал цель рассказать именно об алгоритмах расщепления и использовать вычисление числа Ван дер Вардена в качестве иллюстрации. А SAT там сбоку привязан для еще одной иллюстрации.

Во-первых, не всегда к SAT сводится, а во-вторых, алгоритм собственного написания иногда работает быстрее солверов, потому что можно найти крутые отсечения, свойственные конкретной задаче, которые не ловит солвер, написанный для общего случая.

Ну а вообще да, если к SAT сводится, то свой алгоритм имеет смысл городить только если после сведения чужие SAT солверы работают слишком долго.