Поделитесь информацией те, кто знает, когда будет проводиться полуфинал Украины по программированию(в прошлом году в Днепропетровске). Это нужно знать для планирования участия в чемпионате, ведь в этом году сессия в мае и совпадение экзаменов с чемпионатом ставит под сомнение в нем участие вообще.Если кто-то хоть что-то по этому поводу слышал, напишите пожалуйста!
UPD:Вот график проведения всех этапов олимпиады, взятый из приказа по министерству:
І етап (обласний) – 21 квітня 2012 року у базових вищих навчальних закладах відповідної області України; ІІ етап (регіональний) – 05 — 08 вересня 2012 року в базових вищих навчальних закладах відповідного регіону України; ІІІ етап – 11-14 жовтня 2012 року в базових вищих навчальних закладах у двох групах
Вроде как в сентябре в Луганске.
Присоединяюсь к вопросу, а совпадение с сессией скорее ставит под сомнение участие в сессии)
Можно нарваться на грубость
Раз уж зашла речь — вопрос (скорее, к тренерам, но может и участники знают) : а приказ вообще кому-то пришёл именно официально из министерства , а не только черновик от Месюры? Приглашения из базовых I этапа не предлагать ;)
UPD К нам приказ официально пришёл во вторник 17.04.2012 примерно в 12 часов дня (по Киеву).
І етап (обласний) – 21 квітня 2012 року у базових вищих навчальних закладах відповідної області України; ІІ етап (регіональний) – 05 — 08 вересня 2012 року в базових вищих навчальних закладах відповідного регіону України; ІІІ етап – 11-14 жовтня 2012 року в базових вищих навчальних закладах у двох групах
Интересно, правильно ли я понимаю что будет как обычно раундов, а не как в прошлом году? Может кто знает.
А что в прошлом году было необычного?
Я в прошлом году принимал участие в такой же системе соревнований. Разве что первый этап был раньше на несколько недель, а второй — на несколько месяцев.
Я что — тогда пропустил какие-то соревнования?..
Ничё не понял...
Официальных раундов обещано ровно столько же как и в прошлом году, только смещены во времени (IMHO, неудачно).
Другое дело, что в прошлом году проводили несколько тренировок, которые не были официальными раундами. Сейчас тоже планируется тренировка, только одна (в четверг 19.04.2012 начиная с 15:00 по Киеву).
В прошлом году Винница была параллельно с Бухарестом, а раньше Винница была перед Бухарестом. Так вот интересует то как в этом году будет проводится Винница.
Думаю, что статус 1/2 Мира никто не отберёт. Ведь областные соревнования уже заявлены, как 1/8 — вот и посчитайте. Другое дело, не поостерегутся ли ехать в Винницу лучшие команды...
Зажрались лучшие команды. Пусть достигнут чего-то, а потом будут носом воротить
Если бы я рассчитывал достичь определенных результатов в соревновании, и мне надо было выбрать, писать контест 5 часов или 4 с половиной...
Кстати, что по-вашему, является показателем "достижения чего-то"? Я так понял, что Вам до этого результата тоже еще далеко.
...Насколько я помню, в Виннице контест длился ровно 4 часа;)
4 часа в зачет и полчаса до рестарта?..
Там вообще не понятно, сколько он длился, система минимум 2 раза ложилась спать. В том числе и в конце контеста.
Вот-вот... в конце контеста за последний час НИКТО не смог НИЧЕГО отправить... А в Румынии только последние полчаса так было.
Че вы тут нюни распустили?Надо было за 2 часа все решить
Откуда такие толстотрольные синие вылазят?..
По моим сведениям вы не сделали ни одной правильной отправки, за последний час, вы не имеете права протестовать
А по моим сведениям у команды, в составе которой я принимал участие в том полуфинале, на момент окончания контеста было 1 точно полностью правильное и 1 идейно правильное (хотя, признаю, возможно и с багами) решение, которые физически НЕВОЗМОЖНО было послать, потому что с момента завершения написания первого с этих решений до помента окончания контеста система не работала.
Да и не Вам судить о моих правах. Вас, как я понял, просто зависть душит по отношению к командам высокого уровня.
don't feed мб?
just for fun
Возможно, этих достижений не хватает "лучшим командам" ;)
По моим расчетам,на 17.04.12 всего (n/3) округленных к верху "лучших команд", где n-количество минусов. Дальше, больше
Так это прекрасная реклама проекту. "Codeforces: с нами уровень Вашей команды растёт, как на дрожжах!"
Да уж, ты еще слишком синий, чтобы судить об этом. Вот поработай 3 года до универа, а потом 5 лет в универе в области АСМ, работай так, чтобы не было не праздников, не выходных. Достигни уровня команды типа Джулгаков+Соболя, а потом посмотрим, как ты отнесешься к тому, что на главный старт твоей жизни, на соревнование к которому ты шел 8 лет попадается такая вот Винница и т.Месюра. Ты думаешь, если бы команды, которые претендовали на выход в финал и знали что будет такой облом, не стремились всеми правдами и неправдами поехать в Румынию? Почему т.Месюра решил, что из 5 украинских полуфиналов стоит пускать только 4 команды, почему не дали место Западному региону, где и когда это обсуждалось. И самое главное, что при всем уважении к Диме Джулгакову, далеко не факт,что если бы его команда выступала бы в Виннице, а не в Бухаресте, то она бы заняла первое место!!!
Давайте не трогать Диму — у него было сдано 7 задач ещё до падения сервера. И с квотами перевираете — было предложено любым командам регистрироваться на любых площадках. Другое дело, что тем, кто не прошёл по квоте, в Румынию — за свой счёт, но когда это было иначе?
Не могу вести конструктивную беседу с Вами. Представьтесь.
Что же, удачи всем завтра на контесте. И прохождения в этот самый полуфинал)
А задания были одинаковые для всех регионов Украины? Если да, то можно где-то досдать задачи? Или разбор может где-то есть/будет?
Могу только общим бордом поделиться.
ejudge.sumdu.edu.ua переведён в режим дорешивания. Пароли от основного тура подходят. (Я там ни разу не админ, просто вижу вопрос и знаю хотя бы частичный ответ.)
Минусуйте, господа, минусуйте, но мне сегодня на 1/8 АСМ Украины надоело объяснять, кто такой "Крилик"... :)
Где-нибудь будут опубликованы официальные результаты 1-го этапа? (места по регионам, кто прошёл во 2-ой этап,...) Интересно ещё, кто из участвующих вне конкурса сможет принять участие во 2-ом этапе.
Кстати, кто-то может объяснить детально, как распределяются квоты?
Как мне объяснили, там часть заранее распределена пропорционально АСМ-активности региона, а остальные, 25% примерно, какие-то "бонусные" и их дают за АСМ-успехи региона и успехи конкретных команд на 1/8.
Но я не до конца понял, и не до конца уверен, что мне вообще реальную схему описали.
Да и по тех числах, которые мне назвали, получается, что я с 24 местом в итоговой таблице едва ли прохожу в четвертьфинал.
Я так понимаю для каждого региона это достаточно индивидуально. Не первый год повторяется ситуация когда люди из двацатки не влезали в квоту своего региона, зато некоторые и ниже 60ого проходили.
Раз 1/8 не заслужила на отдельную тему, то будем обсуждать тут:)
Ну что же, разборы задач будут где-то?..
А меня интересует мнение (**в первую очередь — тренеров**, во вторую — участников) по вопросу, соответствуют ли содержимое и уровень задач целям данного этапа.
Мой мнение — не соответствуют. Из 15 задач очень даже нужно было заменить несколько или средних или сложных на несколько тривиальнейших. У нас в Черкассах из 13+1 команд только 5 решили хотя бы по одной задаче. Оно конечно у нас в Черкассах всё слабовато и т.д. Но!!! Пис_а_ть везде подряд, что данный тур должен популяризировать и распространять в массах, что надо привлекать в т.ч. и ВУЗы где вообще нету программирования как профильного предмета, а потом давать такие задачи — несколько противоречит друг другу. Надо выбрать что-то одно.
Моё мнение, что таким пакетом задач, когда из заявленных по Украине команд лишь чуть больше половины сдаёт что-то, мы портим своему же региону возможность расширить квоты на мировом Финале. Ведь в учёт берутся команды, которые смогли решить хотя бы одну задачу. Не хватало задач, как в прошлом году — чтоб сильная команда сдавала первые 5 за полчаса и забывала о них, а слабая решила из них парочку и получила хоть какое-то удовлетворение. К тому же, поставить сложные в начало, а простые припрятать в середине — это тоже издевательство для новичков. Неизвестно, сколько команд так и не дочитало до простых.
Это как же надо было постараться авторам, чтобы задача с решением примерно
cin>>n; cout<<n<<".00"<<endl;
оказалась только шестой по числу ацептов.
Реально, шла речь про 5 задач школьного уровня и 5 задач "начального уровня олимпиад".
Начальный — это все что ниже топ-10 полуфинала что ли? Такое впечатление, что уровень задач оценивал среднестатистический финалист :) Ведь получается, что если команда по уровню выше "школьного" и "начального", то она должна решать 10 задач хотя бы. Такое оказалось под силу 15 командам.
Да, простые задачи были, и не одна, но "совсем простая" была только одна (про строки), да и то — припрятанная почти в самом конце. В прошлом году было лучше в этом плане... Правда, там был минус в том, что после первых 5 был слишком резкий переход по уровню задач — в этом году все плавнее.
Как по мне, то не соответствуют задачи. В прошлом году было штук 5-6 задач уровня А-В дива 2. Тут из тривиальных была только задачка считать N и вывести N c двумя нулями после запятой :) Но и то, чтобы понять, что нужно делать, требовалось прочитать целую страницу "предыстории"!
Честно говоря, я ждал разделения мнений — как подтверждений, что всё излишне сурово, так и заявок в стиле что "чтобы уровень команд рос, надо делать нетривиальные задачи"... В_ходе "игры в одни ворота" как-то трудно услышать новые ценные мнения.
Хотелось бы ещё мнения именно тренеров, умеющих готовить сильные команды. Но именно готовить, то есть выводить на сильный уровень с не шибко сильного, а не брать готовые.
А где-нибудь условия можно посмотреть (или когда они появятся)?
здесь
Как решалась задача H? Получили TL53
Наверно, потоки в стиле Си++ писали? У нас из-за этого было TLE50.
или же пытались 10 в 9 за линию пихнуть?
Писали MlogM (незнаю как там без сортировки обойтись). Чтение через scanf
То же самое, зашло с первого раза.
Не знаю, где там еще можно время потерять.
З.Ы. единственное что приходит на ум, это тл в поиске НОД, если писать обычную реализацию вроде
while (a&&b)a>b?a%=b:b%=a; return a+b;
, и натупить с типами при подсчете числителя, так, чтобы он дал переполнение и ушел в минуса... Тогда такой Эвклид можно подвесить.
Все остальные возможные баги вроде бы дают или WA, или RE.
Мне не нравится такой нод)
Допустим есть функция ((n-1)*(n))/2 считаем для всех праздников функцию от следующий минус предвидущий. Отдельным ф-цию первый минус последний + количество дней. Теперь сумируем все эти значения. Это наш числитель.Знаменатель это n. Дальше сокращаем дробь и будет счастье)
Так само. Вопрос в том, как побороть TL?
Какой ТЛ, 10^6 праздников?Ты за линию решаеш!
Ты про сортировку забыл.
p.s. Была проблема с TL на 53 тесте, проблема была в int вместо long long и как следствие бесконечный цикл в gcd.
Спс за инфу, значит, в посте чуть выше я угадал:)
Расскажите как делать А и В. Мне кажется что В это дерево отрезков....
Вам кажется?
У меня стойкое ощущение, что я уже несколько раз видел задачу В (т.е. именно массив с запросами на "число различных"), но с учетом того, что ее сдали только 2 команды, подозреваю, что я видел какие-то упрощенные версии...
По поводу А — это вообще самая интересная задача контеста, как по мне. Ее не решил почти никто из топов, но порешали команды, которые на 300+ местах с 1 задачей... Я лично знаком с некоторыми из этих "решателей", и понимаю, что они там ничего умного написать не могли.
Это единственная задача, над которой "работали" мои тиммейты, я попросил их генерировать максимально глупые идеи... Не помогло... У меня единственная рабочая идея была — искать наибольшую возрастающую подпоследовательность, WA8.
Да задача крутая, 8 команд только ее и решило, при этом почти никто из топов.
"ее не решил почти никто из топов, но порешали команды, которые на 300+ местах с 1 задачей" Каоманды? Она ведь там одна такая:)
Не все писали в одной системе) Есть еще 100500 команд результаты которых вы можете увидеть только в общей таблице
http://ejudge.crimea.edu/results/Standings.htm Это полная таблица?
Да, и 18 команд решивих А
Поделись решением!
У меня оно кривое. Я написал перебор чтобы закономерности искать. Закономерностей не нашел, зато пооптимайзил перебор, добавил отсечения, и он прошел. Скорее всего тесты не фонтан, хотя стоит отметить, что если первый выигрывает, то это решение находится довольно быстро.
А как там перебор делать, который быстро определяет выигрыш первого?
Перебираем ход, потом, как обычно, — если пришли в проигрышное состояние, то все ок. Получается, что перебор в начале тупо префикс отсекает какой-то, пока в мелкий массив не перейдет. Работает он долго только на тестах, где Мэг выиграет:)
Так если состояние проигрышное, то придется все ходы из него перебирать. А здесь каждое второе такое.
Ну так мы ж их и отсекаем, ибо если оно выигрышное, то найдем быстро, а иначе — оно проигрышное.
Ну, это жадность уже, так как перебора там нет практически.
Его там достаточно.
Вроде бы в В, должна заходить персистентная дуча. Но мой сокомандник, который в этом шарит, не добрался до этой задачи — мы зависли на тупом баге в С и нерассмотренном случае в L.
Я разве что за O(NsqrtNlogN) умею персистентным деревом отрезков. Судя по ТЛу, вряд ли что-то более быстрое ожидалось.
Мы сдали Heavy-light-decomposition на дереве MST. Нормально написанное решение имеет асимптотику O(N log N), но мы сначала написали O(N log^2 N), где на каждом "кластере" MST запросы делались за O(log N) деревом отрезков. Вершинная взвешенность вместо реберной достигалась совсем "втупую": заменой взвешенных ребер на пару невзвешенных + дополнительную вершину, имеющую вес первоначального ребра. LCA решалась сведением к RMQ. Перед приведением O(N log^2 N) к адекватному O(N log N) решил отправить — прошло с первой попытки. Но я до сих пор этому удивляюсь :)
Поправка: извиняюсь за невнимательность, все это относится к задаче C (не B!)
Мы писали решение попроще, как мне кажется:
После построения MST, можно реализовать RMQ на дереве, примерно так же, как и LCA (за O(logn) на запрос). Просто храним не 2^i-го парента, а максимум на пути от текущей вершины до 2^i-го парента.
Асимптотика получается O(q * logn), пишется не сложно.
мы тоже сдали её с помощью MST + LCA и как по мне это куда проще чем Heavy-light-decomposition на дереве MST
Мда... Ну, мы умеем придумывать сложные решения когда не надо, и не придумывать — когда надо :)
если n четное то выиграла Мэг а если нет, но отсорчена по убыванию, то тоже выиграла Мэг; иначе первый игрок
п.сп. извините, исправляюсь
Отличное решение, красивое и просто пишется. Небольшой минус в том, что первый пример не проходит.
Ок... После исправления примеры проходит:)
Как доказать? Т.е., как выглядит сама стратегия?
Увы, не я автор сего чудного решения. Хоть мне оно в голову и приходило, но было откинуто по недоказанности
Не совсем понял... Допустим, вход:
5
5 4 3 1 2
Нечетное, не отсортирована по убыванию. На любой первый ход Стю — Мэг берет "1" — и после этого сложно представить, как может Мэг не выиграть.
Тут Стю выигрывает — инфа 100%
Помогите завалить такую идею — считаем самую длинную возрастающую и самую длинную убывающую подпоследовательности. Если длинней вторая — выигрывает Мэг, иначе — Стю.
Проходит до 8 теста.
Идея решения — каждый будет убирать “лишние”, когда лишних не останется — победа у него в кармане. Кто быстрее убрал — тот и выиграл.
Мысли о том, почему падает — были какие-то идеи на тему “а если у нас нету ходов, которые не помогают сопернику…”. Ну и еще, опять же, стратегическая идея по борду — там есть тимы, которые не умеют искать НВП даже за квадрат, но сдали эту задачу.
За 35 минут тест придумать не удалось.
Заодно помогите завалить и такую: проимитируем процесс игры таким образом:
Стю просматривает слева направо все элементы — и как только находит элемент, который меньше соседа слева — то выкидывает из массива этого левого соседа.
А Мэг просматривает элементы справа налево — и как только находит элемент, который меньше своего правого соседа — выкидывает из массива этого правого соседа.
Если Стю не нашел ни одного такого элемента — он выиграл. Если Мэг не нашла ни одного такого элемента — она выиграла.
Подтверждений не могу привести никаких, просто единственная идея, которая приходит.
Update: а хотя, судя по всему, суть та же, что и найти длины наибольшей возрастающей и спадающей последовательности и сравнить их, только по-тупому реализовано :)
после какого то хода могут получится новые пары цифр которые не выгодны текущему игроку
Тест: 2 1 4 3 6 5.
Здесь возрастающая более длинная, но выигрывает второй.
Он 5, она 1, он 2 так можно долго гадать
А взять "3" за Мэг будет разве оптимальной стратегией?
и цифры путаю ><
"Он 5, она 1, он 2"
так после этого же выиграла Мэг, а не Сью...
Я же говорю цифры путаю.
Как Мег может выиграть при таком тесте 4 1 2 3 4?
Некому задать вопросы — не знаю, у нас (сумской сервер, регионы Центральный & Киев) через ejudge отвечали; вроде бы, отвечал автор задач Виталий Невидомый. Если у вас в другом регионе были местные проблемы — не надо ещё и их валить на Месюру и Невидомого. Где они виноваты — там виноваты, где не виноваты — на черта придумывать?
на “мові” — категорически странное замечание. А что, это так плохо, что начальный этап украинских соревнований на украинском языке (а_также, через ejudge, на русском)? А что, эти условия действительно на нормальном украинском языке?
Не синхронное начало — что имеется в виду? Что начали не вовремя или что разные сервера в разное время?
Менять Винницу и Харьков — не знаю... Мне приходилось слышать, будто ситуацию в Харькове в последний момент спасал Арзубов (учитель академической гимназии №45). Правда это именно слухи, пусть расскажут подробнее те, кто знает точно.
Илья Николаевич, Вы ведь серьезный и уважаемый человек, книги по олимпиадному программированию пишите, а верите всяким слухам. Какую такую "ситуацию" в последний момент спасал Арзубов? Кстати, Николай Алексеевич Арзубов уже много лет работает на кафедре информационных систем преподавателем (по совместительству) и действительно принял активное участие в подготовке и проведении финала во второй группе. Но точно также работали и остальные сотрудники кафедры, начиная от завкафедрой и заканчивая лаборантами учебной лаборатории. Поэтому, говорить, что Щербаков что-то провел, а Арзубов всех спас — просто некорректно по отношению к остальным. А менять Винницу и Харьков действительно не нужно. Нужно просто добросовестно относиться к порученному делу. Если каждый на своем месте обеспечит нормальную организацию и проведение соревнований, то недовольных будет гораздо меньше.
... Когда я включил компьютер, жир начал вытекать уже и из монитора тонкой, но непрерывной струёй. Я терпел, я думал это пройдёт. Но всё же была непонятна "причина" столь активного жироотделения. Когда я открыл http://codeforces.me/blog/entry/4323#comment-88977 ...
Да ладно Вам, "из 600 команд половина ничего не решила " — халявы были. За 5 часов можно было вбить кучу ифов для О или в лоб написать N. Но! У меня в универе (ПолтНТУ), например, ни одна команда не была "согнана насильно по приказу министерства", у кого так было — влепите тут минус, вот и посчитаем. Можно даже подписаться.
"говорили, что Щербаков в Харькове в прошлом году нормально провел второй финал" — ну хорошо там, где нас нету. Вот спросите у победительниц, сколько в итоге задач было пересужено после тура. И да, хватит толстить. Раньше хоть поржать можно было, когда читали ваш мусор, а сейчас, видимо, mihnevsev выдохся что ли...
Покормил