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
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!
Starting in 20 minutes.
There is one more problemsetter : EMINAYAR :D
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:
Or just remove partial scoring entirely. I don't like coding wrong stuff on purpose :/
sorry about that but i was expecting my challenge will used in weekly contest. Many coders could solve in weekly contest.
Wait, you didn't know it was going to be used here?
They told me this morning. Actually it is my mistake. I didn't thought such kind a problem.
How to solve when gcd(P, 10) = 1?
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?
My solution is only for P = 2a5b (otherwise bruteforce).
(-_-)
You only solved the hardest part of the problem? haha
it is sarcasm? because i think it is obvious how to solve for such P, but need to more coding for pass TL.
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.
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.
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)?
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
Let f(a)=2^(2^a). Then, f(a)=f(a-1)*f(a-1)
please explain how.
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).
22a = 22a - 1·22a - 1 = 22a - 1 + 2a - 1 = 22·2a - 1 = 22a, because 2x + y = 2x·2y and 2·2x - 1 = 2x.
can u provide the link to the editorials .. not able to find it
just open the problem and you will find a tab above named editorial
Superpowers of 2: I thought this won't pass, so didn't even try using it during the contest.
Python solution:
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.
i think it works this way but not sure
akulsareen already mentioned 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