Тоже участвовали, заняли первое место :) Вообще да, заметно, что организаторы пытались дать неполиномиальную задачку, но в итоге все забили на некоторые случаи, и решали обычными дейкстрами или динамиками. Кстати, в отличие от некоторых, у нас было честное распараллеливание, правда, всего лишь на 4 потока.
Лично я участвую в третий раз, уже старожил. Весной 2012 вообще не было времени на этот конкурс, и поэтому сделали все тяп-ляп, даже отчета не написали вообще, профукали 25 баллов. В этот раз более серьезно отнеслись, почти весь месяц что-то делали, ну под конец больше тестировали и писали отчет, чем код :)
Ультрабуки, конечно, очень крутые, но 11 дюймов и FullHD — это жесть. Фильмы смотреть, конечно, здорово, но код — это же текст… Я ставил для работы 1600x900 или даже еще меньше. Все становится нормально видно, но картинка становится слегка размытой и непропорциональной :( и шрифты иногда как-то странно едут. Но вообще спасибо за них :)
Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.
Заметим, что если отсортировать массив, то искомое число будет находиться на непрерывном отрезке индексов, который будет длинее N/2. Это значит, что какое бы ни было это число — оно обязательно покроет ячейку массива с номером N/2.
Другими словами, надо найти число, которое после сортировки встанет на позицию N/2, а это можно найти вызовом одной функции nth_element в С++.
Итак, Раунд 1 завершен. Поздравляем прошедших в следующий этап!
Подробнее вы можете посмотреть тут. Кроме того решено добавить 45 уайлд-кард мест в Раунд 2, то есть лучшие 45 участников Песочницы на момент старта Раунда 2 среди тех, кто еще не прошел в Раунд 2 получат допуск в этот этап. Удачи!
Замечание второе: даже тип long содержит всего 64 бита (я использую Java), а наши строки могут быть длиной в несколько тысяч, и при вычислении хешей неизбежно произойдет переполнение. Эту проблему решить проще всего: надо закрыть на нее глаза. Ну, или почти закрыть: хеши у нас будут считаться, по сути, по модулю 264 (и поэтому не потребуется выполнять операции взятия остатка от деления — красота!).
В теории да, посколько суффиксный автомат, суффиксный массив и суффиксное дерево — равномощные алгоритмы. Но только использовать массив для стандартных задач — глупо. Даже найти все вхождения шаблона в текст уже не так просто
Только все-таки суффиксный массив — не замена дереву. Дерево умеет гораздо больше в силу своей структуры и благодаря всяким поддерживаемым ссылкам. Интересно, а практическое применение есть у массива?
Умножение таких чисел быстрейшими алгоритмами будет работать секунды. То есть достаточно большая формула будет считаться минуты. Кому это нужно? =)
Нет, ТАКИЕ большие числа скорее нужны из спортивного интереса + люди всетаки не теряют надежды найти закономерности распределения простых чисел. А вот это уже крайне важно
Лично я участвую в третий раз, уже старожил. Весной 2012 вообще не было времени на этот конкурс, и поэтому сделали все тяп-ляп, даже отчета не написали вообще, профукали 25 баллов. В этот раз более серьезно отнеслись, почти весь месяц что-то делали, ну под конец больше тестировали и писали отчет, чем код :)
Ультрабуки, конечно, очень крутые, но 11 дюймов и FullHD — это жесть. Фильмы смотреть, конечно, здорово, но код — это же текст… Я ставил для работы 1600x900 или даже еще меньше. Все становится нормально видно, но картинка становится слегка размытой и непропорциональной :( и шрифты иногда как-то странно едут. Но вообще спасибо за них :)
А еще подобные конкурсы будут?
Заметим, что если отсортировать массив, то искомое число будет находиться на непрерывном отрезке индексов, который будет длинее N/2. Это значит, что какое бы ни было это число — оно обязательно покроет ячейку массива с номером N/2.
Другими словами, надо найти число, которое после сортировки встанет на позицию N/2, а это можно найти вызовом одной функции nth_element в С++.
Что плохого вы видите в дополнительных местах?
Подробнее вы можете посмотреть тут. Кроме того решено добавить 45 уайлд-кард мест в Раунд 2, то есть лучшие 45 участников Песочницы на момент старта Раунда 2 среди тех, кто еще не прошел в Раунд 2 получат допуск в этот этап. Удачи!
так нельзя делать, почему написано тут: codeforces.ru/blog/entry/4898
Пара вопросов: а какое-то развитие проекта ожидается? И какую организацию вы представляете?
Только все-таки суффиксный массив — не замена дереву. Дерево умеет гораздо больше в силу своей структуры и благодаря всяким поддерживаемым ссылкам. Интересно, а практическое применение есть у массива?
Нет, ТАКИЕ большие числа скорее нужны из спортивного интереса + люди всетаки не теряют надежды найти закономерности распределения простых чисел. А вот это уже крайне важно