allllekssssa's blog

HackerRank HourRank 4
By allllekssssa, 8 years ago, In English

Hello Codeforces community!

I'd like to announce the fourth HackerRank HourRank round! The contest will be held on Sunday, 3th January 2016. You can sign up for the contest here. Top 10 winners on the leaderboard will receive a HackerRank T-Shirt.

Problems have been set by Shafaet Ashraf (Shafaet) and Aleksa Plavsic (allllekssssa). Competitors will have 1 hour for solving 4 problems with variable scoring distribution. Contest are rated for all HackerRank users. We want to thank HackerRank team, especially to [user:wanbo,2015-12-30 ] for testing and great advices and svanidz1 for helping.

If you have any question be free to ask.

The whole HackerRank team wish you good New Year with great success both in private life and numerous programming contests!

See you on Sunday :)

UPD: Score distribution: 20 — 40 — 60 — 80

UPD1: 45 minutes before contest.

UPD2: 15 minutes before the contest. Are you ready to become new HourRank winner, or maybe some previous winner will win this contest? :)

UPD3: Congratulations to winners!

1.xiaowuc1

2.I_love_Tanya_Romanova

3.__math

4.BigBag

5.Sumeet_Varma

I hope you enjoyed in problems! We are glad to hear your comments and suggestions for this and future contest.

Thank you again for participation :)

UPD4: Editorial is published !

Everything best

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

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

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

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

Is it possible to resubmit solution during contests? Are there any penalties for it?

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

    After each submission you know how much points you received ( full testing is during the contest). For each correct testcase you receive some points. You can submit solutions as many times as you want. For each task time is equal with time when you submited the first solution for the maximum points which you had received. Total penalty is equal with maximum of those 4 petalties ( because we have 4 tasks ).

    We have several subtasks ( the main subtasks are mentioned in statements), so if you don't have solution for whole score, you can write some brute force and receive positive score :)

    Also I want to mention one more thing. The tasks will be great challenge for everybody. The first one is very easy, for the last I hope it will be great challenge even for Legendary Grandmasters in one hour :)

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

      Thanks for the explanation!
      Is it correct, that registered for round users automatically appears in scoreboard? So, no submission means the last place?

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

        No, it doesn't mean. For the round were registred around 3500 of coders.

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

          Only at least one submission bring to the leaderboard and affect rating change?

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

            Yes :)

            You are in top 10 ;) Don't worry about it :D

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

              I know :)
              Ask just in case if could not solve anything in the next round :)
              And should I fill some info in my near-empty profile in order to get a T-Shirt? or the address will be asked in a special email or another form?

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

                I really don't know it. Some of HackerRank admins will contact you, I suppose. Also I think you need to put some information at your profile for it.

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

                Please complete your profile, hackerrank team will contact you soon. Congrats.

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

                  Thank!

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

                  and then they'll get to know that he is from Russia:)

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

Is there an editorial? I'd like to know how to solve ToTakeOrNotToTake :)

And is there a way to see others submissions now? It is a great way to learn for me.

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

    First, that problem is HackerEarth problem, and this is contest on HackerRank :) I think each problem on some bigger contest has editorial, I really don't have a lot of experience about HackerEarth contests ( I think for each problem they have setter, tester and editoralist).

    For the HourRank contest you have editorial for each problem, and codes from setter and tester. I am not sure when you can see the codes of other contestants, somethime that option is allowed sometime it isn't :)

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

I am troubling to open problem . I amnot sure anyone have the same issue or not .

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

    The site is bit slow. I have the same problem with Chrome, but please try Mozilia. Also you can reload everything one-two times :)

    UPD: Now is 100% everything fine :)

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

Can someone post a small tricky test for the last problem?

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

    Maybe this: 14 6 6 3 3 3 3 3 3 1 5 1 5 1 5. The answer is 197.

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

      You are the first guy who solved the last task! Congratulation :)

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

      Thanks, it helped to find a bug

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

    6
    1 2 3 6 6 6
    ?

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

Hope you all enjoyed the round. The last problem turned out to be too difficult to solve in one hour even for the big names but I really hope all liked the problems. Please share your opinion, it will help us to improve :).

Update: I just noticed Kostroma solved the last problem after the contest, he is the first person to solve it!

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

    I agree that the last problem is too difficult for that place, particularly it has a couple of corner cases which are not caught in samples. The other problems were good, as they can be good for an 1-hour contest.

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

      Thank you! We really tried to make good contest. I hope to see you again on leaderboard.

      You solved third task with dp, because you lost a lot of time :( Generally I expected guys with three good tasks in 15 minutes, after that I thought that is enough to sovle the last problem for 45 minutes. On many cf rounds that time is enough for D-E div 1 task. Also I mentioned at the start that contest should be great challenge, even for Legendary Grandmasters :)

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

Could you provide a link to editorial? Could not find it from contest's page.

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

    When you click on the some task, you have at the top several topics. The last one is editorial (it is well written).

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

I don't get the explanation for the New Year Chaos.

The answer is number of inversions if for every elements
Inversions of what?

Inversion can be calculated in O(nlogn) too, using BIT
What is BIT? Binary digit?

What happens in the python solution? What is oldp, org? Could someone please explain how this code works?

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

    BIT is binary indexed tree. The python code is just simulation, uncomment the #print org line, and run the code with sample cases.

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

      BIT is binary indexed tree
      Thank you.

      The python code is just simulation
      That doesn't make anything clearer.

      uncomment the #print org line, and run the code with sample cases.
      Ok, I'll research it this way.

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

    If someone has been bribed more than 2 times, terminate the algorithm.
    Why terminate the algorithm? The counter example to that statement:
    23451
    Clearly, 1 has been bribed by four different people and that is valid.

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

      It means that someone bribes two other guys in the queue, not that someone bribes him.

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

        No, has been bribed means that the guy got the money from the people. What you're saying should've been written like this: If someone bribes more than 2 times... :)

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

          Please, don't kill me :D

          I really didn't write it :) If it is mistake, Shafaet will change it. Generally I said you what is the point.

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

          It was a mistake in the editorial, we fixed it now. Thanks for pointing out and sorry.

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

    Inversion of array A is such pair of indexes (i,j) where Ai>Aj. You have different approaches for all the task, so you don't need to think about BIT ;)

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

Can anyone explain why we don't need to keep r0 on dp, we just need r0 % 2, on the 3rd problem?

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

    Because adding or subtracting a number which is divisible by 3 will not impact |Sb — Sk| mod 3. So, selecting such a number can be seen as like changing turns.

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

      Isn't "How many times we can changing turns" important?

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

        Ok, assume there is no number which is divisible by 3, and Player A is winning. Now add even number of such numbers which are divisible by 3 to the same input for which winner was player A. Does it really change the winner? No, because for every turn in which the looser selects a number divisible by 3, the other player will also choose the similar number and negate the effect and turn.

        So the only thing that matters here is whether the number of numbers divisible by 3 are odd or even.

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

    I was looking a lot of codes for this task after contest. There are some other dp approaches for this task, very interesting. For my opinion, this task is was solved by good amount of coders. I didn't expect so big number of correct dp approaches. At least I hope you find something interesting in this task.

    Also I was analysing a lot of things on the contest ( that is my favourite part, when I am setter :D ). Kostroma solved the last task for 45 minutes, so I think that winner of contest and LayCurse had enough time to solve the task :) Yes, the task has several cases which aren't wrriten in samples and it isn't so easy for codinig, but Nikoloz solution had 40 lines of code, so I beleive with great thinking and fast realizing of some things you can solve it for one hour. Personally I expeced 2-3 good solutions on the contest. On the other hand, this is the last task and I think that everybody should prefer one extra hard for contest ( this is extra hard, because contest lasts 1 hour ). This contest, should be graat challenge for everyone ( read this sentences I didn't want to allow Tanya's boyfriend to solve everything in 30 minutes :P ). Also I didn't see easier O(n^3) solutions for 50% of socre. Such solutions could be written in smaller amount of time and yesterday it would be win for that coder ;)

    I hope you had great fun, and you were happy after contest. I know name of next setter, I am sure he will prepare very good and intertesting tasks :)

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

Can somebody explain the solution for problem 4. And also the dp approach that is used to solve problem 3. Thanks in advance :)

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

Problem 2

1

8

1 2 5 3 7 8 6 4

How is this not too chaotic? 4 has jumped 4 times to get to the last spot.

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

    No. You have at the begginng sorted array ( 1,2...,n ), after it you are interested how many at least bribes you perform to gen this array.

    1-step 1 2 3 4 5 6 7 8

    2-step 1 2 3 5 4 6 7 8 (5 bribed 4)

    3-step 1 2 5 3 4 6 7 8 (5 bribed 3)

    4-step 1 2 5 3 6 4 7 8 (6 bribed 4)

    5-step 1 2 5 3 6 7 4 8 (7 bribed 4)

    6-step 1 2 5 3 6 7 8 4 (8 bribed 4)

    7-step 1 2 5 3 7 6 8 4 (7 bribed 6)

    8-step 1 2 5 3 7 8 6 4 (8 bribed 6)

    Answer 7

    4 has been bribed 4 times, but 4 didn't bribe anyone else. Condition of task — some person can not bribe more that two other persons.

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

If you liked the contest or missed the contest (or hated it but want to give us another chance), register for the next round!

→ Reply