Блог пользователя zemen

Автор zemen, история, 8 лет назад, По-русски

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!

  • Проголосовать: нравится
  • +86
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

High quality problems, we are right here waiting for you.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been translated by zemen (original revision, translated revision, compare)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The contest will be started in 45 minutes.

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Ээээ, а это так и предполагалось, что в Tripartite Matching заходит тупой квадрат: для каждого ребра a - b в графе G1 проверяем все возможные вершины c за O(degG2(a) + degG3(b)) ??

Я честно пытался сдать N2 / 32, но получал какие-то странные RE, и отослал это в качестве дебаг-сабмита. Проходит максимум за 0.17 секунд, контртест — три одинаковых графа-звездочки.

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    У меня было решение за O(n5 / 3) времени и столько же памяти. Оно зашло.

    UPD: В разборе пишет такая фраза: If |B| + |C| < sqrt(n), то перебираем все возможные пары. Может я чего-то не понимаю, но это вроде как за sqrt(n) * sqrt(n) = n работает.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да, для конкретного выбора a при фиксированном B, C достигается n операций, но амортизированно для всех B мы перебираем все элементы в C, |C| < sqrt(n), значит всего O(n * sqrt(n))

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Фрагмент кода:

        for (int v: a) for (int to: b) {
                res += e3.count({v, to});
        }
        

        Когда a.size() = sqrt(n)/2 и b.size() = sqrt(n)/2, в результате получается n/4 операций.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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!!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Хочу поделится впечатлением о данном контесте с вами( занял 12-ое место, но...).

К задачам A/B никаких претензий нет( бруты вроде не заходили).

Задача С — пишем то, что написано в условии, получаем O(N * M)-> 1023 и 90% баллов.

Задача Д — перебираем ребро первого графа, зная вершины A, B пересекаем множества ребер с ними ( std::set_intersection) и прибавляем это к ответу. Итого, O(N * M)->1010 и 100% баллов.

Ну и задача Е — делаем то, что в условии, предварительно подвесив дерево за рандомную вершину и сохраняя размер в поддереве. Как всегда, O(N * M)->1010 и 92% баллов.

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can someone plz give some hints regarding the sqrt decomposition solution of last question Tree splitting. Thanks.