Завтра, в 12.00 по Москве, начинается сезон мною очень любимых личных олимпиад на neerc.ifmo.ru/school! Не забудьте заново зарегистрироваться. Всем желаю удачи!
Разумеется, предлагаю после контеста здесь же обсудить задачи.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Завтра, в 12.00 по Москве, начинается сезон мною очень любимых личных олимпиад на neerc.ifmo.ru/school! Не забудьте заново зарегистрироваться. Всем желаю удачи!
Разумеется, предлагаю после контеста здесь же обсудить задачи.
Название |
---|
feedback'и будут?
Думаю, что нет. Они обычно появляются на контестах перед Всероссом, а в преддверии регионального этапа их нету.
У кого-то фидбэк пашет? У меня просто пишет "Unknown, Scored".
Монитора и не предполагается?
Нет.
в первой задаче "любое" == каждое или хотя бы один?
Думаю, что каждое.
это уныло, так писать условия =/
да вроде понятно...
слово "любое" можно понять двусмысленно.
ну да, лучше было написать "каждое"
да, голубчик, намного лучше.
Слово "любое" абсолютно понятно, не нужно придумывать ему второй смысл.
К сожалению, слово "любой" несет в русском языке одновременно два противоположных смысла. Например, в словаре Lingvo:
Любой
...
II. Какой угодно (на выбор).
III. Каждый из себе подобных; всякий.
Для меня, конечно, русский не родной, но думаю, что "любой"=="каждый".
Контрпример: "если оптимальных ответов несколько, выведите любой".
Контекст разный.
У меня времени на прочтение задачи, ушло больше чем на решение;)
Я вот тоже к сожалению понял, что хотя бы одно, причем даже не задумался над этим
Интересно получилось у меня: два жадника и два двоичных подъема:) Хотя на третью есть решение за N+М, я писал тупое N log N+M log M.
Больше всего за первую боюсь:) Там же выгодно либо за 1 штуку платить, либо только за 2 максимальных, да?
Вроде да. Я боюсь за heavy-light в D :)
Я делал фенвиком. Типа как на емаксе написано про покраску ребер. Хэви-лайт — для такого количества вершин и запросов слегка сурово, хотя может они поэтому такой ТЛ/МЛ и поставили.
Да.
у меня такой же расклад) в первой да, если максимальные в одном элементе — за одну, а если в двух, то либо сначала первый, затем второй либо наоборот, и лонги надо не забыть, вроде это верно
Ололо, я правильно понимаю, что засчитывалось последнее решение, даже если ты вручную выбрал засчитывать другое? :D
Вторая задача....втф?!
А где можно увидеть результаты?
тут
Тот неловкий момент, когда ты забываешь поставить used и твое решение вместо 100 получает 2..
Я писал хешсет на вторую руками. Для пары (x,y) брал хеш-функцию, как их произведение. Почему-то долго работает... Поменял, и прошло :(
В общем, я тебя понимаю.
Хеш-фунция равная произведению числителя на знаменатель падала по ТЛ? А можешь код показать? У нее же коллизий быть в принципе не может (если дробь несократимая, а знаменатель — степень двойки)...
У меня шех-функция (x*13+y), т.к я испугался, что произведение за long long выйдет. Тоже упало. Наверное, потому что куб :D
Ну куб заходить и не должен, авторское решение N^2 logN — оно хранит точки в TreeSet'e, и не беспокоится по поводу коллизий :)
я хотел быстрый куб сделать :)
Вот...
Код корявый, но найти должен :)
А... Ну так ты умножаешь на степень двойки (которая в знаменателе), а потом берешь по модулю 2 в степени 22. Понятно, что коллизий будет много. Если бы модуль был бы простым, то работало значительно быстрее.
Спасибо, что помог разобраться. Я всегда беру по такому модулю, чтобы не использовать остаток... Соптимизировал, называется..:)
Он простым никак быть не должен, просто в данном случае из-за степеней двойки произведение кратное модулю получается.
Там даже если поставить h=(x+1)*(y+1), то проходит. Получается, что нулей много... Хз откуда они берутся.
у меня тоже такая ситуация
Ребята, какая главная идея в решении А ?
UPD Извиняюсь, перечитал условие и понял, что все было раз в 500 проще...
Очевидно, что число равное максимуму по первому параметру мы заплатим, ведь никуда мы от него не денемся. Это же утверждение верно и для второго параметра. Зато после этого по каждому параметру уже платить не придется. Если максимум и там, и там лежит в одном задании, то его делаем первым, за остальное не платим. Иначе смотрим как нам выгодно — макс по первому, а потом по второму, или наоборот.
У кого есть права, залейте пожалуйста в тренировки.
Вопрос по задаче С. Правильное ли такое решение за n+m: читаем все запросы. Для каждой вершины сделаем список запросов, на которые нужно ответить, чтобы эта вершина была r(то есть в нее нужно попасть). Подвесим дерево за первую вершину. Для запросов, где l не является предком r ответ очевиден: первый предок l. Теперь для запросов, где l выше r: запустим дфс, для каждой вершины в массиве cur будем хранить вершину, в которую мы пошли из нее при обходе. Теперь если мы находимся в какой-то вершине, пройдемся по всем запросам для этой вершины и ответом на очередной запрос будет cur[l]. То есть идея такая, что мы запоминаем в какое поддерево идем и оно и будет ответом. Вроде понятно объяснил но правильно ли(:
Да, конечно правильно. напоминает алгоритм Тарьяна. Я минут 10 думал над красивым решением, но потом сел двоичный подъем писать. Пока писал, в голову это пришло, но решил не изобретать велосипед.
Соревнование добавлено в тренировки. Удачи в дорешивании!
Спасибо!
На вторую 6 секунд поставил, чтобы у меня хотя бы тут прошло?:)
Там авторские решение достаточно медленные
А почему во вкладке "Задачи" в тренировке для второй и четвертой задачи ТЛ показывает 6с и 10с, хотя, если послать решение, то тл оно получает за 2с и за 6с соответственно?
Кстати, авторское во второй работает меньше секунды...
Моё тоже.
А почему на D -256 Мб а не 512?
Поправил
Спасибо.
На нашем с We.Pepsi.Infi сайте опубликован разбор. http://algorus.blogspot.ru/2012/12/2012-2013.html
Кто-то может скинуть ссылку конкретно на страницу регистрации в олимпиаде?
http://neerc.ifmo.ru/school/io/registerIndividual.jsp Регистрация действует для всего цикла олимпиад
Заходить в систему можно только за какое-то определенное время до олимпиады? (сейчас я зарегался, и у меня не заходит)
Заходить можно непосредственно перед началом олимпиады, так что не беспокойтесь :)
Спасибо!