Привет всем!
Сегодня в 19:30 по московскому времени состоится Codeforces раунд #142, который пройдёт в обоих дивизионах.
Задачи составляли я, Евгений Вихров (gen), и Андрей Вихров (andreyv). Мы оба — студенты Факультета компьютерных наук Латвийского университета. Это наш самый первый раунд на Codeforces!
Раунд нам помогал готовить Геральд Агапов (Gerald), а условия на английский язык по традиции перевела Мария Белова (Delinur). Большое спасибо! Отдельно хочется поблагодарить также Михаила Мирзаянова (MikeMirzayanov) за отличную систему подготовки задач Polygon.
Мы надеемся, что каждый сможет найти себе задачу по вкусу. Постарайтесь прочесть условия всех задач!
Желаем интересного раунда!
UPD1: Разбалловка задач динамическая, однако задачи будут упорядочены в порядке возрастания предполагаемой сложности.
UPD2: По техническим причинам продолжительность контеста увеличена на 5 минут. Приносим извинения за неудобства.
UPD3: Разбор опубликован здесь.
Раунд завершён! В первом дивизионе все задачи покорились 5 участникам, во втором — первой 4-ке. Поздравляем победителей!
this is the last contest at the 'Contests' page. again:-( so, approximately in 7.5 hours the list will be empty. makes me sad so much!
Разбалловка перед началом — будем надеяться!
Будем надеяться на динамо? :)
Перед началом — это за 5 минут или все-таки раньше?
не за 5 — за 8...
Зачем пороть ерунду ? Можете вспомнить контест для которого не была обявлена разбаловка ?Или если узнать об этом на пять минут раньше что-нибудь поменяется.
Да: необходимо тупо сидеть и ждать...
Почему ерунду? мож, забудут) Но, если серьезно, то, может, организаторы попробуют поэкспериментировать и объявить разбалловку уже после раунда — чтобы не повторять ошибки раунда предыдущего? Авантюрная идея, согласен, но все же — чем не идея?
если взять в расчет, что сервер раза 2 упадет перед началом, то думаю, торопиться не стоит
Вот-вот : уже сейчас падает!
Неее, стоИт! Ещё бы 5 минут продержался, потом полегче будет! :)
Динамическая розбаловка! Класно!)
"розбаловка" — это как?
Это как "разбалловка", только с двумя ошибками :-)
Искреннее спасибо за SG1! ^^
И за SAO ^_^
У меня одного Codeforces глючит?(
Продлили специально для тех, кто не успел досдать
Но не продлили для тех, кому больше нравится взламывать задачи, а не бесполезно ломать голову над задачей,которой не сможешь решить
CF ужасно лагал, в конце контеста сервер упал на 10 минут, что не давало ничего засабмитить Oo
Да вот же ж. Неужели он всего 5 минут стоял. Кажется, поболя будет.
Плохо что добавили 5 минут, а сайт висел минут 10! + лаги
я не пойму, С что ли баян какой-то??? почему многие сдавали ее в первые 20 минут, и некоторые с див2 на 11 минуте ее сдавали?? как она решается? и правильно я понимаю, что кто знал идею — немного додумывали и профит?
Nevermind.
Sorry, bug with language.
C is cool, thx 2 authors.
dangerous, вы читаете мои мысли
Задача становится лёгкой, как только подумаешь, а не подсчитать ли количество разноцветных треугольников.
(The task C is a easy, when you will try to count the number of colorful triangles.)
разноцветных по ребрам что ли?
Я на месте придумал. Ответ — .
Чтобы это понять, надо удвидеть, что бывают 4 картинки на трех вершинах. И в указанной сумме квадратов две нужные учтутся с коэффициентом 3, а не нужные — 1.
все довольно просто же. сначала прибавим к ответу все треугольники. потом, для каждого ребра Элис вычтем из ответа n-2. Потом для каждой вершины прибавим к ответу C(cnt, 2). Можно убедиться, что его мы не посчитали ни одного разноцветного цикла, а все одноцветные посчитали ровно 1 раз.
ля, ну баянистая же идея, как я не вспомнил подумать в этом направлении...
И вообще это английский тред, что и вызывает кучу минусов.
(And this is an English thread, which is also the reason for minuses I suppose.)
Давайте решать так. Сначала посчитаем сколько всего треугольников в графе у Боба. Будем добавлять ребра по одному и смотреть, сколько треугольников даное ребро отняло у графа Боба. Пусть ребро исходит из v1 в v2, всего мы до рассмотрения текущего ребра добавили s1 ребер с вершиной v1, и s2 с вершиной v2. Тогда логично, что текущее ребро отнимет от графа Боба (n-2-(s1+s2-мощность пересечения множеств уже добавленных соседей для v1 и v2)). Заметим, что вот эти вот общие вершины образуют треугольники с v1 и v2 в графе Алисы, а больше никакие другие вершины не образуют(на текущем этапе). А значит, можно просто не отнимать их, но и в конце не добавлять треугольники в графе Алисы. Очень крутая задача, ИМХО.
Very annoying contest.
Итак. Задача D div 2 (B div 1). Писал Дейсктру. Обновлял путь таким образом: брал за растрояние минимальный момент времени такой, что "В этот момент времени можно вылететь с планеты", с учетом того, что в последнюю планету растоянием называлось "время прибытия". Что не так?
Спасибо. Именно это у меня и не было учтено. Будет совсем обидно, если в дорешке сразу зайдет с исправлением этого бага (не учел, что из первой вершины не всегда удается отправиться в нулевой момент времени)
UPD. Не совсем обидно, схватил еще и тл. От которого легко избавиться
Ждем скорейшего разбора..
Контест годный, мне понравился. А вот как решать D (div.2)? Дейкстра с кучей?
Вроде да.
мне кажется, или Б все таки стоит свою 1000, а не 500?
А почему в Б дейкстра с модификацией не заходит? модификация такая: когда релаксируем ребро, бинпоиском поищем нужный момент времени и посмотрим предподсчитанное для него значение следующего свободного момента времени? Для n-й вершины такую операцию производить не будем. ва7. это вообще неправильно или баги?
У меня такое претесты проходит.
У меня такое же прошло претесты.
У меня тоже такое претесты не прошло :(
вроде прикол с последней вершиной... или что-то такое
да. + есть прикол с первой вершиной (я ее не учел)
Ждём повальные тлешки по D? )
Я проверяла на рандомных макстестах решение за n^2 log n, почему-то оно работает достаточно быстро :)
Странно, я проверил на
5000
100000 99999 ... 95001
Локально — 4.5 сек
У меня 0.437 работает.
Правда фиг знает, правильно ли вообще)правильно, правильноУ меня работало 0.8 и упало на 15-ом по неправильному ответу. Фиг знает, почему, идея-то вроде была адекватная. Обидно
Задача D уже была как задача F SNSS2011, только с бОльшими ограничениями.
Кстати, ее тогда мало кто сдал, хотя пытались многие)
Еще она же была на пробном туре Ижевских сборов.
Или я что то путаю?
Я например умею решать только за квадрат эту. Что там та же задача не проверял.
Я тогда тоже придумал за квадрат, но есть решение за с каким то извратом на декартовых деревьях.
Сейчас то решение за нлогн не смог вспомнить, придумал заново какое то решение за квадрат, не успел закодить :D
Да, действительно это одинаковые задачи ansf = n + 1 - ansd.
Rating will be update?
I want to thank codeforces for making me understand all sort of network errors that can happen :P This would help me in future.
PS : Translation errors were like ice on the cake... One amusing error : "All those errors belong to me" , This was the real culprit.
who can you tell me solution problem E div 2? thanks you
Look at what PavelKunyavskiy said.
В задаче B можно приезжать в последний город в момент t, даже если в этот момент t туда прибывают путешественники. Огромное спасибо за это авторам.
А если внимательно прочитать условие, в момент времени t нельзя было уезжать из города, а не приезжать.
из условия это очевидно. там написано про "выезжать из города".
Приезжать в город можно всегда. Нельзя выезжать из города, если в это время прибывают путешественники. Не вижу проблем.
Это-то все четко было указано. Смущает другое. В условии сказано, что "Джек начинает путешествие в момент времени 0". Все таки не совсем очевидно из условия, что он ждет свою очередь, перед тем, как отправиться.
Эпично ступил, сорри.
Да ничего. Я думал, что он просто выедет в момент времени 0. Посмотрел сейчас прошедшие чужие решения. Все то же, что у меня, только еще, так сказать, прорелаксирована первая вершина.
Я тоже из-за этого минус получил. Вообще это странно. Я думал, что уезжать одновременно можно, а приезжать — нет.) Но, перечитав пару раз условие, я осознал небольшую проблему.))
К сожалению, мы пропустили этот момент и не пояснили полностью. Извиняемся за недочёт.
Формально вы его вроде бы пояснили полностью, но понять было и правда трудно. Можно было просто сказать, что вершина блокируется, если там кто-то сейчас есть. Сложность задачи не поменялась бы, зато всем все было бы понятно.
Ну не совсем. Если сказать что вершина блокируется, многие бы могли подумать что и прилетать нельзя, если там кто-то есть.
Скажите пожалуйста, в D div 1 такая динамика: d[i][j] — за сколько минимум операций можно получить посл-ть, заканчивающуюся на число <= j (j это суммы [0..i], [1..i], ..., [i..i])?
Если бред, расскажите правильный вариант, пожалуйста!
Изначальный вариант заходит: http://www.codeforces.ru/contest/229/submission/2287457
У меня другая: рассмотрим префикс столбов до i включительно, пусть в конце стоит объединение столбов с j по i включительно, какое минимальное количество объединений нужно затратить? решение за квадрат лог.
У меня такая же динамика, только за квадрат. Можно зафиксировать левый конец отрезка, а потом двигая правый, параллельно двигать указатель на самую первую возможную позицию начала предыдущего отрезка. И за О(1) искать минимум.
Да, я сначала написал пост, а потом понял, что ее и за квадрат двумя указателями можно.)
Казалось бы, правильный вариант. dp[i][j] — минимальная сумма в последней башне, если мы на префиксе j выстроили i башен. Тогда, чтобы сделать переход, нам надо найти самое правое k, такое, что sum(k+1, j) >= dp[i-1][k]. Эта функция неубывает при возрастании j и фиксированном i. Пойдем двумя указателями и все посчитаем. кроме dp[i][j] будем поддерживать булевскую ex[i][j] (возможно ли разбить), которая тоже монотонна при фикс. i. По ней переходы такие же. Дальше найдем наибольшее u, такое что ex[u][n] = 1. Ответ n-u.
УПС, ВА =(
У меня зашло это решение, только я бинпоиск делал вместо двух указателей. Наверно в реализации ошибся.Не могу осознать, напишу как у меня было: dp[i][j] — минимальная высота последней башни, если мы обработали i башен и сделали j операций соединения. Тогда мы можем либо пристыковать следующую башню к нашей (dp[i][j] -> dp[i+1][j+1]), либо построить новую башню из кусков справа, т.е. башню, полученную из соединений всех башен от i+1 до k, такую, что dp[i][j] <= h[i+1] + ... + h[k] (dp[i][j] -> dp[k][j+(k-i-1)]). В последнем случае надо брать минимальное такое k, я это делал бинпоиском, с помощью префиксных сумм.
Бинпоиск не использует идею о том, что место перехода неубывает с возрастанием j. Но это, казалось бы, правильно.
ой, это все вранье, начиная с того, что dp[i][j] монотонна при фикс. i =( ни черта не монотонна.
[user: dangerous]
че за трэш?
как написать твой ник?
how to write your handle?
Yep, at least I can do so: _dangerous_
it doesnt work
Yes, that's why I said
at least
;)Please tick "In Russian" if you don't write in English :)
Скажите пожалуйста почему падает по времени? http://mirror.codeforces.com/contest/230/submission/2276216
Проверка на простоту до корня слишком долгая. Нужно Решето Эратосфена строить
у меня спокойно зашло решение за
Число имеет 3 делителя тогда и только тогда, когда является точным квадратом какого-то числа. Вроде бы просто: извлекаешь корень (если не квадрат, то ответ нет — у него сообще четное кол-во делителей), а дальше проверяешь на простоту. Можно предпросчитать все простые до 10^3 (sqrt(10^6)), и дальше искать двочиным поиском. Но это чтоб уж совсем точно не затлешилось.
Точным квадратом какого-то простого числа, извиняюсь.
Здесь можно редактировать сообщения. :)
Там x до 10^12. Так что посчитать надо для 10^6. Плюс отмечать можно в массиве bool, что позволит нам после предподсчета проверять на простоту за О(1). Я, конечно, понимаю, вы фиолетовый и все дела, но все-таки прочитайте нормально задачу, перед тем, как что-либо объяснять.
UPD. На счет фиолетового уже не актуально. Не подумайте, что я злорадствую. Желаю вам снова стать фиолетовым после следующего раунда. И себе тоже :) И всем синим :-D
Или я чего-то не понимаю, или я все-таки прав с 10^3. Кстати да, про массив bool я почему-то не подумал, спасибо.
И все же...Очевидно, что нужно проверить, является ли число квадратом простого числа. Для этого мы извлекаем корень (он, кстати, <=10^6) и проверяем его на простоту (если он целый, конечно). А поскольку в проверке на простоту надо проверять все простые до sqrt(n), то мы и проверяем до корня из 10^6, который вроде бы 10^3.
Возможно, я жутко туплю. Но сейчас попробую ее сдать.
Выдержка из условия: "n целых чисел xi (1 ≤ xi ≤ 10^12)". sqrt(10^12) = 10^6
UPD. Ааа, понял о чем вы :) Не знаю в общем. Немного не очевидно тогда, как имея корни четвертой степени из x, получить ответ для x.
UPD2. Теперь понял. Для каждого x проверять все это дело, а не делать предподсчет. Тоже норм, если не затлится. Хотя не должно, ведь 10^8 сложность получается, что должно влезать в 2 секунды
Почему не делать? У меня идея вроде бы несложная.
Сейчас дописываю, попробую отправить.
Давайте, а то уже интересно. Я как-то не до конца верю в то, что вы написали.
UPD. Я не разобрал из ваших сообщений, вы точно верно понимаете, когда у числа n ровно 3 делителя? Только в том случае, если его делителями являются: 1, sqrt(n), n. Причем sqrt(n) — целое и простое. Вы это имели в виду?
Да, втупил. Бывает. Все-таки я создавю массив простых чисел.
Ничего страшного :) Зато опыт в копилку.
http://mirror.codeforces.com/contest/230/submission/2287527 N sqrt(sqrt(M)). Заходит довольно-таки легко. Мне просто нельзя переключаться с одной идеи на другую, я начинаю путаться :) Я думал про массив простых, а писал про булевский, будучи уверенным, что они работают одинаково.
It seems that in problem C div1 (triangles) any solution using cin instead of scanf that doesn't have the line "ios_base::sync_with_stdio(0);" gets TLE. I thought timelimits were chosen to allow users using iostream... Is this true?
I've just submitted a solution that got TLE during the competition and it has been accepted changing only cin with scanf.
When there is large I/O(About 100000 or more), you can't use cin/cout without ios::sync_with_stdio(false). Scanf/Printf are OK, but sometimes you should use "getchar" to make it faster.
Great contest! Does pretest 10 contain maxtest? I have 1.6 secs on pretests with solution with 10^6 vectors. Another 10 seconds and I would have submitted fast solution with lists. And I'm really nervous now :)
And after all, it accepted! Runtime is still 1.6 secs after systests
Slow system testing :\ Great competition though, there were some techincal problems at the end but i think extending the contest was a wise decision :P
Почему тл?
I suppose that it's cycles over array t.
но это же всего константа. Очевидно, что он не более 1 раза пройдет по массиву t. итого: 10^5. Неужели для кодфорса это критично???
It's O(n^2) when all edges are from vertex 0, and everebody comes to 0.
In the worst case you will go over array t[u] for every edge v->u.
B: WA67 — маленький INF?
Скорее всего.
Он самый. Максимальный путь — 10^9+10^5+1, сам из-за этого не сдал.
ilona :
Во-первых, выбирай языки правильно. Во-вторых, у тебя подсчёт задержки на точке идёт слишком долго — он вообще квадратный, а по хорошему его надо сделать константным, поскольку, каждую задержку мы обработаем один раз — если мы её уже посмотрели, то она либо меньше всегда будет, либо с этого момента, ведь время в Дийкстре постоянно увеличивается.
почему квадратный? по массиву t мы пройдем в СУММЕ 10^5 раз.
И вот здесь будет квадрат в твоём коде.
нет! Будет линия. он в самом начале для вершины s найдет стартовое расстояние, оно будет 100 000, а потом просто посчитает ответ для вершины 2.
ОК, согласен. Тогда могу сказать, что ошибка в том, что ты считаешь время простоя в вершине, когда ты её обновляешь, а не когда ты с неё идёшь. Это плохо, потому что обновить каждую вершины ты можешь много раз. Например, в таком примере:
(плюсы это не вершины, просто чтобы показать что все рёбра идут в одну и ту же вершину)
ты обновлять самую правую вершину будешь 50000 раз. Если в список её добавить 10^5 запрещённых времён от 0 до 99999, и она будет не последней (после неё представь что есть что-то ещё), то тогда и получится квадрат вроде бы. Или я опять что-то не так понял в твоём коде?
Ребята, что за 10-ый тест в задаче E? Какой-нибудь хитрый крайний случай?
Просто на нём уже несколько человек упало.
Это по сути первый серьёзный тест, там нужно выбрать сначала несколько самых больших, а потом на рубеже остаются 6 элементов, из которых можно выбрать 3.
У автора решение на логарифмах?
Нет, просто в даблах. Но мы сверяли все ответы на решении Java с помощью BigDecimal.
Я выводил не тот элемент динамики.( Тест этот — первый осмысленный.
А я просто неправильно прочитал условие.
Почему ТЛ, 66 тест http://mirror.codeforces.com/contest/230/submission/2284334 ?
У меня там же, тоже не понимаю почему http://mirror.codeforces.com/contest/230/submission/2283365 .
Этот тест отсекает по времени решения, которые по много раз смотрят одни и те же tij (на самом деле хватает одного раза).
Спасибо)
I believe D can be solved in O(n log n), was it on purpose that the limit is low or the authors weren't aware of such a solution?
Isn't that the original solution? Using djikstra with Heap? (sorry thought its div2)
D in Div 1?
Nevermind i thought you meant Div2
It can be solved in O(n).
You don't use dijkstra with heap? Another solution? Can you share it?
Sorry,i meant Div1. Towers
LOL...It seems I'll back to IGM...I'm very happy... in addition I'm going to make my first CF round >.<
OTL, When?
I have prepared the problem statement in Div I already...I need to make some Div II problems and generate the test cases...I think it will be done in this month,(I'm kind of lazy T_T)
Orz..
Guys, what does mean "Orz"? This word is used so often by the Chinese and I never know what does it express :).
edit: googled it, nice :) http://www.urbandictionary.com/define.php?term=orz
I am sorry... ( I just didn't know how to express my Admiration, except "Orz" for a moment.. .
Admire!!! If so, I might not have an opportunity to attend it. TAT...
Да ну что это за фигня с динамической разбалловкой. Я, конечно, все понимаю, но 1000 за Д и 3000 за Е — это не дело. Получается, 4 задачи уровня А и Б из обычного контеста. А последняя не то чтобы тяжелая, но из-за всяких спецэффектов получилось, что за нее баллов больше, чем за многие гробы из предыдущих контестов.
Да клоунада это, а не система. Перед окончанием тестирования тупо сидел и ждал, наберется ли необходимое число ацептов по D, чтоб она стоила 1000, а не 1500...
Мало того, что сама система очень нестабильная, так еще и формулы оценивания как-то подогнать не мешало бы.
Lesson learned for today. Don't ever use Java's sqrt. Nice round :)
Объясните пожалуйста, почему у меня в запуске на тест: 3 1000000000000 1000000000000 1000000000000 выдает: NO YES YES А у меня на компе NO NO NO ? Решение: http://www.codeforces.ru/contest/230/submission/2281434
Перове что бросается в глаза — тип int64_t. Впервые про него слышу, может с ним есть какие-то проблемы в различных версиях. Могу и ошибаться. Просто возможное направление.
int64_t это просто #define int64_t long long (всегда пользовался, проблем никаких не было)
Но в коде нет ни одного дефайна.
извиняюсь, typedef long long int64_t; взято из stdint.h
и еще, если написать cout << a << endl(); то сразу YES YES YES, магия !
А точнее баги оптимайзера, по-моему.
Так как с этим бороться ?
А у меня на этом тесте оно выдаёт это:
спасибо, помогло, надо было maxn сделать на 1 больше; странно что у меня все нормально
I love these questions!
В чем смыл 34-ого теста задачи Adiv1/Cdiv2?
When should we expect rating change?
It will been publish soon, Maybe 5 mins later ... )
динамическая стоимость снова радует: задача С — совсем чуть чуть больше сдач по ней, и стоимость ее 500, согласитесь, такой незначительный разрыв с Б, они должны стоить одинаково
Непрерывную систему надо делать, тем более что технически это должно быть несложно. Баллы можно и до целых округлять.
In div2 problem B, it was asked to avoid using lld. Why?
It's a common thing for codeforces, codeforces doesn't work with lld, just use I64d, it's quite the same. This warning is not specific for problem B, it's usually written on every taks that requiers use of long long integers :)
"%lld" format is used for Linux-based compiler. "%I64d" format is for Windows-based compiler. Codeforces is Windows-based. CMIIW.
I get confused by the statement of problem E. And I can't get the right meaning till now. For example, let's focus on this case: (Final Case #16):
Input 2 3 (endl) 2 2 4 (endl) 1 2 (endl) 1 1 (endl)
I think the answer is 1.0 since we can ask the gold fish to give us 2 gifts with name 1. So finally we could get gifts with value 2 + 4, which is maximal. But the answer is 0.75.
Could you please tell me why I'm wrong? Thanks in advance!
"Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly."
So he'll choose 1,1 or 1,2 uniformly, and there's only 50% chance of getting maximal gifts if he choose 1,2, so the answer is 0.5+0.5*0.5=0.75.
Thanks! Now I understand it.
It turns out that I should read the statement more carefully. By the way, I think examples are too weak (as well as the pretest) such that I can pass it with a totally wrong understanding.
(P.S.: It looks strange that some "\n" disappear in my post, so the data is in a mess. Does anyone know how to fix this?)
I also misunderstood in the same way and just realized that "Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly."
It means he does not only choose the best strategy but any ones as long as it may get him maximum value.
Finally Div 1! :)
solved 4 problems,final tests passed only 1,rly bad contest for me,anyways problemset was nice
Bad luck :(
I liked the non-oeis-problems :) Waiting for the new contest days :D
Взломал одного в своей комнате, так он мне написал в ЛС на своем языке "bahut hack marna aa raha hai sale tere ko.. !!" и фиг теперь поймешь он попросил меня написать на чем я его взломал или он меня оскорбил или проклял =D Даже гугл транслейт не помогает. Кстати, я его попросил на английском написать, так и не ответил =(
Can anybody teach me how to solve E div 2? Thanks for your help!
nice problems. keep up the good work.
"В первой дивизии все задачи покорились"
У нас же звания отменили, давайте все-же употреблять термин "дивизион", а то уж больно выглядит нелепо.
Хм, а как в задаче D div1 надо действовать, чтобы получить неубывающую последовательность на тесте
17
8 6 1 2 3 6 2 2 2 6 6 1 1 1 1 1 1 ?
За 11 объединений (т.е. получается 6 чисел)
Мы с моей программой не понимаем :)
P.S. а, проблема решена. Это как раз надо за 12, а я вывожу 11 :)
Так и нельзя понять, ответ же 12. :)
UPD: Опоздал, видимо.
Ага… (А у нас с Вами рейтинг идентичный :))
Nice.
Кстати C уже была
http://olympiads.ru/zaoch/2011/problems/problems.pdf А тут задача K — логическое продолжение темы :)
On Div-2 problem B, while contest I using (double)pow to get square root from n, and I get wrong answer, then I change into sqrt and get accepted. Whats wrong with pow ? I use this for pow :
double temp = pow((double)n, 0.5);
long long square_root = (long long)(temp);
It is floating point precision issue, I guess.
And where is the editorial?
We are going to publish it within 14 hours.
We have just published the analysis.
Для таких как я, разбор здесь: http://mirror.codeforces.com/blog/entry/5437
В топ-10 одни азиаты О_о
Good contest