Comments 30
Интересно, Геннадий Короткевич есть в англоязычной википедии —http://en.wikipedia.org/wiki/Gennady_Korotkevich. А в русскоязычной нет, обидно.
Например, выдающимися результатами на международной олимпиаде школьников по информатике (IOI): 7 участий (5-11 классы), 6 золотых медалей, из них — три абсолютных чемпионства, одно — с полным решением всех предложенных задач. Вообще говоря, само попадание туда в пятом классе уже о многом говорит.
Например тем, что он возглавляет рейтинг ТопКодер. Начиная с Дэрека Кисмана на вершине рейтинга TopCoder было всего пять разных человек, так что тут уже о «тысячах» речи не идет.
Вообще, сложно сомневаться в том, что Гена сейчас самый сильный спортивный программист на планете.
Википедия создаётся нашими общими руками. Хотите статью — напишите.

Хотя в русской 99% вероятность, что удалят.
Хм, а первая задача разве за линейное время не решается? В каждом слове ищем первую слева букву (начиная при этом со второй буквы, т.к. префикс не должен быть пустым), большую первой буквы в следующем слове и обрезаем слово по найденной букве (не включая ее), от последнего слова оставляем только первую букву. На всех приведенных примерах это вроде работает…
Но если очередная буква совпадает с первой буквой следующего слова, то надо переходить к сравнению следующей буквы со второй буквой следующего слова и т.д. В итоге, получим квадратичную сложность.

Например:
Unnnnnnnnnnnnnnniversity Nnnnnnnnnnnnichego Nnnnnnnnnnnnne Delanya
Или менее тривиальный вариант:
Uninininininininininiversity Ninininininininininichego Nininininininininini Delanya
Да, меня всегда забавляло, когда математические задачки описывались в гуманитарном русле :)

Это просто шикарно:
«По удивительному стечению обстоятельств, как раз сегодня родители Анюты принесли с работы два набора чисел. Папа принёс с работы набор A, состоящий из P чисел, а мама — набор B, состоящий из M чисел. Все числа в наборах были целые, неотрицательные, а также не превосходящие 65535. Кроме того, числа в наборах были пронумерованы, начиная с 1.»

Прочитав данный абзац — возникает попутная задача на дедукцию, а именно — где работают родители Анюты, что с работы они принесли наборы с пронумерованными числами :)))))
Ага, математикам зарплату наборами чисел выдали. А дети давай их побитово умножать вместо ужина.
UFO landed and left these words here
когда я работал на литейно-механическом заводе в 1985 году, мы делали корпуса для подшибников, корпус состоял двух половинок, которые были уникальны.

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


Вот тут-то меня и накрыло.
Всегда интересовало, а насколько широк спектр задач где надо применять подобные методы подхода. По ощущениям в прикладном программировании какой-нибудь бизнес системы большая часть времени уходит на сборку функционала из стандартных кубиков. Внутри которых и скрыты все подобные хитрые алгоритмы скрыты уже внутри них, а сам программист должен только прописывать связи.
Просто создается ощущение, что спортивное программирование это вещь вообще мало связанная с реальными задачами.
С реальными бизнес-задачами — да, наверно. Но эти «кубики» кто-то должен написать. Так что тут смотря с какой стороны посмотреть.
UFO landed and left these words here
UFO landed and left these words here
Всегда есть опасность, что какого-нибудь кубика не хватит. Или он будет делать не совсем то, что надо. Или потребует очень громоздких подпорок. И тогда придётся или его реализовывать, или оправдываться перед начальством тем, что «гугл такого не знает».
Геннадию можно заочно давать первое место и не дразнить других участников.

А вообще, парень в 18 лет не хило бабло поднимает на проге — каждое соревнование это $10-20к.
Объясните пожалуйста, почему |f(x, S)| может быть вычислено за время O(|S| + 3^B)? Откуда 3^B?
Передаю вам ответ от Лёши Толстикова:

Каждое число y нам нужно отметить в ячейках x таких, что x & y = x (т.е. биты x — это подмножество битов y). Различных y у нас не более 2B, а суммарное количество подходящих x не более 3B (об этом написано здесь: e-maxx.ru/algo/all_submasks).
Возможно, где-то упустил по тексту, но на каких языках могли участники писать программы?
Only those users with full accounts are able to leave comments. Log in, please.
Information
Founded

September 23, 1997

Location

Россия

Employees

свыше 10000 человек

Registered

9 August 2008

Habr blog