Codesprint 5 Hackerrank experience !!

I participated in the codesprint 5 that was held on january 18-19 ’14 organised by hackerrank as many leading tech companies use result of this contest to interview new employees and interns 😉 . At first i’d say the problems were really good and i enjoyed it really while solving them (infact that should be the main thing ofcourse ).  Though the start timing (in india) wasn’t the best but that doesn’t affect much (to me atleast ) as it was a 24 hour long contest and second your rank doesn’t depend your submission timing as two person will get the same rank as long as they have same points and thats the good part of such long contest i think . There were 11 problems  that span the CS disciplines of varying difficulty. I managed to solve 7 problems (4 having perfect score and 3 partial ) and ranked around 150 worldwide (around 60 in india) . I know that is not good (but i’d say not bad too 🙂 ) and i could have done better than that !!

one thing that i really hate is that in one of the problem one can get around half of the total points just by printing the output of test cases. I came to know this after looking submissions of some of participants after contest (though i informed them about it & they said they will definitely resolve this issue ) but I wasn’t expecting it in such a contest and that is one part that hackerrank should look to. Apart from that the contest was really good.
A brief description of some problems and how did i solved them :

• Is fibo :
  This problem was an easy one , the problem is : you are given an integer N , you have to tell whether a given no belongs to fibonacci series or not . one can do it easily by storing all the fibonacci no upto 10^10 in an array initially as there will be only around 50 fibonacci no upto 10^10 & then check whether N is in precalulated array or not. Another method is checking wheter 5*N*N+4 or 5*N*N-4 is perfect square or not . if yes then N belongs to fibonacci series else not .

• Matrix tracing :
  This was also an easy one , problem is to count no of ways to reach from (1,1) to (n,m) in matrix . only right or down moves by one cell are allowed from any cell .so the no of  ways are :(n+m-2)!/((n-1)!*(m-1))!  modulo it by 10^9+7 &  for calulating modular inverse euler’s theorem may be used (thats the important part in this question ).

• Special multiple :
  This was good problem ,the peoblem is to find least poistive multiple of no. N which consists of 9’s(atleast one) and 0’s . As N<=500 so one method is precalculate all the multiple of number N<=500 & store them as all multiple will be less than 10^18 which can easily fit in built in data type. second and more better method (that i implemeted ) is by using BFS & it’ll work even if N is large. It’s really a challenging task to implement this by BFS 😉 . think it in this way  : let the required no be Z so that Z%N=0 .one need to save the remainder instead of Z. Now start with 9 & do BFS & don’t consider the branches that have same remainder as earlier(mark the current modulus every time as visited so one don’t require to visit it again).

• Hyperrectangle GCD :
  This was bit tricky for me but i managed to solve it , problem is ,given n dimension hyperrectangle , in which each hyperrectangle cell addressed at (i,j,k…) has a value equivalent to GCD(i,j,k..) . the goal is to sum all GCD values & print result modulo 10^9+7. This was nice mathematical problem.

  The main idea is to use euler totient function(phi(N)) and some of the facts:

  ∑ _d|N (d * mu(N/d)) = phi(N)

  ∑ _d|N (phi(d))=N

  gcd(d1,d2,d3,…dn)=g <=> gcd(d1/g,d2/g,d3/g……,dn/g)=1

  one can try to solve this problem keeping in mind the above facts.

• In two other algorithmic problems i didn’t got the full score so i’d  not state them here.

  finally the most fun part of the contest (and keeping alive the thrill during the contest ) , a multiplayer game . I didn’t got much time to solve this problem (can’t fight with my sleep ) but i really love such type of problems. initially i solved it using greedy approach which got me nominal points , & then adding some randomisation helped me to get li’l bit more.

  Another nice attraction of this contest was 100$ aws credit for each one who has correctly solved atleast one problem (although i don’t have any plan now of using it) ;).

Thats it 🙂 .if anyone would like to discuss or add alternate solutions or anything , then please add them in comments 🙂 .