Shafaet's blog

HackerRank HourRank 13
By Shafaet, history, 8 years ago, In English

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.

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

Comments Comments (22)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

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 !

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

Can anybody show the HackerRank T-shirt? I've wanted to see it since my first CodeSpirit!

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

It's very good to see the change in the scoring system and the formation of subtasks. Finally the much awaited change.

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

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.

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

How to solve Coprime Conundrum ?

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

    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

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

      Thanks a Lot , just asking why you did not use the euler phi function ? Is it not simpler to implement ?

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

        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

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

          http://ideone.com/nGUThy

          This is one of the accepted solutions . Please explain the coPrime function ?

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

            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

            for (int mask = 0; mask < (1 << numP); ++mask)

            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.

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

      Thanx pandey , you made my day buddy , bhgwaan tera bhalla krein , teri bachein jiye tu khub fulle falle

      → Reply