| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Этап Открытого Кубка 6 мая пройдёт на задачах Чемпионата Урала 2012 (то есть по сути, это перенесённый с 30 апреля Гран-При Урала).
В связи с этим командам, участвовавшим в Чемпионате Урала, в зачёт Кубка пойдёт показанный на Чемпионате Урала результат.
Если кто-нибудь знает актуальный (неактуальный у меня и так есть :) ) телефон Олега — скиньте в личку плиз
А почему нельзя посмотреть текущий монитор? (div 2)
За что минусуете? На момент написания сообщения монитор для див. 2 был действительно недоступен.
Уже вроде можно. Как решать M?
Заметим, что длина ответа не превосходит 2k...
Как это заметить ?
Не знаю, спроси у Hohol
Толком не знаю, как доказать, но раз ты спрашиваешь как заметить, объясню как я заметил.
Заметим, что максимальный ответ, меньший единицы, достигается отрезком вида 11111011111 (k-1 единиц 0 k-1 единиц). Любой отрезок с большим отношением числа единиц к длине обязан содержать k подряд идущих единиц, в таком случае просто возьмем их и получим ответ 1. Каким-то образом это связано с тем, что длина ответа всегда не превосходит 2*k-1.
Доказать можно так:
Пусть есть ответ длины 2*L. Тогда разделим его на 2 половинки длины L. В левой x единиц, в правой — y. Для удобства будем считать, что x>=y. Частота в левой половинке x/L, в целом куске (x+y)/2*L<=x/L.
Теперь, если длина ответа 2*L+1. x — сумма первых L элементов, y — сумма последних L элементов, опять считаем, что x>=y. Если по середине стоит 0, то аналогично четному случаю приходим к ответу длины L. Если по середине единица, тогда частота в целом куске (x+y+1)/(2*L+1), частота в левом куске длины L+1 (x+1)/(L+1).
Покажем, что (x+1)/(L+1)>=(x+y+1)/(2*L+1). Преобразуя получаем x+1>=y+y/L. Неравенство верное, причем в равенство оно обращается только если y=L, т.е. когда ответ не содержит нулей, в этом случае мы можем взять в качестве ответа любые L единиц, в противном случае ответ улучшится, значит ответ не максимален. Таким образом, всегда можно ответ длины L уменьшить до L/2 (округленное вниз).
Отправка банана в прошлое с помощью микроволновки и визуальная новелла "Песнь Аси" порадовали ^_^
В F правильно каждый раз выбирать самый короткий путь и ходить по нему? Если нет, то как ее решать?
Мы решали динамикой: вершина и бул. Бул означает пришли ли мы в вершину суперпрыжком или обычным. Переходы такие сначала посчитаем сумму по всем сыновьям если мы прыгнем в них обычным образом плюс сумма по всем сыновьям количество личстьев в их поддереве. Теперь перебираем сына в которого пойдем последним вычитаем из суммы значение обычного прыжка и прибавляем кое-что еще (значение динамики в сыне с булом единицей плюс количество листьев если у нас бул равен 0).
Сюда ещё можно добавить и референсы к Макроссу.
А также к несколько менее известным Terra E, Gunbuster и Aria.
И Акросс думаю тоже
Да, Excel Saga упустил. Так же как и Texhnolyze.
Кто-нибудь знает, из-за чего ловился WA 51 в А?
И вообще, правильно ли там жадно набирать очередь двумя указателями (отсортируем исходный массив, дальше meet-in-the-middle)?
Я отсортировал массив и шел по нему слева направо. Для каждого невыбранного
a[i]необходимо взять в пару наименьшийa[j], такой, чтоa[i]+a[j]>s(я это поддерживал в мапе). Если такогоa[j]нет, то плохих пар больше вообще не будет.Хмм, а meet-in-the-middle не то же самое сделает?
Я могу показать код, возможно, где-то просто ошибка в реализации.
Не понимаю, что такое meet-in-the-middle в этом контексте. Но мне известно, что нельзя решать так же, но с идти конца массива, это WA (хотя пока не понимаю, почему).
http://pastebin.com/eevsTWeb
Всё-таки я ошибку так и не нашёл. Ни в алгоритме, ни в реализации.
Ну я делал почти тоже. Вот мой код — http://pastebin.com/kLQvvqht
Получилось внезапно — ошибка в том, что я зря отдельно в очередь писал тех, у кого ai = = s.
Очень просто же, тест: 5 7 5 3 1 1 4
У тебя получается: 3 5 1 1 4 (ответ 3), а правильно: 3 5 4 1 1 (ответ 4)
А, ты по другому шёл. Ну мы пары формировали с конца и числа, не вошедшие в пары, выводили с конца. Если сначала остаток выводить, то вот тест сверху валит.
Одни из самых поганых условий, которые я когда-либо видел. Невозможно ничего понять. Громкое ФИ авторам.
Я так и не осилил ни одного (пытался прочитать С и F — никакого толку)
А можете высказать чуть более конкретные претензии? Кроме поганости перевода на английский. А то я ни на онсайте подобных претензий не слышал, ни по монитору не замечаю никаких намёков на проблемы с пониманием.
Я читал условия на русском. У меня были некоторые трудности с пониманием задач C и I. Пришлось перечитывать несколько раз, сопоставляя с сэмплом.
Проблем с неправильным пониманием не было. Были проблемы с абсолютным непониманием условия. Например в задаче С даже после двух полных прочтений условия непонятно было что вообще сделать нужно. Все условия были излишне замусорены легендами, которые было очень трудно отделить от самих условий. P.S. Чуть не забыл к таким условиям прилагались максимально капитанские семплы.
Плюс за замечание о сэмплах. Присоединяюсь.
Я попробовал прочитать C. В самом деле очень непонятное условие. Явным образом не написано что надо найти. Видимо, четко понять условие можно только реверс-инженирингом сэмпла.
Кроме выше сказанного в ряде задач какие-то моменты были написаны в разделе Input/Output. Я все-таки считаю, что этот раздел неспроста часто называется "формат входных-выходных данных", что бы писать там именно формат, а не ключевые моменты условия.
И в следующий раз пусть кто-то не имеющий отношения к подготовке попытается прочесть и сказать вам, вообще хоть что-то понятно или нет. Я не знаю, как у вас, но в саратовских соревнованиях часто пропагандируется философия "если условие не ясно с первого прочтения кроме особых моментов, то это плохое условие".
Кроме того, если красивая сказочка засталяет участников очень сильно напрягаться при прочтении, то нафиг такую сказку?
P.S. ладно мы, у нас была просто тренировка, но мне жалко те команды, для которых это было официальное соревнование.
Условия на вычитывание постороннему человеку мы и так давали, и некоторые не совсем удачные места по его просьбе правили. Но существенных проблем с пониманием у него не возникало.
Насчёт философии — да, у нас она немного другая. Если участник не умеет отделять зёрна от плевел, а сказку от сути — это проблема участника. И поэтому у нас были и есть большие литературные сказки, в которых вся суть может быть размазана по тексту. И чтение таких сказок — это тоже своеобразная тренировка.
s/литературные/графоманские/
тренировка к чему — вылету на Марс? :)
Многие хотят добавить свою "особенность" в соревнование. На мой взгляд, желательно, чтобы эта особенность нравилась участникам. Видимо, не все авторы контестов так считают :(
Чемпионаты Урала всегда были достаточно неформатными соревнованиями. Бывали и задачи, где не было условия, но был чёрный ящик, который нужно было воспроизвести. Были задачи с нечёткой формулировкой. И на любое отклонение от стандарта всегда находятся недовольные, в какую бы сторону это отклонение не было. И находятся те, кому эти особенности нравятся. Просто первые обычно кричат об этом громче, потому их лучше заметно.
Я только за нестандартные отклонения — это же развитие (или хотя бы попытка :). Но если каждый год делать такие своеобразные условия и каждый год слышать множество недовольных отзывов — наверное стоит задуматься?
По мне условия как условия. Правда я только русские видел. Проблем с пониманием не было. Правда задачу С не читал.
про описание ключевых моментов условий в Input/Output
Это ещё что, вы задачу Google Code Jam 2012 :: 1B Round :: Tide goes in, tide goes out читали?
P.S. Ещё один замечательный пример — региональный этап всероссийской олимпиады, задача "Космический кегельбан" (геометрия, 3 задача второго дня). Там то, что в сотни раз упрощает задачу (по сути ключевой момент условия), описано в "Формате входных данных".
что вы хотите мне этим сказать? я выразил мнение, что так делать очень плохо что сейчас, что в GCJ, что в любом другом соревновании
А как все сдавали G? У нас были какие-то пляски с epsilon'ами и WA на >70 тестах. Или там предполагалось в integer'ах/rational'ах писать?
У нас было много wa82, прошло в даблах, только один момент в длинке на c++
Еще хотелось бы узнать с какой точностью получает ответ авторское решение?
Ну учитывая, что тут всё можно посчитать абсолютно точно в квадратичных иррациональностях с длинкой, то скорее всего у авторов есть такое решение. Если нет — то они не очень правы :)
Все авторские решения либо в целочисленной длинке, либо в BigDecimal'ах. И если у участников заходило решение в даблах, то это недоработка тестов и на тимусе подобные решения будут исправно валиться.
У нас кстати зашло решение в даблах сегодня :)
Когда задачи будут на тимусе?
Не раньше начала июня. Ближайшая неделя и без того перегружена контестами, потом все способные проводить контест уедут в Варшаву болельщиками. Да и хочется найти другого переводчика и всё перевести заново — уж слишком русское строение предложений для английского текста.
а зачем так делать?
В Петрозаводске не один раз пытались поднять проблему, что никто из участников не умеет оценивать точность вычислений в своих решениях и пишут как пишется, потом с эпсилонами колдуют. Вот это — ещё одно напоминание о том, что не любое решение достаточно точно. А вообще, если хорошо представить происходящее, то целочисленное решение оказывается ничуть не сложнее вещественного. Зато немного развивает пространственное воображение.
Ну не знаю, на Java дабловое решение переделывается в "целочисленное" (учитывая, что мы работаем только с числами вида a + sqrt(b), где a, b — рациональные) за 5, максимум 10 минут. А на c++ за конечное время на контесте не переделывается. Так что это задача не на "развитие пространственного воображения", а на "шаманство с eps" либо "кодирование на джаве" :)
У меня в решении не было чисел вида a+sqrt(b), мне хватило операций с векторами (сумма, разность, векторное/скалярное произведение). И у меня даже не было длинки как таковой — я решал в парах <long long, double>, этого достаточно, чтобы при данных ограничениях оно считалось точно. Просто подход к решению, чтобы в нём не было корней, несколько другой. И тут-то и требуется пространственное воображение.
Не вижу ничего хорошего в том, чтобы решить задачу, оценить точность и понять, что надо в дополнение к 100 строкам красивого правильного кода написать 200 строк технической банальности.
Этак интересные соревнования по спортивному программированию превращаются в скучную рутину.
Кстати, похожая ситуация с длинными числами в задаче про плоды (по крайней мере у нас).
Плоды решаются в лонг лонгах. В меньших ограничениях её не дать — тогда она решается тупым разложением на множители и становится совсем неинтересной.
на самом деле цель благая, я помню прекрасно холивары в ПЗ, но тогда и ограничения нужно давать 109?
у нас прошло в даблах путем стопицотзапихивания
10^9 не стали давать именно для того, чтобы не требовалось на плюсах писать полноценную длинку. Казалось, что и при 10^5 по точности дабловые решения должны надёжно отсекаться. Оказалось, что нашими тестами — нет. Ну да, наш косяк.
У нас прошло решение в long double, может проходит и в double. О погрешностях вообще не думали. Можно сказать прошло с первого раза, после исправления багов в формулах :)
Идея была следующая. Повернем всю картинку так, чтобы лучи, по которым движутся дроны были в плоскости xOy. При этом для удобства сделаем, чтобы один луч стартовал в (0,0), а второй луч в (a, 0). Тогда задача сведется к задаче на плоскости, а ее решить довольно просто. В этом решении точность могла теряться только при повороте картинки.
А может кто-нибудь код по D показать, пожалуйста, не понятно где набажили :(
Был бы рад, если б разморозили табличку.
До закрытия Кубка Векуа этого было делать нельзя. Сейчас на сайте Кубка таблица разморожена и результаты интегрированы в общий зачёт.
Что-то пока не видно размороженных резов на сайте кубка
http://www.opencup.ru/index.cgi?data=macros/stage&head=index&menu=index&stg=5®ion=main&ncup=ocb&class=ocb
Спасибо
Кто-нибудь получал WA #12 в I? Написал довольно очевидное решение. Переберем сколько слева и сколько справа располагается кораблей с таким же классом как и известный. А дальше нужно дополнить позиции слева, кораблями с классом меньшим чем известный, и справа кораблями с большим классом чем известный. Все решается через кол-во сочетаний.
Код в студию!
Вот
Путём сравнения этого решения с почти таким же, но получающим AC, и последующего рефакторинга первого во второе было выяснено, что WA12 -- это на самом деле ML12.
Спасибо. Печально, что система выдала неправильный вердикт. Да и на ML поскупились явно.
64 мегабайта — стандарт для уральских задач. В этой задаче этого хватало с многократным запасом, памяти требуется o(N).
Жаль, что система мне об этом не напомнила :)
...в то время, как во всем остальном мире стандарт уже давно 256...
Это где, на Topcoder например? :)
В АСМ задачах. И таки на ТС тоже давно пора поменять
Сперва бы компиляторы лучше обновили. А ML — фиг с ним.
Да на TC давно пора увеличить TL до 256 метров. Я 2 раза не сдавал задачу из-за того что слишком сильно поджимал массивы и решение падало.
ну если в задаче расчитывается, что ее надо соптимизировать по памяти, логично поставить 64мб (или даже меньше, если понадобится)
Да, такие задачи бывают. В этом случае МЛ обычно выделяют жирным. Я против подобного МЛ по умолчанию
Можно было хранить треугольник Паскаля векторами...(N^2)/2 как раз хватало.
Да, нам примерно так пришлось извращаться. Когда считали C(n,k) c помощью факториалов — получали TL35, наверное слишком много модулей было. Полное хранение C-ек давало MLE, поэтому мы стали хранить только половину этой матрицы, т.к. C(n,k) = C(n,n-k), и тогда только зашло.
Ты предпросчитывал обратные значения к факториалам?
Я, например, посчитал по формуле три строчки треугольника Паскаля. Этого в задаче достаточно.
Да, я препросчитывал обратные значения к факториалам. Про три строчки не знаю, задачу писал Никита, а я ее запихивал)
У нас прошло и с предподсчитанными значениями факториалов и обратных факториалов. Я тоже немного боялся что может заТЛить из-за кучи операций взятия по модулю, но прошло сразу. Причем локально работало очень быстро.
У нас не прошло с предпросчитанными факториалами (но не обратными), но это легко исправилось сохранением всех цэшек заранее, т.к. верхний индекс у цэшки принимает только три возможных значения.
Чеерт, действительно, всего три значения. Не заметили на контесте, долго шаманили.
Я, наверное, очень сильно туплю, но, пожалуйста, расскажите решение L (найти последние 3 не нулевые цифры числа N!(1 ≤ N ≤ 108)).
Посчитаем кол-во двоек и пятерок, дающих нам конечные нули. Далее за O(N) можно найти ответ. Каждое число, пока есть лишние 5-ки и 2-ки делим на 5 и на 2. Далее берем его по модулю 1000 и умножаем на ответ, который тоже берем по модулю 1000. Нужно еще учесть, что в нем могут получится ведущие нули, например 8!
Когда прочитал ваше сообщение, очень увидился.
Думал, как может пройти 2*10^8 взятий по модулю.
Написал решение по вашему разбору.
http://pastebin.com/NzNsB219
В нем есть assert(n<=1e7);
Но задача зашла. То есть не было ни одного теста, где n>10^7.
В ограничениях на задачу было написано, что n<=10^8.
Как-то не хорошо получается))) Написано одно, на деле другое.
На контесте у меня была похожая идея, как написал Jokser но меня вообще испугало ограничение в 108, да и наткнувшись пару раз на скорость тестирующих машин на Opencup (довольно медленные), я решил писать хитрее с прекальком небольшим.
Где-то накосячил, получал WA 15.
Я тоже получал WA 15, ошибка была в прекальке.
На локальном компьютере подобное решение на тесте n = 108 работает за 1452 мс, в то время как ограничение было 2000 мс; надо думать, на тестирующем сервере время не сильно отличается. Так что всё хорошо.
сколько-сколько?! о_О
У вас не комп, а зверь какой-то.
Во вкладке запуск на кф работает 5.5секунд.
Интересно. В запуске на Codeforces — 2980 мс. Скомпилировал как 32-битную программу и запустил на том же компьютере — 2699 мс. 64-битная магия!¹
Насчёт ограничений тогда беру свои слова обратно.
¹Видимо, потому что переменная-аккумулятор —
long long.Запуская решение под разными компиляторами, увидел интересную вещь:
Если res и x хранить как long long, то
под msvc2005 программа работает 7.44сек
под gnu c++ 4.6 программа работает 5.5сек
Теперь. Если res и x хранить как int, то
под msvs2005 работает за 1.1сек(!!!)
под gnu c++ 4.6 работает за 3.22сек
Какие-то непонятные различия в скорости))
1e7 <= 1e8. Все ограничения соблюдены. )))
А где можно надыбать положение? Не вижу на сайте опенкапа
Здесь
Спасибо
Можно ли в задаче D ждать на планетах? То есть приехать в момент времени x на планету, а уехать в x+y...
а) Это нигде в условии не запрещено б) Это показано в семпле, например.
Спасибо, значит ошибка у меня была не в этом :)
а) -- это отличный аргумент. В условии также не запрещено уничтожить повстанца межпланетной пушкой, например. У "самого талантивого спецагента" с машиной времени просто обязана быть межпланетная пушка, а с ней даже летать никуда не надо.
Ну на самом деле, руководствуясь только здравым смыслом, условием и семплами можно было понять все задачи. Правда, некоторые моменты все же были очень расплывчатыми и нечеткими.
Например, в этой задаче было написано что оказываться на одной планете дважды рискованно и нужно стараться так не делать, но нигде четко не написано, что нельзя дважды в одно время попадать на одну и ту же планету. Было ощущение, что можно вывести любой ответ, а потом подать апелляцию с формулировкой "но я же старался не дать агенту встретиться с самим собой". Хотя, ясно что просто так это бы не упоминали в условии, так что в решении это само собой соблюдалось.
А как же это: "But remember that if you will be at least twice in the same planet at the same time, you will be able to face yourself. Since such a meeting would be likely fatal, it can not be allowed until the job will be done." "Но помните, что если вы дважды окажетесь на одной и той же планете в одно и то же время, вы рискуете столкнуться с собой. Поскольку подобная встреча наверняка окажется фатальной, её нельзя допускать, пока задание не выполнено."
ПС Только сейчас понял претензии, но по-моему они еще более глупые, чем просто недочитать условия.
Ну встречу-то допускать нельзя, но там же не сказано что я гарантированно встречусь с собой. Там сказано "вы рискуете столкнуться с собой".
Вы бы не могли подсказать, что в 5-ом тесте по задаче D?
Ты, скорее всего, не учитываешь случая, что чувак может придти в вершину, навернуть по циклу, придти в эту же вершину раньше, а дальше прождать и встретиться сам с собой.
Пример: 2 2 1 1 5 0 1 2 6 7 1 2 5 7
В 5-м тесте всего одна вершина и нужно найти путь в прошлое. Причём есть пути как с ожиданиями, так и без них.
Спасибо. UPD : только что получил АС :)
Народ а как участвовать в московском контесте в альтернативное время?
Обратиться к координатору сектора, далее от него получите инструкции.
Так и сделал :-)