Another HourRank round is on the way! The time is 4th October 2016, 16:30 UTC. You have just 1 hour to solve 3 algorithmic problems.
The authors for this round are ma5termind, scorpion and me. wanbo tested the problems. tunyash and allllekssssa helped a lot to finalize the selection.
We tried our best to make the round interesting. All the problems have short statements. There are subtasks in each of the problems, so I highly recommend you to read all the problems.
Scores of the problems:
- 25 [70% score for the 1st subtask]
- 50 [30% score for the 1st subtask and 60% score in the 2nd subtask]
- 60 [25% score for the 1st subtask and 70% score in the 2nd subtask]
If two person has the same score, the one who reached the score first will win.
Update
The contest has ended and rating updated. Let us know your feedbacks!
Top-10 winners will get a cool HackerRank t-shirt.
First HourRank round was held before one year ! I am pretty happy because this round getting more and more participants and I hope that this number will continue to grow in next months :)
I participed in several rounds as setter and normal contestant and I hope it will be the same situation now when I started with university.
About this round I think tasks are interesting. I can not estimate level of tasks at all, for me it was harder than usual rounds, but again with many subtasks where you can get easy points and good place on leaderboard.
It was planned to be used one my task, but after finding the same task on google we decide to remove it... So I believe that won't be frustrating situation like on many rounds and you will enjoy in new problems.
Good luck and have fun !
Nobody cares
Can anybody show the HackerRank T-shirt? I've wanted to see it since my first CodeSpirit!
My friend's design
WOW, it's very cool! I'm looking forward to getting it!
You can buy it here: teespring.com/world-champion-on-hacking
I don't want to buy it, I want to win it!
Too expensive .
It's very good to see the change in the scoring system and the formation of subtasks. Finally the much awaited change.
I've won three T-Shirts from HackerRank for different contests.
They only gave me one option... I literally have three of the exact same HackerRank T-Shirt.
Please, give me one :)
I know that feeling. I've got the exact same CodeChef T-Shirt 10(!) times :D
How to solve Coprime Conundrum ?
We aim at finding p,q such that p,q are coprime and p.q==k and also 1<p<=q<=k. Now it can be seen clearly that p and q can both take values from 1 to root(n) as k varies from 1 to n.
Now lets fix value of p by looping from i=1 to root(n), now we need to find q such that p.q<=n(As k can any value from 1 to n). So the problem boils down to finding for every p the numbers in the range [p+1,r] which are coprime to p. Here r=n/p. Analyse the inequality p.q<=n you will understand why the range is required.
Now solving the new task in hand , we will calculate the reverse ie we will try to find the multiples of p in the range [p+1,r] and subtract them from total numbers in range. To find multiples efficiently first we will find the prime factors of p and store them in an array after that using the inclusion-exclusion principle we can find total-number of multiples in the range.
To implement this efficiently for any p make a function solve(p,r) which will find the number of coprimes to p in the range [1,r]. So to calculate in the range [p+1,r] the answer will be solve(p,r)-solve(p,p). Finally just add this value for all the p values.
Complexity Analysis : The main loop is O(root(n)) clearly and prime factorization can be done in O(logn) now the tricky part is here , the recursive function is exponential in nature ie 2^(no. of prime divisors) in the question n<=1e9. So at max 10 distinct prime divisors can exist ie 2^10 is ~1000 so this solution will pass in O(root(n)*2^(log10(n))). worst case 10^4*10^3~10^7 quite acceptable :)
I Hope this helps , here is my AC code
Thanks a Lot , just asking why you did not use the euler phi function ? Is it not simpler to implement ?
In this task you can calculate for [1-p] using phi(p) but for finding numbers coprime to p in the range [1-r] phi(r) will not be useful and thus you will have to call solve(p,r) itself. So i felt lazy writing phi() :P which could be achieved by the solve() function itself :D .. fewer lines of code are always better :P
http://ideone.com/nGUThy
This is one of the accepted solutions . Please explain the coPrime function ?
This is the iterative implementation of the recursive inclusion-exclusion function. Pay close attention nump in this code denotes the number of prime divisors of the number as i had explained the recursion's time complexity will be exponential the main loop
this has the same time complexity of 2^(num of divisors) which is exponential itself and in the inner loop,mask is used to check whether the ith prime factor has been already multiplied or not by checking if the ith bit is set in the mask. Work it out on your notebook once you will get it :)
PS: This code is typical implementation to find out all the subsets of a set.
Thanx pandey , you made my day buddy , bhgwaan tera bhalla krein , teri bachein jiye tu khub fulle falle
bleh
pandey , codeforces hai ye , tumhare hostel ka mess nhi hai jo kuch bhi likhte rhoge
move on