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
Auto comment: topic has been updated by kevinsogo (previous revision, new revision, compare).
This one was easier than usual
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. :)
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 :).
Second one was an interesting problem for newbies like me . Got to learn something new.Thanks.:)
How to solve first problem?
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.
The easy problem was too difficult, the moderate problem was too easy — that's how I see 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!
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.
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.
That's an interesting suggestion, thanks!
I think problems A and B should be harder ... I don't have any Idea about C
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 :)
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?
I used this algo : just sort the array , then you should defeat a suffix and eat a prefix
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]
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]
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....
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
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
How to solve the Hard problem(third one)?
How long does it take for ratings to update?
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.
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
Thanks for your explanation. I have understood it now. although I feel that I have to work on my mathematics.