ma5termind's blog

HackerRank 101Hack 29th Edition
By ma5termind, 9 years ago, In English

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.

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

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

Auto comment: topic has been updated by ma5termind (previous revision, new revision, compare).

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

Please provide me feedback on the problem set so that i can prepare a even better contest next time.

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

    Problems like "copy-paste treap" are boring :(

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

      But problems like "copy-paste palindromic tree" are not, aha.

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

        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 ;)

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

    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

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

      Thank you Xellos for you feedback. I will keep this in my mind while preparing problems for a contest in future again.

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

    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 std::map to maintain the masks. This 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.

    UPD OK, I accidentally used long long instead of int here :) But usually ML is double of the memory used by the author's solution, I have some doubts about it in this problem :)

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

Solution of Xaero And The Enigma Hacking without treap: #oQF6U0

Btw, has anybody write it from scratch?

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

UPD: My fail. I've misread problem statement, such problem was in NEERC 2012.

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

    IGNORE

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

    It's also an identical version of a standard problem :D

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

      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.

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

Does anyone else have problems solving last 4 tests of "Xaero And The Enigma Hacking" with java?

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

    No solutions on java, mine have same problems + 0 points for EgorK.

    :|

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

      Is it TL?

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

        WA

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

          It is possible to view input and output for problems on hackerrank (in case you didn't know that).

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

            Yes, I checked it. My diff is empty.

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

              I encountered this problem, and asked of admin after the contest. It appears to be a HackerRank's bug, and leaderboard is modified now.

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

Screencast, if anyone cares

UPD: with discrete optimizations again!

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

Can someone explain his solution for D in a bit more detail (with or without treap, doesn't matter).

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

    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.

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

    Please look at the editorial section for the solution and its explanation. I tried my best to explain everything.

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

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!

→ Reply