Errichto's blog

HackerRank HourRank 6 — short contest for both divisions
By Errichto, 8 years ago, In English

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

  1. Endagorion
  2. LayCurse
  3. riadwaw
  4. I_love_Tanya_Romanova
  5. tabasz
  • Vote: I like it
  • +67
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

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

    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?

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

      So, why won't you try both?
      Well, finally, that's a real challenge going on ;)

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

      Actually both platforms do this rather often. Seems that they just do not care.

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

Contest will start in two hours. Remember to hurry in other contests if you want to win them all today.

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

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.

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

    Problem-set was nice. Good job.

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

    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.

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

      Read the editorial for C. You will be surprised :)

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

        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 :/

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

    Nice problemset, thank you. :) faced some problem implementing binary search in second problem,managed to solve it in 52 minutes.

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

    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 !

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

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 array dp[][][] (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.

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

    Didn't manage to do that in time, but solved got 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

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

      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 was 1 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).

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

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like 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.

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

        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 :)

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

        Actually, this is exactly my solution.

        → Reply