Pull to refresh

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.