Hello Codeforces community!
I am glad to announce that HackerRank 101 Hack 37th edition will be held on 17th May 2016 at 16:30 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.
Problems have been set by Moscow IPT Jinotega (ACM/ICPC WF team): zemen, Arterm, ifsmirnov, and tested by wanbo.
The contest will consist of 5 problems with variable scoring distribution. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.
Good luck and have fun!
High quality problems, we are right here waiting for you.
Auto comment: topic has been translated by zemen (original revision, translated revision, compare)
The contest will be started in 45 minutes.
Ээээ, а это так и предполагалось, что в Tripartite Matching заходит тупой квадрат: для каждого ребра a - b в графе G1 проверяем все возможные вершины c за O(degG2(a) + degG3(b)) ??
Я честно пытался сдать N2 / 32, но получал какие-то странные RE, и отослал это в качестве дебаг-сабмита. Проходит максимум за 0.17 секунд, контртест — три одинаковых графа-звездочки.
У меня было решение за O(n5 / 3) времени и столько же памяти. Оно зашло.
UPD: В разборе пишет такая фраза: If |B| + |C| < sqrt(n), то перебираем все возможные пары. Может я чего-то не понимаю, но это вроде как за sqrt(n) * sqrt(n) = n работает.
Да, для конкретного выбора a при фиксированном B, C достигается n операций, но амортизированно для всех B мы перебираем все элементы в C, |C| < sqrt(n), значит всего O(n * sqrt(n))
Фрагмент кода:
Когда a.size() = sqrt(n)/2 и b.size() = sqrt(n)/2, в результате получается n/4 операций.
Can anyone explain this problem solution in detail : https://www.hackerrank.com/contests/101hack37/challenges/yet-another-minimax-problem I didn't understand the editorial. Thank you!!
Let's build the solution bit by bit from the most significant to the less significant. There are 2 cases:
If the bits at position i are all ones or all zeroes, then it doesn't matter which pair of numbers we chose, their xor will be 0 at position i.
If at position i there are both ones and zeroes, then in any permutation there will be at least one adjacent pair of numbers with xor 1 at position i. Moreover, we can create the permutation adding all the numbers with bit i equal to one first, and then all the numbers with bit i equal to zero, in that way there will be just one xor of adjacent numbers with bit i equal to one. So the maximum xor will be the xor between one element from the set of numbers with bit i equal to one with one element from the set of numbers with bit i equal to zero.
Thanks a lot Morphy
Хочу поделится впечатлением о данном контесте с вами( занял 12-ое место, но...).
К задачам A/B никаких претензий нет( бруты вроде не заходили).
Задача С — пишем то, что написано в условии, получаем
O(N * M)-> 1023 и 90% баллов.Задача Д — перебираем ребро первого графа, зная вершины A, B пересекаем множества ребер с ними (
std::set_intersection) и прибавляем это к ответу. Итого,O(N * M)->1010 и 100% баллов.Ну и задача Е — делаем то, что в условии, предварительно подвесив дерево за рандомную вершину и сохраняя размер в поддереве. Как всегда,
O(N * M)->1010 и 92% баллов.грусть, печаль, огорчение.
Good problemset. I wasted too much time on the easiest problem because I didn't use enough long longs...
In the last problem, I used Fenwick trees over HLD paths to find the sizes of subtrees (when vertex 0 is the root) and count blocked vertices; before answering a query, I'm moving to the highest unblocked ancestor, since the answer to that query is the size of its subtree. When removing a vertex, the size of its subtree is subtracted from each of its ancestors up to that one, so the Fenwick trees have to support the operation "add x to the first i elements".
It sounds complicated, but it's quite easy to write... but with too many silly bugs, like forgetting to read part of the input.
Can someone plz give some hints regarding the sqrt decomposition solution of last question Tree splitting. Thanks.