Появился текст приказа — см. https://drive.google.com/file/d/0B59CuYKkspcjcnJ4MDFDeW5qZUZfcF96Q0RnUFo5SVAtRG1r/view?usp=sharing
Всё примерно аналогично прошлому году.
I (областной) этап Сб 25.04.2015.
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 8 | ecnerwala | 3494 |
| 9 | Um_nik | 3396 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | -is-this-fft- | 161 |
| 3 | maomao90 | 160 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 04.10.2024 09:25:58 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Up! До планируемого завершения регистрации осталось меньше недели.
Кто-нибудь с КНУ еще ищет команду?
а чего минусят? мне что отдельный пост создавать?
А известно, на каком языке будут условия? украинский (русский) или английский?
Должно быть на украинском/русском. Английский с 1/4 начинается
а начало во сколько? в 10:00?
Где можно посмотреть таблицу с результатами?
Ссылки здесь, но многие из мониторов еще не разморозили.
Upd. Западный с временами АС и после разморозки — здесь.
Я прямо в восторге от контеста. Особенно понравилась задача N, которая заключалась в угадывании метода считывания:
-TL 40
-TL 42
-TL 44
Еще очень понравилось, что сначала на джаве всегда вылетало CE, а потом это исправили и с таймлимитом 100мс всегда вылетало TL1.
100 мс и Java — это старая проблема. Я не понимаю авторов, которые так делают уже несколько лет подряд. Система так сильно просядет от TL повыше?
А по поводу считывания — не согласен. На контестах часто нужно считать в несколько раз больше данных. Вполне привычно в подобных задачах видеть матрицу 4000*4000 вместо 2000*2000, и потом с этой матрицей нужно будет сделать еще что-то нетривиальное; здесь же ограничения были адекватными. Либо участник на свой страх и риск умышленно использует весьма медленное считывание, либо пишет нормально. У меня язык не поворачивается называть это "угадыванием".
ну у меня до сегодняшнего дня ios_base::sync_with_stdio(0); полностью ставало. Жизнь меня не готовила к считыванию 4кк элементов за 100мс.
ИМХО лучше вот так себе испортить настроение на контесте вроде этого, и чему-то научиться на будущее, чем в перспективе впервые нарваться на подобный фэйл на каких-то важных соревнованиях.
P.S. Хотя я думал, что cin там проходит:) Не писал его, конечно — но думал, что проходит.
Казалось бы, после самого первого ТЛ нужно было сразу юзать char* и gets, а так — те же грабли
Если я не ошибаюсь, то в Киеве не показывало какой тест не проходит решение.
в Киеве то да, а на западном сервере показывало.
Из-за этого мы не могли понять какой алгоритм нужно использовать Первый показывал TL, а второй WA.
Восток. Та же проблема. Очень сложно понять — либо алгоритм в корне неправильный, либо не учел буквально одну мелочь.
На финале будет так же, нужно привыкать — это не проблема :)
Расскажите кто-то E и J.
H (?) — согласно условию, нам в первую очередь нужно сделать лекс.мин. строку. Поскольку число вида 100...000 не может быть простым, а + меньше за любую цифру, то нам нужно действовать жадно. Ставим на первое место лексикографически минимальное число, которое подходит; потом на второе, на третье, и так далее. Легко показать, что для определенной длины нам невыгодно использовать какие-то простые числа этой длины кроме первого — мы можем заменить наше число на первое простое такой же длины и получить строку меньше. Только нужно избегать случаев, когда мы пытаемся поставить число n-1 :) Генерируем все хорошие числа, сортируем их лексикографически, жадно строим ответ. Еще не забыть, что число 3 особенное — его нужно записать именно как 3.
E — вроде довольно стандартный прием — использовать ориентированные площади при подсчете площади многоугольника. Здесь же аналогично будем считать что-то вроде "ориентированной длины линий внутри". Решим для какого-то одного направления, потом поменяем координаты и решим для другого. Вроде можно использовать триангуляции, но у нас там получался неприятный разбор случаев для точек на границе, поэтому написали разбиение на трапеции. В зависимости от направления данной стороны многоугольника, нам нужно либо прибавить к ответу значение в этой трапеции, либо вычесть его. А посчитать суммарную длину внутри примитивов вроде трапеции или треугольника не сложно — в прямоугольнике все понятно, для треугольника используем арифм.прогрессии, трапецию можно разбить на треугольники/прямоугольники.
В Е вроде так и делали трапециями, вылезали неприятные случаи с вертикальными прямыми (для вертикального направления). Хотя возможно это я криворукий. Хотя если сохранился код — буду благодарен :)
J — это не та задача, J про 31-ричную систему счисления
А, ок, прошу прощения :) Ну а если кому-то будет нужна та задача, которая на самом деле не J, то пускай будет)
Про 31-ричную — так как система 31-ричная, то все классно. 31 — простое. Поэтому при известных последних цифрах a и c мы можем однозначно подобрать последнюю цифру b такую, что a/b=c. Только нужно заранее сократить числитель и знаменатель на нужную степень 31 (отбросив лишние 0 в конце). Так как a делится на c, то после этого в знаменателе последняя цифра точно будет ненулевой.
Подобрав последнюю цифру ответа (пускай она b0), можем вычесть b0*c из a, и теперь искать предпоследнюю цифру b по предпоследней цифре a и последней цифре с. Пока что это 10^6*10^4, но очевидно, что можно не делать честное вычитание на каждом шаге, потому что нас интересуют только последние 10^4 цифр a, корректность остальных можно не поддерживать. Отсюда решение за 10^4*10^4.
Еще раз по поводу E. Предположим, мы считаем вертикальную составляющую. Вы както рассамтривали отдельно случай с вертикальными прямыми или както его избегали?
Просто мы делали чтото такое — считали сумму в трапеции, тогда выходит что сами вершины мы или учли два раза, или вообще не учли — иногда нужно добавить/отнять одно вхождение. Поэтому добавим или отнимем y-координату таких вершин. Но. У нас вылезали непонятки с вертикальными прямыми, и непонятно как их обрабатывать.
Пускай мы cчитаем общую длину вертикальных полосок. Пускай порядок обхода у нас по часовой стрелке. Если против — реверснем все; направление можно определить по знаку ориентированной площади.
Дальше я буду употреблять "слева" в значении "в направлении уменьшения x", а не "слева в порядке движения".
Если перед нами горизонтальный отрезок — забьем на него — ведь у его проекции нулевая высота.
Если перед нами наклонный отрезок — в случае, если он идет вверх, мы вычитаем из ответа суммарную длину вертикальных полосок слева от него; если же он идет вниз, мы прибавляем к ответу суммарную длину вертикальных полосок слева от него. Поскольку у нас обход по часовой, то каждая полоска внутри будет прибавлена на 1 раз больше, чем вычтена, каждая полоска снаружи — прибавлена столько же раз, сколько и вычтена.
Остались вертикальные отрезки. Если этот отрезок идет вверх, то мы вычитаем из ответа суммарную длину вертикальных полосок слева от него плюс длину самого отрезка. Если этот отрезок идет вниз, то мы прибавляем к ответу суммарную длину вертикальных полосок слева от него. Благодаря нашему порядку обхода каждая ошибочно прибавленная вертикальная сторона (которую мы прибавили, проецируя что-то справа от нее) будет вычтена во время рассмотрения этой стороны.
В Е красивая формула есть: 2S - Len / 2, где S — площадь фигуры, а Len — суммарная длина сторон, которые паралельны какой-то координатной оси.
А можете обьяснить почему такая формула? То есть как вышли к ней?
Если разбить многоугольник на трапеции (можно вырожденные) с, например, горизонтальными основаниями и единичной высотой, то площадь каждой такой трапеции будет полусуммой её оснований, умноженной на единицу. А сумма всех этих площадей даст площадь многоугольника. С другой стороны сумма площадей трапеций будет равна суммарной длине горизонтальных отрезков внутри + половина длины горизонтальных отрезков на границе (потому что они входят только в одну трапецию). Отсюда получаем длину горизонтальных отрезков внутри — S - Hor / 2, где Hor — длина горизонтальных отрезков на границе. Аналогично для вертикальных. Получаем 2S - Len / 2.
ок. спасибо
Я не знаю, в чём заключалась задача, но эта формула напоминает теорему Пика.
В задаче H дополнительно нужно было заметить, что (если не ошибаюсь) для 13 порядка простое число лексикографически больше, чем для предыдущего, и не учитывать его в ответе.
А кто может подсказать по поводу задачи с елочными игрушками? Кажется I. Мы брали сумму двух входных чисел, делили её на меньшее из чисел и проверяли будет ли полученное число степенью двойки. Если будет — 1, иначе 0. Это совершенно неправильное решение или мы не учли какой-то мелкий момент?
Проще всего было решить в лоб, цикл всего-то на log(N). Хотя на первый взгляд подход верный, но у нас тоже была WA в подобном коде
Поговаривают, что делить нужно было на наибольший общий делитель.
Да, действительно, контрпример 3 13 если (3 + 13) / 3 — не степень 2, хотя переложить игрушки можно: 3 13 / 6 10 / 12 4 / 8 8 / 16 0 И ещё несколько примеров:
Спасибо! Сам подобрать контрпример не смог, хотя на 3 и 13 вроде не так уж и сложно было натолкнуться.
Кому интересно, на новом сервере Южного региона здесь открыто дорешивание I stage 2015, также активирован python3. Буду рада, если потестите сервер решениями на python3 и java. Логины, пароли выдам по запросу. TL для python3 и java выставлены, и больше 100 мс.
Совет авторам: если вы не хотите, чтобы участники думали, что вы даже передрать готовую задачу нормально не можете — следите, чтобы в задачах, которые вы даете на соревнования по правилам ACM ICPC в условии не было строк
В данной задаче двенадцать блоков. Тесты насчитываются отдельно за каждый блок, при условии прохождения всех тестов блока. 40 баллов можно получить, если Ваша программа верно работает при 1<=N<=4 и 1<=M<=5.
(Для тех, кто не в теме — выше примерный перевод фрагмента условия задачи D).
Значит, в разных областях ещё и не_вполне одинаковые условия задач... У нас такого (двенадцати блоков) не_было! Ни в D, ни в иных задачах. Только что ещё раз перепроверил — не_было. И не я убирал, а так и пришло "из Центра" ;) Только я решил, что такие усилия по экономии бумаги несколько чрезмерны, и случаи втискивания трёх задач на одну страницу поубирал (но по две, которые при насущной необходимости легко разрываются с хорошим промежутком между ними — почему бы и нет?).
У нас в бумажной версии приписки о 40% не было, а в электронной была.
В то же время, в одной из задач в бумажной версии было сказано выводить "NOSOLUTION", а в электронной — "NO SOLUTION" (именно второй вариант был правильным). В общем, кое-какие различия были.
Условия по 2-3 задачи на странице это тоже сильно. Конечно, я не против стратегии давай я сейчас еще вот эту напишу сразу, чтобы страницу выбросить, но у некоторых волонтеров в глазах видно было определенное удивление: мы им раздали условия... а они их... рвут... на части... зачем они их рвут?.. Теперь буду с собой на контесты ножницы носить.
В Южном регионе, по крайней мере в Запорожье, не было того, что 2-3 задачи на листе, видимо организаторы решили отформатировать задачи и разместили одну задачу на листе А4, и тем самым, позаботились про участников олимпиады
В Южном регионе я проблем вообще не наблюдал на Одесской площадке, ни с условиями ни с каким-то пропихами в TL, спасибо организаторам.
также хочу выразить огромное спасибо 977kai за поддержку и помощь в настройке сервера Южного региона
тебе это сильно помешало?
в некоторой степени, я даже начал думать, что задача может засчитываться за пол-задачи))
Ем. Парень, фигню сказал.
Видимо в этом году к стандартному "мы поставим 100ms Time Limit, чтобы Java давала Time Limit Exceeded на первом тесте" добавилось "мы сделаем условия немного разными для разных регионов" и "мы напечатаем условия так, чтобы вы их 5 минут разрывали руками".
Слишком много обсуждений как для 1/8
То, что этап не слишком важный не значит, что он не может быть качественным. Особенно радуют баяны (которые появляются не первый раз). Я на локальные соревнования стесняюсь ставить не свои задачи (или свои, но уже засвеченные), а тут такое.
Привет. Может кто-то залить в тренировки первый этап? Спасибо.
На всякий случай напомню, что полуфинал Украины (четвертьфинал мира) совсем скоро — 11-12.09.2015
Подскажите, есть ли ссылка на борд?
Upd. Вот Спасибо Наталье Кеберле и snarknews
Вообще-то, ссылка предназначалась только для жюри, украинских тренеров и участников, так как 13-го планируется Гран-При Украины. Украинским командам результаты полуфинала пойдут как в общий зачёт Открытого Кубка, так и в спонсорский (надеюсь, что он скоро будет анонсирован).
К сожалению, после этих действий придётся перемешивать задачи.
Ну и ещё просьба — не обсуждать задачи полуфинала до 16:00 13 сентября (завершения Гран-При)
Прошу прощения. К сожалению, мне не сообщили о конфиденциальности днной информации.
Ну переставить не так сложно, на самом деле.
Названия задач тоже, естественно, поменяются (всё же соблюдать правило первой буквы — это хороший стиль в ACM). А здесь World Finals style выдерживается даже по количеству задач...
а разморозка когда будет?
Спасибо за борд) Что значат звездочки возле названий некоторых команд (вроде LNU Penguins* и KhNURE_United*)? Обычно это "вне конкурса", но здесь как-то не подходит.
А кто автор задач?
А где можно посмотреть окончательные результаты?
А где-то можно смотреть результаты опенкапа не имея логина к yandex.contest?
Сейчас будет ссылка. А логин вам будет нужен на следующие этапы опенкапа
А Вы можете нам его создать?
Вроде Ваш координатор Виталий Бондаренко попросил яндексовый логин для того, чтобы выдавать Вам пароли, я его ему выслал.
Следующий этап в лучшем случае 27.09, так что время получить пароль у вас ещё будет.
Спасибо!
Кто-то может скинуть полные правила 3-го этапа(финала Украины)?
Пиши мыло в личку.
Минутка урчания
Уважаемые авторы!
Пожалуйста, перестаньте давать тайм лимиты по 200мс. Прочитайте наконец-то руководство для авторов Codeforces и следуйте их правилам по установке тайм лимитов.
Спасибо.
А в чем сейчас была проблема таймлимитов на 200мс? У меня I на джаве прошла, хотя там был ТЛ 100мс.
Правильный ответ — всем. Хотите много тестов — делайте мультитест
Мое мнение — жесткие тайм лимиты вносят в контест рандом и больше ничего. Никакой пользы от них я не вижу.
Кроме очевидной: у нас сервер находится в той же вселенной, что и участники, так что большИе TL приводят к очередям, а параллелить проверку на многих однотипных машинах нет технической, финансовой и т.д. возможности. Мне кажется, что Вы-то должны помнить если не саму ситуацию на финале Украины 2009, кажется, года, то хотя бы разговоры о ней. Ситуация была таковой: Вася Билэцькый ставил огромные размеры входных данных и огромные TL, в результате проверок ждали по полчаса. Правда, тогда был ещё PC^2, который приходилось ещё и иногда перезагружать.
Может, я недостаточно внимательно слежу за новостями codeforces, но, насколько знаю, вроде бы всё ещё актуально описанное в http://codeforces.net/blog/entry/8457?locale=ru "_все ограничения времени перед запуском программы делятся на 2, программа исполняется, а в конце время её работы умножается на 2_". Не понимаю, почему вдруг честно сказать "у нас тайм-лимит 500 мс" — хуже, чем врать "у нас тайм-лимит 1 сек" и проверять с 500 мс. (UPD: в комментариях меня поправляют, что на CF это касается только совсем старых туров, готовившихся под другое железо. Возможно.)
БольшИе TL в совокупности с боязнью очередей приводят к желанию жюри/авторов ограничить количество тестов, что также "_вносит в контест рандом_" — становится бОльшей вероятность пропихнуть вообще-то неправильное решение (быстрое, но дающее не всегда правильные ответы). Каковой факт вчера реально имел место. Вероятно, далеко не один, это я знаю только об одном (но вопиющем).
Если лично Вы в следующем сезоне уже не будете участником — пожалуйста, подготовьте пару задач. Я с превеликим удовольствием уменьшу количество своих.
(2) — это работает только для старых задач, когда компы на CF были еще старые. Чтоб не менять массово TL, обошлись вот таким недорогим хаком.
1) Нет, я такого не помню, в 2009 еще не участвовал в ACM. Помню про фейл, кажется, 2011 года (когда полуфинал впервые был в Виннице и Бухаресте), но тогда по-моему проблемы с другим были.
2) Когда я говорил о тайм лимитах на codeforces, я имел в виду следующую фразу из советов для авторов: "Time limit не менее 1 секунды, и не менее 2(time_limit авторского на java)." (надеюсь я не разгласил ничего тайного)
3) В такой ситуации подход, описанный Egor мне кажется оптимальным — давайте использовать мультитест.
4) Уже не буду участником, спасибо за предложение, я не готов пока что дать какой-либо ответ (хотя не понимаю, почему именно Ваших задач должно становиться меньше). Поймите — я же написал эти вещи не для того чтобы кого-то обидеть или для чего-то такого. Проблемы таймлимитов на украинских этапах поднимаются постоянно, это можно проследить даже по комментариям к этом посту про 1/8. До полуфинала остался месяц, и я подумал, что если есть шанс повлиять на исправление этой проблемы — почему бы это не сделать.
Вообще я с моим сокомандником привыкли больше к стандартым ТЛ в 0.5 1.0 или 1.5 сек. Когда же увидели на задачу 0.2 сек то немного растерялись. Хотя был такой момент, не знаю, то ли компьютеры во Львове слабые, то ли сервер сильный, но задача ускорилась чуть ли не в 3 раза на сервере.
Где и когда можно будет найти список команд, которые прошли на SEERC?
скоро на сайте тут (вижу часть команд Центрального,Восточного и Киевского региона,скоро и по остальным регионам будет информация)
а почему столько команд прошло? Мы заняли низкое(непроходное) 14 место по восточному региону, а в списке есть наша команда? И не только наша из тех, кто не должен был проходить. Или я не правильно понял ту таблицу??
если не ошибаюсь, 8 команд всего должны проходить же
P.S. Я доволен, конечно, просто интересно, не очепятка ли это
P.P.S. Судя по всему, некоторые команды дисквалифицировали, и поэтому мы прошли
Аж 3 штуки из топ14? Это единичный случай, или такое в норме вещей?
у меня есть подозрения, что там так же есть те команды, что прошли в Харьков, т.е. не в полуфинал асм
А кто то знает, есть ли дорешивание 2-го этапа?
Есть http://olimp.vntu.edu.ua/cgi-bin/new-client?contest_id=117
А где можно взять логины и пароли?
Логин и пароль с соревнования. Правда это киевский контеcт, возможно и в других регионах открыто дорешивание.
а может кто-нибудь залить в тренировки? или выложить тесты?
Кто-то знает, есть ли дорешка с полуфинала?
Для тех кому не написали на почту. С 23-го было открыто дорешивание. По всем вопросам обращатся к Петрову.