ну про эту штуку я не знал :) спасибо

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

Лично я участвую в третий раз, уже старожил. Весной 2012 вообще не было времени на этот конкурс, и поэтому сделали все тяп-ляп, даже отчета не написали вообще, профукали 25 баллов. В этот раз более серьезно отнеслись, почти весь месяц что-то делали, ну под конец больше тестировали и писали отчет, чем код :)

Ультрабуки, конечно, очень крутые, но 11 дюймов и FullHD — это жесть. Фильмы смотреть, конечно, здорово, но код — это же текст… Я ставил для работы 1600x900 или даже еще меньше. Все становится нормально видно, но картинка становится слегка размытой и непропорциональной :( и шрифты иногда как-то странно едут. Но вообще спасибо за них :)

А еще подобные конкурсы будут?

Спасибо, стало понятно. Просто стоит более понятно называть переменные, как минимум, m переименовать в sum, а mt — в add например :)

поясните, что именно хранится в массивах m и mt, при каких условиях туда что прибавляется, с какими коэффициентами суммируется.

Никакой сортировки в решении нет, она есть только в объяснении алгоритма.

int find(vector<int> a) {
	nth_element(a.begin(), a.begin() + (a.size() / 2), a.end());
	return a[a.size() / 2];
}            

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Заметим, что если отсортировать массив, то искомое число будет находиться на непрерывном отрезке индексов, который будет длинее N/2. Это значит, что какое бы ни было это число — оно обязательно покроет ячейку массива с номером N/2.

Другими словами, надо найти число, которое после сортировки встанет на позицию N/2, а это можно найти вызовом одной функции nth_element в С++.

А вы бы отказались, если бы мы поменяли призы на еще лучше?
Что плохого вы видите в дополнительных местах?

Итак, Раунд 1 завершен. Поздравляем прошедших в следующий этап!

Подробнее вы можете посмотреть тут. Кроме того решено добавить 45 уайлд-кард мест в Раунд 2, то есть лучшие 45 участников Песочницы на момент старта Раунда 2 среди тех, кто еще не прошел в Раунд 2 получат допуск в этот этап. Удачи!

Замечание второе: даже тип long содержит всего 64 бита (я использую Java), а наши строки могут быть длиной в несколько тысяч, и при вычислении хешей неизбежно произойдет переполнение. Эту проблему решить проще всего: надо закрыть на нее глаза. Ну, или почти закрыть: хеши у нас будут считаться, по сути, по модулю 264 (и поэтому не потребуется выполнять операции взятия остатка от деления — красота!).

так нельзя делать, почему написано тут: codeforces.ru/blog/entry/4898

Кстати, очень интересный рассказ.

Пара вопросов: а какое-то развитие проекта ожидается? И какую организацию вы представляете?

Я согласен, Очень крутое мероприятие =) мои листочки помогли?

это называется распаралеленный обход в ширину :) и не спорьте, я прав

зачем брут-форс? почитайте ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83

ясное дело — и там вклад поднять, и тут карму :) это же главное занятие всех троллей

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

Суффиксный автомат проще строится, но только дерево как структура проще и интуитивнее… гораздо проще рассуждать на дереве

Спасибо за статью!

Только все-таки суффиксный массив — не замена дереву. Дерево умеет гораздо больше в силу своей структуры и благодаря всяким поддерживаемым ссылкам. Интересно, а практическое применение есть у массива?

Умножение таких чисел быстрейшими алгоритмами будет работать секунды. То есть достаточно большая формула будет считаться минуты. Кому это нужно? =)

Нет, ТАКИЕ большие числа скорее нужны из спортивного интереса + люди всетаки не теряют надежды найти закономерности распределения простых чисел. А вот это уже крайне важно