Друзья, всем привет!
Через несколько часов состоится очередное соревнование — Codeforces Round 112 для участников Div. 2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Артем Рахов (RAD), Павел Холкин (HolkinPV). Как всегда с нами были Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).
Отдельно хотелось бы пожелать удачи моим сокомандникам, Артему Рахову и Иванову Максиму (e-maxx), которые на днях улетели в США для принятия участия в онсайд-раунде Facebook HackerCup.
Мы надеемся, что сегодняшние задачи понравятся всем участникам, и каждый займет заслуженное высокое место в итоговой таблице :)
UPD: Соревнование завершилось, всем спасибо за участие :) Мы надеемся, что вам понравилось.
UPD: Друзья, предлагаю всем ознакомиться с разбором задач: http://codeforces.com/blog/entry/4124
UPD: Поздравляем победителей!
Полные результаты доступны по ссылке: http://codeforces.com/contest/165/standings
Артему удачи!
а Максу?
желаю всем зла
а Максу?)
All the best to all of us. :)
Разбаловка стандартная?
Если скажут 1500-1500-2000-2500-3000 даже пробовать решать не будешь?
Интересно человеку, вот и всё, зачем минусовать!?
Пытаюсь с вкладки "отослать" отправить не файл, а код. Получаю окошко с багом =(
Почему у меня при нажатии на кнопку "комната" отображается комната №1 второго дивизиона?
Да, тот же баг, комнаты в пер. диве руками искать нужно.
Blog about match with A, B and C explanations
This was a fun problem set, thanks.
Может, есть мысли, как D и E решались? Не минусуйте только.
D — Dynamic Connectivity Problem в почти чистом виде.
из пушки по воробьям, не?
В чем-то Вы правы, но мне ничего сильно проще не придумалось, я и написала DCP.
если честно, я тоже бы написал, если знал)
самое прикольное, что перед контестом начал это разбирать и не успел
На что вы рассчитывали, когда писали, чтобы вас не минусовали?=)
На то что, что бы не ставили 'не нравится'...оО
Кеп.
Скорее всего в Д как-то используется тот факт, что заданный граф — борода:) Я делал так же, как и для общего случая — красил ребра и смотрел чтоб количество покрашенных на пути было 0, когда отвечаю на запрос третьего типа.
Ну факт, что граф -- борода, позволяет нам просто на пути его разбить, не зная H-L. Просто возьмем вершину, со степенью > 2 и разобьем от неё по различным путям, а дальше как обычно.
Обидно, что не заметил.... Но такую задачу можно решать и без ХЛ, да и кода не больше будет, чем если разбивать на пути.
А как ребра красил/проверял?
Через Эйлеровое представление дерева: добавляем вершину в список при входе в дфс, и при выходе из каждого ее сына. При этом храним для каждого ребра его номер в списке прямых и обратных ребер дфс. Если хранить адрес первого вхождения вершины в список, то на отрезке first[x]..first[y] все ребра будут иметь свою пару (то есть для каждого закрытого будет открытое), такой пары не будет только у ребер, что лежат непосредственно на пути от х до у. Как-то так в общем:) http://e-maxx.ru/algo/tree_painting Должно работать, хотя еще не прошло:)
Для каждого пути можно завести дерево Фенвика.
Серьезно?
Я перенумеровал вершины (корень — 1, дальше — ДФС), завел одно дерево отрезков, а дальше, видимо, как у тебя идея.
What is this message? -> "Judge protocol is inaccessible." (I got this message when I tried to hack.)
have u locked ur submission?
yes.
HackID : #36282
Vertect : Unknown verdict:OTHER
Message : Judge protocol is inaccessible.
Maybe someone hacked that solution before you.
Аццкая D, полконтеста на поиски баги. Если кому интересно, 4 претест содержит запрос на расстояние в котором a = b = корень.
Мда, а в это время все решали E.
+1
Да ну, гораздо интереснее (уж как минимум при внеконкурсном участии) читать E->D->C->B->A.
Как минимум, пока пишется что-то простое, в фоне можно придумать что-то сложное.
Заодно, если несколько самых сложных задач не нравятся, можно вовремя решить не участвовать.
Спасибо за очень интересные задачи )
During the contest today, I kept getting WA on pretest 11, during the last 5 minutes (in desperation :P) I spammed a bunch of (long long) (I used C++) wherever i had calculations going on and then i got pretests passed. All my variables were already long longs anyway, can someone please explain what might have happened? much thanks.
type of bits.size is int.
Actually it is
std::size_t.thanks guys :D doh. silly me -_-
Louise Françoise Le Blanc de La Vallière? Is that you?
Any hint on problem D?
I tried using Fenwick's tree. I couldn't finish it in time so I don't know whether that method would have been successful.
Fenwick's tree (or another tree) should be OK for this problem.
We have root (vertex with largest degree) and some paths from root.
I used Fenwick's tree and got Accepted in less than 1000ms. What you should do is just to maintain some paths from root.
I run a DFS from the root through the paths and give each node a unique ID. For example, root node has ID 1, then first path has IDs 2, 3, 4, 5, 6, 7, second path has IDs 8, 9, 10, 11, third path 12, 13, 14 etc.
Also, for each node I calculated the distance between it and the root node.
When an edge is colored white, I call fwt_update(x, 1) where x is the ID of the node right after this edge. When the egde is colored black, I call fwt_update(x, -1).
When asked to tell about the SP between nodes X and Y, there are two cases. Lets assume that Y is further from root than X.
If both X and Y are on the same path, I can express the number of white edges between them as fwt_read(Y) — fwt_read(X — 1).
If X and Y are on different paths, I similarly check if there are any white edges between root and X as well as between root and Y.
Am I right about the idea?
Yeah, your solution is very perfect and convenient,thank you! I got a Accepted that I delete the root and for each chain build a Fenwick tree.Also my code is very long.
Can anyone please explain why beard graph has to be a tree. 1->2->3->1 satisfies as a beard graph but is not a tree. Please correct me if I am wrong
Let the vertex who has the maximum degree be root,if we delete the root,there will be several chains.For each chain,build a segment tree to maintain it.
как решалась Е?
Ну, например динамикой по подмножествам: http://codeforces.com/contest/165/submission/1370354
As it seems E has surprisingly short solution.
Does anyone know where could I read about the method used in solving E?
I couldn't solve problem E in time but had a solution in mind. It involved converting each element of the array to its binary form->reverse it and then create a trie type DS (binary tree in this case). the height of this would at max be 20. Along this trie I also store information of when an element of the array ends in a particular node(call this val A). As well as a information at each node which tells any one of the numbers whioch would be discoverable in the path following(call this val B). Then for each number in the array I travel the Trie. Convert the number to binary and reverse it and then travel it from the front. For each 1 I take the 0 path. For a 0 I search in both path's. DFS in this process should work. If the search string ends at a particular node I return the val B else if any val A is found first before the search string ends I return the val A
Most probably it will time out, as the DFS is not guaranteed to stop very soon.
To solve the problem E, you may can just use the dynamic programming. dp[i] = dp[j], if j is sub-state of i and dp[j] != 0 ( 1100(2), 0110(2), 1010(2), 1000(2), 0100(2), 0010(2) are all sub-state of 1110(2), but you can just use 1100(2), 0110(2), 1010(2) to transfer dp).In the beginning， you just let dp[a[i]] = a[i], the others equal to 0. Finally, you can get answer from dp[(1 << 22) — 1 — a[i]], because (1 << 22) — 1 — a[i] is sub-state of ~a[i] and if (1 << 22) — 1 — a[i] has none-zero's sub-state, dp[(1 << 22) — 1 — a[i]] must not equal to 0.
use long long, instead of int... shouldn't make such a trivial mistake! :(
Yes，you are right. I would be wrong in problem D. My way to solve it may bigger than int...
When will raintings be updated ?
Проявились недочеты в системе подсчета рейтинга. Вот два участника: Gantz и NCoder , первый был выше и выступил лучше, а в итоге оказался ниже. Несправедливо.
Все верно т.к. gants изначально имел 1530 рейтинга,а NCoder 1500,поэтому от первого ждали место выше,чем от 2,а в данном случаи разрыв минимален,и следовательно первому дали поменьше рейтинга,чем второму.
Пусть два участника участвовали в двух контестах. Вначале рейтинг обоих был 1530. Первый контест. Первый из участников выступил "так себе", и его рейтинг остался 1530. А второй слил и стал 1500. Второй контест. Оба участника выступили хорошо, причем первый лучше второго, но в итоге его рейтинг стал ниже, чем у второго, в соответствии с системой переоценки рейтинга. Получается, что участник, который два раза выступил хуже, оценивается более высоким рейтингом. Вот и недочет.
Дело в том, что формула подсчета ожидаемого места для новичка несколько отличается от формулы подсчета места для синего участника с 1500 рейтингом, так что ваши рассуждения неверны.
Не знал, спасибо. А иначе это действительно выглядело бы странно.
Thanks for contest. I like the problems, B and C are good for hacks, but unfortunately I stucked on C :-(
Thanks for contest,E is a good problem, I think for a long time，very happy finally solved。And problem D with problem ——Query on a tree is very similar。：-D
hello! Could you tell me where the problem Query on a tree is? Thank you!
http://www.spoj.pl/problems/QTREE/
В топ-50 подавляющее большинство фэйков -_- у которых в истории по 1-2 контеста
Кто бы про фейки говорил. Сам то вместе с Serzhan читеришь за будь здоров. Взять хотя бы прошлый Div. 2. Решения по C:
Battle_Mage:
1367614
Serzhan:
1367087
И это не единичный случай далеко.
мы просим о любых случаях читерства сообщать любому из авторов в ЛС, вы можете найти ссылки на профили в тексте поста.
То есть это тебя смущает, а то, что в топ 10 только 2 аккаунта похожи на реальные — это нормально?
с чего ты взял? многие участники высокого уровня, пришедшие на кф первый раз, сразу занимают высокое место в див2. Это же вполне нормально? В любом случае, нефиг самому читерить и оправдывать это тем, что кто-то другой читерит
Сравни ТОП-10 div2 в дни, когда раунды для обоих дивизионов, и дни, когда div2 only.
ну не знаю, по прошлым раундам не слишком видны отличия. в этот раз действительно много "новичков", но не уверен, что это не в пределах статистической погрешности
Разница и в более старых раундах видна. За примером далеко бегать не надо — 111ый раунд.
111 и 112 — действительно, согласен. В нескольких до них не особо заметно. Не считаешь, что наплыв участников мог быть связан с анонсом VK cup?
стрелки кидать — это называется)
Editorial??
Waiting for the editorial eagerly. Hope it will be published soon.
Editorial in Russian: http://codeforces.com/blog/entry/4124 Maybe you are in need of google translate.
thanks...:)
It would be nice to have the editorial in english too, just saying...
sorry
I think it's because of
pow(), never use it if you work with integer numbers.This gets Accepted: