Hi. I want to invite you to HourRank 6. The contest will take place tomorrow (exact time) on the HackerRank platform. The duration is exactly one hour. I think that both beginners and experienced participants will find problems interesting for them.
There are problems from me and from forthright48. I want to thank Radewoosh for helping me with preparing problems, and for testing. I also thank malcolm, wanbo and Shafaet for testing and the technical help.
Limak needs you! I wish you great fun and no frustrating bugs. Looking forward to seeing you!
Besides fun, top 10 will get HR t-shirts. Good luck.
WINNERS
Why do you do this?
Both contests at the same time on the platforms with almost the same name :)
Is it some kind of a strategy to reduce the amount of participants from competitors?
I've talked with both platforms a moment ago. They are both cool about setting dates to avoid collisions but now it is too late to change anything about tomorrow. I hope it won't happen in the next month.
Besides, you have half an hour of HE-Easy before HR-HourRank. I'm sure some people will try to compete in both. And after the end of HourRank there is still Easy going on. So, why won't you try both?
So, why won't you try both?Well, finally, that's a real challenge going on ;)
Actually both platforms do this rather often. Seems that they just do not care.
Contest will start in two hours. Remember to hurry in other contests if you want to win them all today.
This time I would really appreciate feedback from lower-rated participants. How hard should be first two problems? It's hard to prepare four problems and give something interesting for everybody.
btw. for each problem you can find an editorial by clicking "Editorial" above the problem.
Problem-set was nice. Good job.
I read first 3 three problems. Problem set was perfect for a participant like me. Solved first problem(equivalent to div 2A), implemented O(n^2) approach for second problem(Div2C) and passed few test cases in third one.
Read the editorial for C. You will be surprised :)
Now i am sad. :( Submitted C with just an wild guess (didnt have much time after solving B) , felt happy with the bonus 15 points in contest time , and now i see handling only one case could give me full points :/
Nice problemset, thank you. :) faced some problem implementing binary search in second problem,managed to solve it in 52 minutes.
Fine problemset! For my opinion the first two tasks should have had a little lower level, but for me they were interesting :)
I always prefer tasks as third on contests like this. Good task, with nice short solution :)
See you on next round !
My big congratulations to all who solved the last problem. Endagorion has the same solution as the intended one (you can check the editorial) but with two times shorter code . And LayCurse solved it so amazingly that I want to describe it here. We will binary search the answer.
So, for the fixed value of the expected value
dp[N][M][0](N boys didn't dance, M girls didn't dance, 0 pairs danced) we want to check whether it's too small or too big. Now we can iterate backwards over O(N·M·NM) states and easily calculate values of an arraydp[][][](storing expected values), without an extra array for probabilities. Because we know the (assumed) expected value of the situation when a pair is upset and we must start on the next day. You can find find LayCurse's code here.Didn't manage to do that in time, but
solvedgot accrpted last problem with iteration of this dp until TL.Is it possible to create test that will fail my solution?
BTW, what is the 10th test? It was only test that gave WA on 5k iterations
It's not hard to come up with a test with the biggest answer and it is
1 30 0.1. The 10-th test was1 30 0.0997. Your solution was intended to be a reasonable brute force. It must work well because r ≤ 0.1. It wouldn't work with r close to 1.0 though (or n = 1 and m bigger than allowed in constraints).Thanks
I might suggest a way to improve binary search solution by removing the binary search :). Let's assume dp[N][M][0] equals to some unknown X. Now in all formulas for dp we can use X instead of dp[N][M][0]. Thus dp[i][j][k] will be of the form A[i][j][k]+ X B[i][j][k]. The only thing left is to find X from equation X = A[N][M][0] + X B[N][M][0] which is trivial. Essentially binary search tries solving exactly it.
Doesn't sound similar to the intended solution but again we have two arrays. Will there be some simple relation between them and ones in the intended solution? But still, nice observation.
Well... It seems that A is expected number of dances if we assume that when bad situation happens we immediately stop. And B[i][j][k] is the probability that we will run into a bad situation. So the result A[N][M][0]/(1-B[N][M][0]) becomes pretty much like yours :)
Actually, this is exactly my solution.