Yury_Bandarchuk's blog

Invitation to HackerEarth MarchEasy
By Yury_Bandarchuk, 9 years ago, translation, In English

Hello CodeForces Community,

I would like to invite you to participate in HackerEarth March Easy Round that will be held on Tuesday, 01 of March. The duration of the contest if 3 hours.

The problems were set by me (Yury Bandarchuk) and tested by RomaWhite (Roman Bilyi). The difficulty of this round will be like usual Div. 2 Round or a little bit easier.

As usual all the problems will have partial scoring.

In any case, Good Luck && Have Fun all of you! See you on round!

UPD: Contest is over! Congratulations to winners!

Also, sorry for bugs with problem "Benny and Triangle", but in any case I hope you liked the problems.

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

»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Fun facts:

  1. This contest is the first rated contest on Hackerearth.

  2. There are prizes, too.

Good luck, have fun!

→ Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Is it rated?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm intrigued to know how did people find the problem-set.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Weird that City was solved only by 19 people, it is quite simple.

    For Queries, naive solution passed 50% of tests, I was surprised for 1010 to pass. (though TL was quite large, 4 seconds). And that "solved by 220" was really confusing.

    Segments is nice, I liked it.

    For Triangle — why give a wrong formula?..

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      It was not a formula. It was a part of editorial that somehow appeared in sample explanation :).

      It's luck, that it was a little bit wrong and therefore you have to think by yourself.

      → Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve this problem : https://www.hackerearth.com/march-easy-16/algorithm/benny-and-queries-marcheasy/

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +6 Vote: I do not like it

    I use a trie on my solution. Suppose queries are in the form 1..R instead of L..R. You can answer queries by increasing R mantaining a trie with all the bitstrings from a[1..R]. Bitstrings will be added as usual, starting from most significant bits (you should make all the strings the same length. 20 is enough in this case). When you a got a bitstring X, you can find a bitstring Y in that trie that gives maximum in the following way:

    1. find Y from the most significant to the least significant bit.
    2. when processing the i-th bit, if there's some outgoing edge !Xi from current trie node, take it (that's because you are greedily maximizing the most significant bits).
    3. take Xi otherwise.

    Problem here is that you are given L..R queries. To avoid ending up with a Y that does not lie on this segment, you can mantain a maxidx value on every node of the trie. maxidx of a node is the maximum index (on the original array) of a bitstring which ends on the subtree of this node. Given this, you can always take transitions which guarantees you that you will end up with a valid Y.

    1. when processing the i-th bit, if there's some outgoing edge !Xi from current node and the next node maxidx ≥ L, take it.
    2. take Xi otherwise.

    Time Complexity: O(nlogmax(Ai))

    → Reply