darkshadows's blog

HackerRank 101Hack 26th Edition
By darkshadows, 9 years ago, In English

Hello Codeforces community!

I am glad to announce that HackerRank 101 Hack 26th edition will be held on 23rd June 2015 at 16:30 UTC. You can sign up for the contest here.
The problem statements will be available in English and Chinese. 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 me(darkshadows) and tested by wanbo. The contest will consist of 5 problems with variable scoring distribution. I have tried my best to set a balanced 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!

UPDATE1 Scoring is 30 — 40 — 50 — 100 — 120.
Cumulative time taken to solve the challenge is used as a tie-breaker.

UPDATE2 Editorials for all problems have been enabled.

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

Comments Comments (44)
| Write comment?
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Clashes with CF Round 309 now :(

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

    No more clash now ^_^

    Day for CF Round 309 has been changed. 101 Hack will still happen at the announced time.

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

Starts in a few hours.

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

    I love that you are looking forward to it. Hopefully you'll be able to enjoy the contest! I along with wanbo have given our best try to make a balanced and interesting problem set.

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

first three are too boring to solve and last two are too hard to solve — this contest was so unlucky for me:(

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

    The first three are boring, but the last two are quite standard. Still I haven't managed to solve the fifth because I have spent too much time (about 40 mins) on the second problem lol.

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

      Oh, at least I am not the only one :) I spend 50 minutes on 2nd, feel ashamed :)

      In fact I don't agree with Neodym, I'd rather say that last 3 problems are boring (and standard), comparing to first two :)

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

      I did not solve second one. Spent almost an hour on it... What is the idea behind? My code is here.

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

        I can explain what I did .please be patient :P A- rotating ball . B is ball thrown from origin.

        • First I tried sending ball B at t=0. I found position of ball b at time =R (time taken by ball to reach at the circumference with thrown at time =0) if this position was in the first quadrant. Then optimal answer would be the one we get by throwing the ball B at t=0 answer in this was would be "R R%S/ gcd(R%S,S) / S/GCD(R%S,S).

        • if position of ball B at t=R is not in the first quadrant then answer would be "(r/s + (r%s):1?0)*s 0/1" because he can wait for some time t>0 and then throw the ball such that it collided at R,0

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

What's wrong with this approach for 2nd : - r=r%s. if(r belongs to 0..s/4) print r/gcd(r,s) "/" s/gcd(r,s) - otherwise print 0/1 explanation : if r through at t=0 can reach a place in the first quadrant than do so . otherwise it can r,0 point in the next cycle

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

    lets have a good laugh shall we :P .For 2nd I though the answer was of for "testcase_number fraction" :P XD

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

editorials?

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

Almost did task no.4. Suffix-Array + Lcp + Fenwick tree + Mo's algorithm. code However, getting TL... :(

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

    Suffix-Array + lcp is enough.

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

      My solution was an overkill. I used suffix+lcp+2seg trees.
      Can you explain your solution?

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

        In fact it is not that bad, I would not call it an overkill. Constraints are loyal, so I did the same, but using hashes.

        With hashes you can compare two substrings in O(1), this gives you LCP with bin.search only, this gives you SufArray with "LCP+comparing next char" comparator; and instead of using seg.tree of pairs / two seg.trees you may use two Fenwick trees, and code becomes even simpler.

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

        For each index i lets find such f[i], that s[i..f[i]] is unique substring, and s[i..f[i] - 1] is not. That can be done in using suffix-array and lcp. Note, that f[i] is non-decreasing sequence. Really, s[i + 1..f[i] - 1] is substring of s[i..f[i] - 1], so it is non-unique.

        Now, for each query we can answer in : we'll find first segment i..f[i], which intersects with r, let it be q (q=upper_bound(f, r)). Now it's easy to count number of non-unique subsequences in s[l..r]: it's . That's because for all indicies x < q: f[x] < r, and for indicies x > q: f[x] >  = r.

        May be I missed  + 1 or  - 1 somewhere, but I hope that you can get the idea.

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

      Haven't figure out it during contest... can you help me with it?

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

    SA + MO works fine.

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

      I did Suffix-Array + Lcp + Fenwick tree + Mo's. :) but getting TL sometimes. Can you share your code?

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

Is there any problem in using Math.floor(1 + Math.log10(number)) to get the digit length? My one test case failed in 3rd question due to that.

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

Is there any edge case in 5th question? I got a seg fault on 3 test cases.

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

    I think it may be due to recursion depth. One of such test cases was a linear graph.

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

      Stack limit is around 106. So, I think there might be some other issue.

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

For 3rd what should be the output for 1 53959375 29374943

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

It is just me or everyone felt that 3rd was quite easier than 2nd ? :P

Edit : I did it with O(17) ad-hoc solution per test case.

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

    The 3rd problem was indeed a piece of cake with DP.

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

      How to solve via DP?

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

      After I wrote the DP, I realized that you don't even have to do that. Once one number gets below its limit (that is, you use a digit lower than the limit), you can always get a 9 on the rest of the digits.

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

    176 AC on second, 220 AC on third. I believe that difference would be even higher in case author swapped these tasks in a problemset — lot of people didn't even tried 3rd because of being unable to solve 2nd.

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

      Fun fact: I earlier had intention of keep 2nd one as the 1st. But wanbo later told me that it might be a little difficult.

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

      This made me wonder if HackerRank will ever decide on implementing Dynamic Scoring in short contests.

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

106 bytes for stack size? Are you seriously? Can you please increase it? As I know, it's a common practice.

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

    I meant that its at least 106. I just found out its 8MB.

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

      OK, 8MB. But it's not enough.

      p.s. 256MB = codeforces stack size.

      → Reply