dyps's blog

[HackerRank] 101 Hack Dec'14
By dyps, 9 years ago, In English

Hello Coders,

The December edition of 101 Hack is here. This time we have 5 interesting challenges lined up for you.
The contest commences on 18th Dec 2014 at 16:30 UTC, and will run for 2 hours. You can sign up for the contest here.

The problem statements will be available in English, Russian and Chinese.

Top 10 on leaderboard get cool HackerRank T Shirts

Problem Setter
Shaka Shadows EMINAYAR

Problem Testers
dyps
wanbo

Please try all problems, Editorials will be available at the end of contest.

GL&HF

Update

The contest has begun!!

Update 2

Editorials are live!

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

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

Starting in 20 minutes.

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

There is one more problemsetter : EMINAYAR :D

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

If you're going to let people race to squeeze partial points out of the last problem, it would probably be better if you actually gave some info so that we don't have to blindly code stuff hoping for points.

Something similar to:

  • In a set of test cases worth 10.43 points, max(NQ, N2) ≤ 107.
  • In a set of test cases worth 20.62 points, gcd(P, 10) = 1.

Or just remove partial scoring entirely. I don't like coding wrong stuff on purpose :/

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

    sorry about that but i was expecting my challenge will used in weekly contest. Many coders could solve in weekly contest.

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

      Wait, you didn't know it was going to be used here?

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

        They told me this morning. Actually it is my mistake. I didn't thought such kind a problem.

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

    How to solve when gcd(P, 10) = 1?

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

      Let's store all the suffixes modulo P. Then for segment [L, R] suf[L] - suf[R + 1] = number(L..R) * 10something. When gcd(P, 10) = 1 number(L..R) is divisible by P when suf[L] = suf[R + 1]. Now it's reduced to pretty standard problem about counting binomial (A[i], 2) over all possible i where A[i] is a frequency of number i over segment [L, R + 1] .

      I wonder what was your solution? There are at least 3 large(hence expensive!) test cases with P = 2k. I bet there are also test cases with P = 5k, or P = 10k. Did you use it?

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

        My solution is only for P = 2a5b (otherwise bruteforce).

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

          (-_-)

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

          You only solved the hardest part of the problem? haha

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

            it is sarcasm? because i think it is obvious how to solve for such P, but need to more coding for pass TL.

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

              Not at all, I saw the solution to the gcd(P, 10) = 1 case almost immediately, and spent the rest of the contest trying to solve the 2a5b one.

              The final solution was just a mix between the two, and you can see the editorial takes more time to explain the second case as well.

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

    Sorry about this. We had to remove our previous challenge as the idea was very similar to another challenge previously published and we used an un-used challenge. We will be careful not to make this error again.

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

      Considering how many new problems are used in contests all the time, that isn't something you can hope to decently avoid. For example, the 3rd and 4th problem are just applications of well-known stuff and I think I've solved the 2nd problem (or something similar to it) recently...

      It would've been better to focus on diversity, considering 3/5 problems were about math.

      Also, there were no problems left that aren't about taking the time to squeeze out points (this hard problem would really fit into a weekly contest much better)?

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

The editorials solution for the 4th question is needlessly complicated. Here is a simpler approach.

Let f(a)=2^(2^a). Then, f(a)=f(a-1)*f(a-1)

Since, a was reasonably small for a linear approach just do a linear scan from 1 to a and get the answer. My solution

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

    Let f(a)=2^(2^a). Then, f(a)=f(a-1)*f(a-1)

    please explain how.

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

      Since, (a^b)^c = a^(b*c).

      Therefore, f(a-1)*f(a-1) = f(a-1)^2 = (2^(2^ a-1))^2 = 2^((2^a-1) * 2)

      Also, a^b * a^c = a^(b+c)

      therefore, 2^(2^a-1 * 2^1) = 2^(2^(a-1 + 1)) = 2^(2^a).

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

      22a = 22a - 1·22a - 1 = 22a - 1 + 2a - 1 = 22·2a - 1 = 22a, because 2x + y = 2x·2y and 2·2x - 1 = 2x.

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

can u provide the link to the editorials .. not able to find it

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

Superpowers of 2: I thought this won't pass, so didn't even try using it during the contest.

Python solution:

a,b=map(int,raw_input().split())
print pow(2,2**a,b)

Can someone tell me how Python's pow(a,b,c) works exactly? I thought it won't work in cases where gcd(2a, b) ≠ 1.

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

akulsareen already mentioned it.

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

The gradient of the problem-set was not good. 4 easy problem and 1 hard problem. All the easy problems were very standard. The play with words problem was derived from this post on geeksforgeeks. The example test case included the subs-sequence "geeksforgeeks" too.(It may be a coincidence, but such standard problems should not be used in international contests)

Seeing the editorial of "a superpower of 2" , it looks like that testers did not check the constraints of the test cases. They seem to forget about the linear time solution :P

→ Reply