UPD 24.04.2014: Напоминаю, что послезавтра (Ср 16.04.2014) -- вроде как последний день регистрации на icpc.baylor.edu , а сам тур будет Сб 26.04.2014.
UPD 27.01.2014: Пришёл по официальным каналам текст приказа, см. https://docs.google.com/document/d/1C95TiSSi7y7w6nwN_vSXiijY3jITvdTl_zSYnz-Tsmw/edit?usp=sharing
=== старый текст ===
На днях координаторам 1--2 этапов пришло письмо от В. И. Месюры, с позравлениями насчёт выделения 6 мест SEERC-у и предложением обсудить сроки проведения 1-го (областного) этапа следующего сезона. Поскольку на то не было разрешения, само письмо публиковать не буду. Отмечу лишь, что к обсуждению предлагались лишь сроки 1-го этапа, а прочие обсуждения — моя личная отсебятина.
Я на самом деле не знаю, буду ли я лично не то что на финале Украины, а даже и на полуфинале (четвертьфинале мира). Так что просто довожу информацию, а формы обсуждения между собой и формы обсуждения с В. И. Месюрой пусть заинтересованные лица выбирают сами.
Собственно моё письмо координаторам 1--2 этапов (украинский — оригинал, русский — Google-перевод, за качество не отвечаю) .
Доброї пори доби усім.
Щодо питання "коли проводити І (обласний) етап AUCPC" -- дуже важливо не створити конфлікту зі шкільним Всеукром, і в цьому плані кінець березня -- стрьомний варіант.
І заодно хочу винести на загальне обговорення питання термінів ДРУГОГО (півфіналу України, чвертьфіналу світу) та ТРЕТЬОГО (фіналу України, SEERC) етапів. На мою думку, проведення ІІ етапів у останні роки на самому початку вересня -- поганий варіант, тому що: 1) досить складно і неприємно вибивати відрядження якраз тоді, коли абсолютно всі університетські посадові особи по саме нікуди заклопотані тим, щоб запустити навчальний рік, "а тут ще ти зі своєю олімпіадою іншого часу вибрати не можеш"; 2) за правилами ACM ICPC, учасниками можуть бути і студенти, і аспіранти; початок вересня -- той момент, коли для тих, хто переходить зі статуса студента у статус аспіранта, цей перехід ще не завершений, і людина формально не має права на участь; 3) якщо команда містить у складі іногородніх студентів, їм буває складно/дорого передати власноручну заяву з проханням про відрядження; 4) якщо команда містить у складі іногородніх студентів, їй важко встигнути провести адекватну кількість тренувань сАме у командному режимі (літню школу не пропонувати -- по-друге, у нас відрядження на літню школу-2013 досі не оплачені, а по-перше, є великі сумніви, чи ці літні школи надалі взагалі будуть, і якщо будуть, то в якому форматі і з якою вартістю).
Проведення фіналу України перед самим початком опалювального сезону таки має свої недоліки. Не треба казати про те, що у 2013 році обійшлося; досить того, що у 2012 було жахливо (холодно, а опалення нема). Звісно, перенесення термінів SEERC потребує обговорень і узгоджень з міжнародним оргкомітетом взагалі і румунами зокрема, але хотілося б хоча б спробувати їх ініціювати. NEERC, SWERC, CERC проводять помітно пізніше; які тоді принципові й нездолАнні перешкоди провести пізніше SEERC? Або навпаки раніше?
Враховуючи все вищесказане, особисто мені здається, що вибирати треба між варіантами == І етап -- або 01 березня (узгодити з ХаркЗимШк!!!), або 15 березня, ІІ етап -- кінець квітня або самий початок травня == та == І етап -- кінець квітня, ІІ етап -- десь у районі 20 вересня (Звісно це не годиться якщо раптом SEERC перенесуть на раніше) ==
===================================================================================
Доброй время суток всем .
По вопросу " когда проводить I ( областной ) этап AUCPC " — очень важно не создать конфликта со школьным всеукр , и в этом плане конец марта — стремный вариант.
И заодно хочу вынести на всеобщее обсуждение вопрос сроков ВТОРОГО ( полуфинал Украины , четвертьфинал мира ) и ТРЕТЬЕГО ( финала Украины , SEERC ) этапов. По моему мнению, проведение II этапов в последние годы в самом начале сентября — плохой вариант , потому что: 1 ) достаточно сложно и неприятно выбивать командировки раз тогда , когда абсолютно все университетские должностные лица по самое никуда озабочены тем , чтобы запустить учебный год , " а тут еще ты со своей олимпиадой другого времени выбрать не можешь " ; 2 ) по правилам ACM ICPC , участниками могут быть и студенты , и аспиранты ; начало сентября — тот момент , когда для тех , кто переходит из статуса студента в статус аспиранта , этот переход еще не завершен , и человек формально не имеет права на участие ; 3) если команда содержит в составе иногородних студентов , им бывает сложно / дорого передать собственноручное заявление с просьбой о командировке ; 4) если команда содержит в составе иногородних студентов , ей трудно успеть провести адекватное количество тренировок именно в командном режиме ( летнюю школу не предлагать — во-вторых , у нас командировки на летнюю школу- 2013 до сих пор не оплачены , а во-первых , является большие сомнения, эти летние школы в дальнейшем вообще будут , и если будут , то в каком формате и с какой стоимости ) .
Проведение финала Украины перед самым началом отопительного сезона все-таки имеет свои недостатки . Нет необходимости говорить о том , что в 2013 году обошлось , довольно того , что в 2012 было ужасно (холодно , а отопление нема) . Конечно , перенос сроков SEERC требует обсуждений и согласований с международным оргкомитетом вообще и румынами в частности , но хотелось бы хотя бы попробовать их инициировать . NEERC , SWERC , CERC проводят заметно позже , какие тогда принципиальные и непреодолимые препятствия провести позже SEERC ? Или наоборот раньше?
Учитывая все вышесказанное , лично мне кажется , что выбирать надо между вариантами == I этап — или 1 марта ( согласовать с ХаркЗимШк ! ) , Или 15 марта, II этап — конец апреля или же начало мая == и == I этап — конец апреля , II этап — где-то в районе 20 сентября ( Конечно, это не годится если вдруг SEERC перенесут на ранее ) ==
Пункт по поводу "команде трудно провести достаточное количество тренировок" — поднял настроение.
Взгляд со стороны участника — если менять, то наоборот, передвигать все на осень. Конец сентября, конец октября, конец ноября.
Я вижу довольно много причин, почему так удобнее. Так лучше для школьников, которые начинают свой первый сезон. Допустим, сейчас в NEERC можно со своими друзьями после школы сразу же, в том же году, собрать команду и выступать на NEERC. А у нас? Или есть какие-то неизвестные мне серые схемы, в которых ко второму этапу допускаются команды, которые не принимали участие в первом, или же лучший из вариантов — идти к "старшим" в роли замены. Еще одна причина — если участник или целая команда между сезонами хочет изменить вуз, за который она выступает, то в том же NEERC с этим проблем не сильно много. Поступление в магистратуру (самая популярная причина) или просто перевод участника — это обычно лето, новый сезон еще не начался, все ОК. А у нас? Как я понимаю — или менять место обучения посреди учебного года, или пропускать сезон.
Пришёл по официальным каналам текст приказа, см. https://docs.google.com/document/d/1C95TiSSi7y7w6nwN_vSXiijY3jITvdTl_zSYnz-Tsmw/edit?usp=sharing
Одно из существенных изменений — Центрального региона полуфинал Украины (четвертьфинал мира) теперь не в Сумах, а в Хмельницком.
Понятно. Придется пропускать сезон. Лишний раз доказательство того, что наше правительство относится к студентам, как к мусору.
Кто-то знает время начала контеста 26-го апреля? А то у нас в университете никто не может ответить на этот вопрос. Обычно начинался в 10:00, но вдруг в этом году изменилось...
Нас собирают на 8.30, следовательно скорее всего 10.00 (для 9 совсем поздно, для 11 совсем рано)
В 10.00
Знаю абсолютно точно и абсолютно официально, что по центральному региону начало собственно тура ровно в 10:00 (киевского летнего времени).
Ну а раз перед этим не только бюрократическое "здравствуйте, товарищи", а и жеребьёвка, и возможность в последний раз высказать до тура претензии к компу, то собирают обычно где-то на 09:00. В разных областях возможен разный небольшой плюс/минус.
По другим регионам -- по уму должно быть так же, но это я так думаю, а не знаю наверняка.
Тур закончился, чето никто не обсуждает.
Два вопроса:
1) У кого-то есть таблички? По Украине и по регионам?
2) Как решать J,L?
1) http://ejudge.crimea.edu/ — тут есть ссылки на таблички всех регионов, но восточный ещё не разморозили.
2) Тоже интересует =)
Хм...а почему это всё на сайте ТНУ?
Результаты есть здесь http://ejudge.crimea.edu/
Несколько бесполезных предположений по J:
На этом идеи закончились(
J: Сначала выбросим вершины из правой доли которые не достижимы из вершин левой доли. Тогда можно заметить, что для каждой вершины с левой доли будет достижимым последовательный отрезок вершин с правой доли. Дальше построим компоненты сильной связности. И запустим динамику на ациклическом графе, поддерживая для каждой вершины отрезок достижимых вершин с правой доли.
А у вас случайно нету кода решения?
Пока нет. Если получится загрузить код с ejudge, то будет, но пока такой возможности нет(
Еще интересует решение А. Хотелось бы услышать как можно больше разных вариантов решения, задача выглядит боянистой, было б здорово уметь решать её по-разному.
Мой вариант решения: клик
В целом, вроде, всё понятно, но прокомментирую. Семимильными шагами идём к ответу. Каждый раз проверяем, сколько чисел находится в лексикографическом порядке между k и k + 1 и отсюда получаем порядковый номер числа k + 1. Если он меньше либо равен искомого, инкрементируем k, иначе — умножаем его на 10, т.е., двигаемся к следующему в лексикографическом порядке элементу. Легко заметить, что решение работает за
P.S. А кто-нибудь умеет решать быстрее?
Спасибо за классное решение. Пойду разбираться. У меня было 200 строк какой-то переборной фигни.
Можно свести к
если не перебирать каждый раз новый порядковый номер вручную, а пользоваться знанием того, что, пока мы не дошли до той же разрядности, что и число n, мы суммируем одно и то же. Клик.
L: мы сначала составили систему уравнений с переменными left_even, left_odd, right_even, right_odd. Названия означают сумму чисел на позициях такой-то четности в такой-то половине числа. Из системы получилось, что left_even = right_odd, left_odd = right_even. Дальше если эти равенства уже выполняются, число не трогаем, иначе ищем самую правую цифру, увеличив которую, (и соответственно, получив полную свободу действий в цифрах правее от нее), мы сможем исправить ситуацию с невыполняющимися неравенствами. Найдя эту цифру, увеличиваем ее (возможно не только ее, если на пути девятки), обновляем значения left_even, left_odd, right_even, right_odd. Чтобы добить наши новые значения right_even и right_odd до left_odd и left_even, соответственно, жадно увеличиваем цифры справа налево. Правда, с моим решением получился один отдельный случай — для всех чисел 99<=x<=1000 сразу выводим 1001.
общая табличка по Украине будет примерно к понедельнику (попросила очень Козлова А.И.)
Загнал результаты в одну табличку:
http://mrdindows.github.io/scores
Спасибо)
Для большей информативности, можно добавить туда еще этот монитор с неофициальными.
Добавил.
А тут наоборот, попытался убрать команды вне конкурса.
Oxxxy!
Не мог бы кто-нибудь подсказать сколько команд от каждого университета проходят в 1/4?
от 2 до 4, стандартно 3, это в том случае, если команды решили хоть одну задачу. Есть правила расчета кол-ва команд от области + квота региона(+ дополнительные места, решают организаторы 2 этапа, согласовывают с Месюрой В.И.)
"Максимальні норми представництва ВНЗ у І – ІІІ етапах Олімпіади
Кількість команд-учасниць І етапу Олімпіади від одного ВНЗ – не обмежується. Кількість команд-учасниць ІІ етапу Олімпіади від одного ВНЗ складає не більше ніж: – дві команди для ВНЗ, які минулого року не були представлені у ІІІ етапі Олімпіади; - три команди для ВНЗ, які минулого року були учасниками ІІІ етапу Олімпіади; - чотири команди для ВНЗ, команди якого минулого року увійшли до першої десятки першої ліги ІІІ етапу Олімпіади; - п’ять команд для ВНЗ, команди якого минулого року стали призерами фіналу Першості світу. Кількість команд-учасниць ІII етапу Олімпіади від одного ВНЗ не перевищує 3 команди."
Я правильно понимаю, что "минулого року" в этих правилах — это "в прошлом сезоне", а не "в прошлом календарном году"?
Просто у меня не получается иначе объяснить, как здесь оказалось целых 5 команд от КНУ. В 2012 на финале не было ни КНУ, ни медалей в Украины. А в 2013 были.
Если так, то что же — 5ая команда ЛНУ, которая выше всего центрального региона — уже точно не проходит, а 5ая команда КНУ, которая выше 5ой команды ЛНУ, всего центрального и всего восточного региона — о своей судьбе узнает только через 2 месяца, после финала?
Два прошедших сезона точно было по 5 команд из ХПИ
Что такое АСМ-наивность — это на середине контеста увидеть, что условия сразу двух задач кривые, но подумать — "да ладно, сотни команд пишут этот контест, и задачи эти уже сдают, в случае проблем — уже были бы клары, надо перечитать еще раз". Через полчаса подумать — да нет, ведь действительно кривые условия.
Написать клар, получить в ответ — читайте условие.
И в результате старательно пробовать придумать какое-то искусственное понимание условия, которое будет работать... Потому что "все здают" и "читайте условие".
А кто автор задач?
Одна из этих задач — не F. Linguist случайно? Потому что я долго неверно понимал фразу "Вона, як і усі студенти факультету, панічно боїться чисел, в яких модуль різниці будь-яких двох сусідніх цифр більше ніж 1 (такі дивні ці мовознавці)." Да и сейчас мне кажется, что это можно понять двусмысленно.
Двузначность в том, что "будь-яких" — это либо "хоть одной пары", либо "каждой пары"?
Я не знаю, я не читал ни одного условия, кроме J и L. Мне тоже говорили, что еще в каких-то задачах что-то было криво, не знаю. Я две задачи читал — и в двух были проблемы) В J, условно говоря, надо реверснуть все ребра — автор перепутал, что откуда должно быть достижимо. В L — 3 приводят как пример "плохого" числа. Хотя, казалось бы, 0=0 и 0=0, число дважды хорошее.
В южном регионе, например, по L вскоре появился клар об этом, а о том, что в J автор перепутал, было отдельно написано на бумажке, которую дали вместе с печатным вариантом условий...
Как я уже понял, на клары отвечали не централизованно, а отдельно в каждом регионе. Отсюда подозрение — что на них отвечали люди, которые не имели ничего общего с процессом составления набора задач. Тогда все ясно) У нас на вопросы по поводу этих задач отвечали чем-то вроде read problem statement, как мне, так и нескольким другим командам.
И вообще единственный клар, который у нас пришел в общей рассылке — это ответ на вопрос "где посмотреть борды других регионов", в котором, к тому же, указали не все регионы)
"будь-яких" — это либо "хоть одной пары", либо "каждой пары"ага. Может, это у меня уже bias потому, что я из-за неправильного толкования много штрафа получил, но можно понимать и так, и эдак.
Большая просьба к автору — залейте контест в Тренировки пожалуйста.
Так есть же дорешивание. Здесь о нем написано.
Хоть там и включили full feedback, но все же... Как ни крути, никакое дорешивание не сравнить с тренировкой на Codeforces) В дорешивании виртуально поучаствовать не выйдет. А тренировка с общим монитором по всем участникам — это намного круче.
А забавно, кстати, подорешивать, не зная украинский язык и не пользуясь переводчиком:)
Мой логин-пароль не работет, возможно для команд центрального региона дорешка не открыта.
UPD Блин, там же регистрироваться можно, нужно учиться читать
Где можно узнать точные даты проведения полуфинала в этом году? Если они уже известны; если нет — то когда примерно будут известны? В приказе, ссылку на который дал IlyaCk, написано только "октябрь 2014".
Завтра 1/4; так как более подходящей темы не нашел, а новую создавать ради такого вопроса смысла не вижу, задам его здесь: по какому адресу будет доступен монитор соревнования для посторонних наблюдателей? Если, конечно, он вообще будет:)
http://olymp.sumdu.edu.ua/standings.php
Общий монитор, учитывающий также внеконкурсные (как правило, школьные) команды — http://olimp.vntu.edu.ua/all2014.php
Подскажите, а есть дорешивание?
Я был бы благодарен, если кто-то бы выложил ссылку на условия задач с 1/4. Спасибо.
Ссылка
Премного благодарен.
Расскажите как решать B и I.
B — в основе решения meet-in-the-middle. Сгенерируем все возможные значения на всех префиксах длины <=n/2 и всех суффиксах длины <=n/2. Переберем позиции первого слева от середины знака + и первого справа от середины знака +. При фиксированных значениях этих позиций, выражение будет вида pref+a[i]*a[i+1]*a[i+2]*...*a[j]+suf. Обозначим a[i]*...*a[j] как prod[i][j]. Тогда мы свели задачу к тому, чтобы для всех возможных значений выражения pref определить, есть ли среди значений suf число R-prod[i][j]-value[pref]. Ходят слухи, что с map'ами это могло получить TL, поэтому для надежности пишем meet-in-the-middle, отсортировав предварительно массивы значений pref и suf. Сложность выходит N*T*log(T), где T=2^(N/2).
I — предположим, что мы умеем отвечать на запрос "сколько нолей в массиве на позициях 1..x" за разумное время. Это можно сделать неявным/сжатым деревом отрезков или декартовым деревом. Каждая считалка, фактически, имеет вид "найдите i-ую единицу в массиве, считая с позиции х, и замените ее на 0". Сразу можно отбросить полные циклы — если в массиве осталось 10 единиц, а нужно найти единицу на позиции 75, то это то же самое, что сделать 7 полных кругов и после этого найти единицу на позиции 5. Теперь у нас осталось два возможных случая. Либо нужная единица будет в суффиксе после позиции х, либо же в оставшейся части круга — в префиксе до позиции х. Так как мы умеем отвечать на запрос "сколько нолей на префиксе", то можем очевидным образом научиться отвечать на запрос "сколько единиц на префиксе", посчитать число единиц на префиксе до х и на суффиксе после х. Далее мы можем определить, какой из двух случаев перед нами, и перейти к задаче "найти в массиве і-ую единицу, считая от начала, и сделать из нее 0". Чтобы получить чистый log на запрос — опять же, сжатое дерево отрезков или декартово дерево. Здесь можно написать бинпоиск за log^2 или корневую, но это, вероятно, получит TL (хотя какой-то log^2 вроде бы у некоторых заходил).
Спасибо.
"какой-то log^2"
Нормальный log^2 :D
а какой конкретно?
Будем закидыавать числа, которые уже удалили в любую структуру, которая за лог умеет говорить сколько чисел не больших какого-то h. Тогда просто на каждый запрос делаем бинпоиск, чтобы найти первую позицию, в которой длина отрезка(левая граница — последний удаленный; правую границу, собственно, ищем) минус количество удаленных на нем >= ki (число из запроса).
У нас log^2 с декартовым деревом получал TL, пришлось убирать бинпоиск, чтобы отвечать на запрос за log.
n*log^2 с декарткой ~ n^2 :)
А вообще, если уметь декартку, то халявно чистый лог пишется, если хранить в вершинах непрерывные отрезки, и суммы длин отрезков на поддеревьях.
А чем чистый лог с ДО не халявный?
Я ничего плохого про неявное ДО не говорил, кажется.
Кстати, константа хуже, лог же будет от 1018, а не от N.
Вряд ли хуже, всё-таки у ДД у самого по себе константа не очень
Просто, как по мне, ДО тут намного проще пишется. Одна функция-запрос, и всё.
Можно на код глянуть?
http://ideone.com/MF8qBK
not bad
Компетентные люди! Посодействуйте в добавлении 1/4й в тренировки КФ.
У нас тут на днях вроде очередной этап в Виннице. Может кто-то сказать точнее: какого числа будет тур и где можно будет найти результаты?
http://codeforces.me/blog/entry/14326
Если речь идет о полуфинале — сегодня был тур, вот обсуждение.
Есть ли у кого-то ссылка на размороженные результаты с сегодняшнего "контеста"?