kevinsogo's blog

HackerRank HourRank 9 — Short contest!
By kevinsogo, history, 8 years ago, In English

Hi all. I want to invite you to HourRank 9. The contest will take place tomorrow (exact time) on HackerRank. There are three problems to be solved in one hour.

For this round I wrote the problems. I hope you find them interesting! wanbo tested them, and other contributors (pre-solving, suggestions, technical help, etc.) are malcolm, satyaki3794, and Shafaet. Thank you for all your help!

The top 10 will get awesome HackerRank t-shirts. Editorials will be available at the end. Good luck and have fun!

Update: Score distribution : 30-50-80

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

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

Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).

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

This one was easier than usual

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

    Congratulations on finishing first! (and finishing so fast)

    Yeah, it was easier. Shafaet wanted an easier HourRank. I had some harder problems but replaced them later with easier ones upon request.

    I hope you had fun even then. :)

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

    In previous three hourRanks, only 1, 0 and 3 people solved all respectively. So we wanted to make it a bit easier this time.

    I hope you still liked the problems :).

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

      Second one was an interesting problem for newbies like me . Got to learn something new.Thanks.:)

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

How to solve first problem?

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

    I went through the array, and then if I found an odd number I would increment it by one and the one to the right of it by one. I would continue doing so, until I get to the last element. If the last element is even, then it works and I output how many times I added one. Else, it doesn't work.

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

The easy problem was too difficult, the moderate problem was too easy — that's how I see it.

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

Following up with the Egor's comment about the contest being easier than usual, I would love to hear opinion on how difficult the contest should be to make it very interesting. When only 1-2 person solve the last problem, is that interesting to top people? If 15 people gets full score, is it good or is it too many? Lets discuss :). Also I would like to hear opinions of beginners too. We want to make the next rounds more awesome!

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

    I found the difficulty level perfect, as a beginner. Problem A was approachable, Problem B a little bit trickier and Problem C subtask something I'd aim for.

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

    I think it could be more interesting if rounds had two hard problems instead of one. There will be more freedom to vary strategy and choice of problems to solve.

    Also the scoreboard on hackerrank is a bit boring, I'd like to see scores for all problems not only sum.

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

      That's an interesting suggestion, thanks!

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

    I think problems A and B should be harder ... I don't have any Idea about C

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

    I think it's okay when 15-20 people fullscore, it just means the last task could be entertaining to average people. Personally, I would love to see more "think — like" problems. I mean that some problems go like "Oh, I have to think about it" and some "Oh, I got the idea in 10 seconds, but I won't code in 1 hour anyway".

    My impression on 80pts problem is probably worsen by the fact that I didn't read that graph is connected :)

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

For the second question i was trying something like this dp[i][j] be the answer for the first i numbers (numbers are sorted) with j=0 if i choose to eat and it being 1 if battle . Also i was maintaining another array of exp[i][j] with the same parameters but i failed.Can someone provide a solution using my approach?

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

    I used this algo : just sort the array , then you should defeat a suffix and eat a prefix

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

      yes that works if we are allowed to sort the values.But consider a different question wherein the ordering matters then we don't know what values we need to eat or fight in the optimum case so i blindly started coding dp solution but still for this new question wherein values should be processed in order someone suggest a transition for this dp[i][j]

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

        something like if j=1 ( ihave decided to fight then we set) exp1 is keeping track of the experience values.

        if(dp[i-1][0]+exp1[i-1][0]*arr[i]>=dp[i-1][1]+exp1[i-1][1]*arr[i])


           {

            exp1[i][1]=exp1[i-1][0];


            dp[i][1]=dp[i-1][0]+exp1[i-1][0]*arr[i];


        }


        else


        {


            exp1[i][1]=exp1[i-1][1];


            dp[i][1]=dp[i-1][1]+exp1[i-1][1]*arr[i];


        }

        but for j=0 i am unable to code a transition.Can someone help? dp[i][0] is either dp[i-1][0] with exp1[i][0]=exp1[i-1][0]

        or

        dp[i][0] is dp[i-1][1] with exp1[i][0]=exp1[i-1][1]

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

    Hey, Javacoder I did absolutely the same thing in the contest and I failed.I'll tell u the reason why as I analysed in detail what I did wrong...

    1> dp[i][j] can never be linear in nature as you may reach a particular index 'i' with different values of S and P. Thus, you may calculate dp[i][j] , however, this value will change when u reach index i with s=w and p=x or something like s=y and p=z...Thus, this dp[i][j], is wrong

    2> In addition, this recurrence will take the maximum at every index. So, u shall try and maximize p at every index i..this is also wrong as u may see in the sample, we take lesser value of p at step 1 and then maximize p at further steps..

    3> Last point, here the recurrece should be dp[i][s][p] as what is the maximum u can get If u reach index i with current value of s and p..However, this would result in a time complexity of O(n*n*max_value_of_p) which is not feasable for TL as well as ML...

    I also made a wrong recurrence and kept on failing throught the contest....

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

      the ambiguity is in calculating the vaue when according to me we have to eat as i mentioned when j==0 how to decide whether to take dp[i-1][0] or dp[i-1][1] if this is resolved then according to me it is fine

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

        It will still be wrong, as you cannot maximise value of p at every i.. Even if u eat at index i, you will take previous maximum of p, however u may have to take lower value of p at previous index too.. and maximise at some greater index

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

How to solve the Hard problem(third one)?

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

How long does it take for ratings to update?

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

In the third problem, I was able to think upto forming the expression (a+b.n)%M. But I couldn't maximize it. Can anyone explain how to maximize it. I read the editorial but I'm still unable to understand it.

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

    We have to find maximum x such that x = (b.n)modM and x≤M - a - 1. Let g = gcd(b, M). (b.n)modM can't be smaller than g(except 0) but there's at least one integer n makes g = (b.n)modM. So x = k * g. Maximum k equals (M - a - 1) / g(integer division). Finally ans = a + ((M - a - 1) / g) * g

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

      Thanks for your explanation. I have understood it now. although I feel that I have to work on my mathematics.

      → Reply