zemen's blog

By zemen, history, 8 years ago, translation, In English

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!

  • Vote: I like it
  • +86
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest will be started in 45 minutes.

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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