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.
Fun facts:
This contest is the first rated contest on Hackerearth.
There are prizes, too.
Good luck, have fun!
Is it rated?
I'm intrigued to know how did people find the problem-set.
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?..
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.
Auto comment: topic has been translated by Yury_Bandarchuk (original revision, translated revision, compare)
How to solve this problem : https://www.hackerearth.com/march-easy-16/algorithm/benny-and-queries-marcheasy/
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:
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.
Time Complexity: O(nlogmax(Ai))