Hello Codeforces community!
I am glad to announce that HackerRank 101 Hack 29th edition will be held on 23rd September 2015 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 ma5termind 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. Xaero is the main character of the problem set. He is one of the awesome person I met in my whole life. So, your main task would be to help him in each problem. Although, Xaero is smart enough to solve all of these problems but he is quite busy these days.
Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.
Good luck and have fun!
UPDATE
Editorials for all problems are up.
Auto comment: topic has been updated by ma5termind (previous revision, new revision, compare).
Please provide me feedback on the problem set so that i can prepare a even better contest next time.
Problems like "copy-paste treap" are boring :(
But problems like "copy-paste palindromic tree" are not, aha.
I have nothing to do with such problems :)
Anyway if you prefer to copy-paste Manacher's algorithm + suffix tree, it's up to you ;)
Problems 2, 3 and 5 were about equally easy IMO (which is: pretty easy, one was tree DP, one bitmasking prefix-sums-thingy and the last one sweeplining and classic DP, which is all basic algorithmist's equipment). Except 2 was just a slight variation on a standard problem and 3 totally a standard problem; the last problem wasn't, but it's far below what I'd expect (I solved it in 20 minutes).
On the other hand, problem 4 was above what I'd expect from problem 4. My solution to the "reversals in permutation" subproblem (the hard part) was sqrt-based, we store info about the current permutation as
, where P0 is explicitly known and P1 is a sequence of arithmetic segments with difference + 1 or - 1; when there are more than 
segments, recover P1 and merge it with P0 (and set P1 to identity); otherwise, a reversal in P1 can be performed in 
time. I wonder if there's a simpler solution...
The sqrt-decomposition didn't come immediately to me, but even then, it does require a bit of careful work with reversals in P1... definitely harder than the last one.
I struggled a lot with the language. There should be better, or existing, language review.
Overall, one of the easier contests even for HR. At least I finally solved everything :D
Thank you Xellos for you feedback. I will keep this in my mind while preparing problems for a contest in future again.
The memory limit in the third problem should have been larger. I had troubles with creating an array of 226 elements (I received Abort Called on Hackerrank) and had to use
solution had TL only at last testcase, so I had to add a tricky optimization with char array, maintaining the last testcase when the mask existed modulo 256.
std::mapto maintain the masks. ThisUPD OK, I accidentally used
long longinstead ofinthere :) But usually ML is double of the memory used by the author's solution, I have some doubts about it in this problem :)Solution of Xaero And The Enigma Hacking without treap: #oQF6U0
Btw, has anybody write it from scratch?
An option with neither treap nor rope is sqrt decomposition. http://pastebin.com/5xJjXtf1
UPD: My fail. I've misread problem statement, such problem was in NEERC 2012.
IGNORE
You can see any accepted solution.
It's also an identical version of a standard problem :D
Great Xellos !!!! I agree to each and every point that you have stated above. I also feel sorry that i was not able to deliver you an interesting set of problem but now you are saying that 4th problem is also an "identical version of a standard problem" which i guess you enjoyed the most in the whole contest. Please do not call everything standard if you know a lot of things or solved a lot of problems. I tried my best to come up with the ideas.
This is about the 3rd problem, not the 4th.
then sorry again !!! :D :D
Does anyone else have problems solving last 4 tests of "Xaero And The Enigma Hacking" with java?
No solutions on java, mine have same problems + 0 points for EgorK.
:|
Is it TL?
WA
It is possible to view input and output for problems on hackerrank (in case you didn't know that).
Yes, I checked it. My diff is empty.
I encountered this problem, and asked of admin after the contest. It appears to be a HackerRank's bug, and leaderboard is modified now.
Screencast, if anyone cares
UPD: with discrete optimizations again!
Can someone explain his solution for D in a bit more detail (with or without treap, doesn't matter).
Let's replace every '?' with its number. Then after processing m queries (with or without treap :) we will know how string will look at the end. So we can merge equivalent positions in connected components and check if there are any contradictions. If there is no contradiction there will be some "free" '?'. Let's find representation of k base 26 and replase such free '?' with letters from this representation.
Please look at the editorial section for the solution and its explanation. I tried my best to explain everything.
isn't this contest rated ? the ratings didn't update till now!
the problems were hard for me. However, the editorial is really well written thanks for your efforts!