Есть текст приказа о собственно студенческой ( https://drive.google.com/file/d/0B59CuYKkspcjOWo2RHhuSkNKQ2kwN0dEaGhhMEJTRVo4d0lJ/view?usp=sharing ) и проект текста приказа о школьном дивизионе ( https://drive.google.com/file/d/0B59CuYKkspcjMk9zZTJaSlVmM2EyaU03RG1EUUZnTERPVHpn/view?usp=sharing )
Дата самого этапа -- Сб 21.04.2018
Дата окончания регистрации -- сейчас установлена Сб 07.04.2018; вероятно, будет ещё продлена, но слишком твёрдо на это лучше не~рассчитывать.
Все, в том числе школьники, регистрируются на двух сайтах — icpc.baylor.edu и icpc.org.ua
При регистрации на icpc.baylor.edu, учитывая, что это сезон 2018/19 годов, а сейчас ещё не окончился сезон 2017/18 годов, работают не все возможные способы регистрации. Работает, в частности, выбрать нужную из ссылок
https://icpc.baylor.edu/regionals/finder/ukraine-central-2018
https://icpc.baylor.edu/regionals/finder/ukraine-northern-2018
https://icpc.baylor.edu/regionals/finder/ukraine-eastern-2018
https://icpc.baylor.edu/regionals/finder/ukraine-southern-2018
https://icpc.baylor.edu/regionals/finder/ukraine-western-2018
https://icpc.baylor.edu/regionals/finder/ukraine-southwestern-2018
Есть способ регистрировать команды на icpc.baylor.edu через "API" — это может снять необходимость в регистрации на двух сайтах. Попробуйте обратиться к snarknews, если интересно
Весьма интересно, если правда; но весьма непонятно, как вообще что бы то ни было может снять необходимость в регистрации на двух сайтах, если без регистрации на icpc.baylor.edu в принципе нельзя участвовать в ACM ICPC, а без регистрации на icpc.org.ua в принципе неоткуда взяться таким полям, как "украиноязычное написание имени" и "номер студенческого билета". В любом случае прошу snarknews прокомментировать, если он считает нужным.
Интерактивные задачи могут быть на 1/8 ?
Это нормально что статус "Pending" ?
Нормально; он меняется на Accepted вручную координатором 1-го этапа, и это может быть очень длительный процесс.
Спасибо)
Как решать N?
Пройдем справа налево и каждой букве X поставим в пару первую свободную букву Y слева. Отсортируем полученный набор пар по позиции буквы Y. Можно доказать, что если существует ответ из k слов, то существует ответ, в котором индексы последних двух букв каждого слова являются одной из k последних пар в полученном наборе.
Теперь сделаем бинарный поиск по ответу. Пусть мы хотим проверить, можно ли вырезать k слов. Оставим k максимальных пар из построенного набора и попытаемся поставить им в соответствие первую букву. Сделать это можно жадно: пройдемся слева направо по всем парам и для очередной пары поставим в соответствие самую левую, невзятую букву X или Z. Если для какой-то пары такой буквы не нашлось, то ответ на проверку "нет".
А если так:
1) Для каждого Z поставим в пару ближайший справа свободный Y.
2) Для каждого свободного Y поставим в пару самый левый свободный X.
3) Достроить полученные пары ZY и XY свободными иксами справа налево. Если для какого-то XY пары не нашлось, то использовать X как свободный.
Если я не ошибся, то во всех трех пунктах работает доказательство жадности "так будет не хуже, чем если не так", и в целом должно работать. Ну и получится линия, так как все три пункта делаются двумя указателями, .
У нас вначале похожая жадность была, но она оказалась неверной. Если я правильно понял твое решение, то оно не должно пройти тест XXYXYYX.
На втором шагу получатся пары (1 3), (2 5), (4 6). На третьем шагу пара (4 6) достроится до (4 6 7) и больше ничего набрать не получится.
Хотя оптимально было бы выбрать тройки (1 3 4) и (2 5 7).
Ага, третий пункт значит неверный. Не учел, что иногда выгодно разбить тройку, чтоб закрыть две другие. Но вроде все равно можно за линию, но чуть сложнее. Так как в оптимальном ответе все левые иксы можно сделать левее всех правых иксов, то можно поддерживать их двумя указателями. По сути как твой второй пункт, только без бинпоиска, а добавляя по одной паре, пока добавляется.
Первый пункт использовали похожим образом: справа налево для каждого Y искали самый правый свободный X справа от него, таким образом сформированы были пары. Но вместо второго в твоем алгоритме, жадно слева направо шли и брали все Z или X, которые еще не были использованы в каком-то слове, и брали ближайшую к нему справа пару YX для слова. Но это решение падало на 28 тесте, а контрпример так и не нашли. Не подскажешь, в чем проблема такого решения?
Да, у нас как-раз WA 28 было с похожим решением. Например, оно не проходит тест XYXYYXX.
Жадность выберет только первые 3 символа и больше ничего взять не сможет, в то время как можно выбрать тройки (1 2 7) и (3 4 6).
Да, действительно, спасибо!)
Результаты
Запад, Киев: http://olymp.franko.lviv.ua
Восток (пока заморожено): http://ejudge.khai.edu/ejudge/Contest180421.html
Что-то не наблюдаю я тут центр(upd: уже нашел)
Как решать D?
Динамика.
Пусть dp[i][j] — это минимальное кол-во знаков '+' в строке состоящей из первых i символов исходной строки a образующей сумму j. dp[i][j] можно вычислить как минимум по k из dp[i — k][a[i-k+1..i]] + 1, где a[i-k+1..i] — число образованное подстрокой строки a c позиции i — k + 1 по i включительно — получается мы пытаемся вставить '+' между i — k и i — k + 1 символами. Перебирать все k не нужно, т.к. ограничение на общую сумму 5000, то достаточно перебрать k до 4-ех (еще нужно учесть что перед подстрокой могут быть лидирующие нули и обработать это, т.к. всегда выгодно поставить '+' перед лидирующими нулями).
Ответ(минимальное кол-во знаков '+') находится в dp[n][t], где n — длина строки a, а t — сумма которую необходимо получить. Чтобы восстановить ответ нужно вместе с dp[i][j] запоминать из какого состояния было обновлено значение динамики (позицию i-k).
Огромное спасибо!
Результаты Юго-Запад
Студенты+школьники http://olimp.tnpu.edu.ua/standing2018/all_standings.html
Студенты без школьников http://olimp.tnpu.edu.ua/standing2018/student_standings.html
Школьники без студентов http://olimp.tnpu.edu.ua/standing2018/school_standings.html
А где можно посмотреть расшифрованные результаты по Киеву и центру?
Подозреваю, что пока что нигде. Черкасскую область я расшифровывал вручную; можете попробовать сделать то же для других областей Центра на основании http://194.105.136.86/center500.php и https://docs.google.com/spreadsheets/d/1303Q2_H5b30C22-1VMsXwWk10fbvEu4y5QpRDxPaOuk/edit?usp=sharing Для Киева у меня нет даже таких данных.
Сделал общую табличку по всем регионам (Запад, Восток, Юго-Запад, Киев) и с расшифрованными результатами центра. Если кто-то поделится расшифровкой киевских команд, смогу их тоже добавить.
UPD: Добавил все школьные команды и отметил их как внеконкурсные.
Спасибо за проделанную работу, но у Вас получилось, что для одних регионов у школьников указан регион School, а для школьников Центра -- регион Center. Если что, по Центральному региону школьники имели диапазон логинов от team69 до team89 (обе границы включительно).
UPD: Честно, понятия не имею, почему по адресу http://194.105.136.86/center500.php ПОЛИТ есть, а в той табличке соответствий, которую я получил во время тура от организаторов, ПОЛИТа нет. А это ведь существенно меняет весь верх турнирной таблицы школьников.
Супер!
Только пару коректив:
sUzhGymn_Racoons West — Это школьная команда, насколько я понимаю, с Ужгородской гимназии (а у вас числится студентами)
Вообще все у которых первая буква маленькая "s" — школьные sUzhNU_wise_uncles_and_Yulia West — тоже школьная sLPML_Beavers West s80% water, the rest is logic West sKhBSO_GeniusProgrammers East ...
таково было требование организаторов, именовать школьные команды с маленькой "s", а коледжи с "c"
Т.е. я так понимаю, что в табличку надо внести коррективы, отметив все команды названия которых начинаются на "s" — как школьные (сейчас из регионов West, East они идут как студенты у вас)
Сайт с табличкой уже недоступен?
Говорят, вчера были какие-то DDoS атаки на сервера .ho.ua, сейчас уже все работает.
В качестве бонуса добавил расшифровку киевских команд и возможность фильтрации по региону :)
Круто, огромное спасибо)
А как К делать?
.
Наши школьники стеком решали, за O(N)
Только надо равные значения обрабатывать как одно (просто держать число и количество таких в стеке)
Помогите с задачами F и G, пожалуйста)
G: https://ideone.com/GFWYym
Ребят, если хотите дизлайкайте, я просто хочу немножко разобраться :) По ссылке link1 , если выбрать регион Center только , и по этой ссылке link2 немного различная информация. Может кто-то подсказать какая точная, а какая ложная в действительности информация о результатах региона Center?
Спасибо, что обратили внимание.
Насколько могу судить по тем результатам Черкасской области, которые выверял вручную, правильно на http://acmallukrainian.ho.ua/standings.html и неправильно на https://icpc.baylor.edu/regionals/finder/ukraine-central-2018/standings Что грустно, потому что именно на бейлоре должны быть официальные результаты.
Только моё личное мнение ещё не имеет никакой официальной силы. Если кто-то что-то может уточнить -- отпишитесь, пожалуйста.
Региональному координатору А.Л.Хиже я уже сообщил, но он в отъезде и не_может сегодня посмотреть.
А.Л.Хижа посмотрел, согласился, что на бейлоре что-то не то, будут исправлять. Когда -- я не_знаю, т.к. и желательно, чтоб на всё это ещё раз посмотрели остальные областные координаторы, и весьма вероятно, что обоснование необходимости исправлений потребует объяснений с международным оргкомитетом в рабочее время.
Ещё раз спасибо SickMyDuck за проявленную бдительность.
Добрый вечер. Со списком всё также творится какая-то магия http://prntscr.com/jbd84n