Yury_Bandarchuk's blog

HackerRank HourRank 14 Invitation
By Yury_Bandarchuk, 8 years ago, In English

Hello, Codeforces!

I want to invite all of you to participate in HourRank 14.

There will be four problems to solve in ONE hour. I am the author of all the problems in this contest and I hope you will enjoy solving them. Also, I would like to say thanks to danilka.pro and Shafaet for helping with contest preparation.

The top 10 will get awesome HackerRank t-shirts.

Editorials will be available at the end as usual.

Good Luck and Have Fun! :)

Score distribution is the following: 25-40-60-80

UPD: Unfortunately, contest will be unrated! :(

I am sorry for everything bad happened during the contest.

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

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

Just to clarify on tiebreaker, if two person has the same score, the one who reached the score first will win.

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

There's some problem with the website. It refreshes every seconds.

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

The editor is refreshing every minute. Not able to submit the code.

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

there seems to be a bug in the UI , in this problem , i submitted a different code about 3 — 4 times but then for some reason all of them are the same code which is identical to my second submission and i was able to submit a proper code only after the contest ended. did anyone else experience this as well?

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

    I had the same problem, the code in UI kept changing to previous code.

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

you should make this round unrated, failed to submit my code in the last 15 minutes. totally disgusting

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

    I couldn't submit only in the last 5 minutes, the code editor was getting refreshed.

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

      my code editor refreshed just from the beginning of the contest, but there was a slight little gap before each refresh. but in the end the code editor started getting refreshed continuously. missed 60 points simply because of this shit.

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

Does C have something to do with meet in the middle? (Yes, it has, I cleared my idea now)

PS: There were also some problems, I couldn't submit in the end because of the frequent refreshing :(

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

    I did dp with bitmasks and got AC.

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

      Bitmask without meet in the middle? What's the complexity?

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

        2d·n·k, where k is the number of operations to or two bitmasks of size 90

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

Is there any alternate approach to the third problem other than meet in the middle?

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

Last 2-3 minutes website did not work properly. I could not copy paste my local code in submit form due to permanent autoreloading page. It was critical, because I was late with better solution on 1 minute. After the contest ended all is working properly.

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

    We made the contest unrated due to this problem. Sorry about that.

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

In the last problem, if you always output "3", you'll get 18.46 score.
I wanted to do it in the last minute, but the web interface didn't allow: it was reloading page just after taking a focus.

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

    And how come you know about it when you haven't submitted one?

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

      I've tried it after contest.

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

        Tried it after contest and you were trying to submit it in the last minute of contest. And still you are getting up votes.

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

          Don't understand, what you are trying to say.
          I've supposed, that if solution will always output answer for the first sample, then non-zero score will be received.
          Tried to do it in the last minute — bad luck, web interface glitches.
          Tried to do it after contest, when the interface became ok again — 18.46 points.
          If you rub your eyes open and open my submittions from the leaderboard, you'll see "Did Not Attempt" for the last problem.
          Have you any other questions?

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

For this case in problem D(True Square in a Binary Matrix):

4
1 0 0 1
0 1 1 0
0 0 0 0
0 0 0 0

We can exchange the top left 1*2 rectangle with top right 1*2 rectangle and get a 2*2 square. But the answer of author's code is 1.

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

    Nice catch! Do you have ideas how to solve the problem including such cases?

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

      No, I cannot solve it for n=300. I feel this problem is quite hard.

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

        Me, when Red coder says it's quite hard

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

    Wow that's tricky. Is the problem solvable then ?

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

    And for such test:

     5
 1 1 1 1 0
 1 1 0 1 0
 1 0 0 1 0
 1 1 1 1 1
 0 0 0 1 1

    It returns 3 instead of 4. Their solution isn't just wrong, it is really dumb.

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

      I feel the answer to your test case should be 3. Can you explain how 4 can be achieved?

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

        Swap rectangle ((1,1),(2,2)) with ((3,3),(4,4)). You will get full 4x4 rectangle ((0,0),(3,3)).

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

how to solve B ??

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

    Editorial is available now

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

      i didn't get the part how the answer is N — number of cycles can u plz explain ??

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

        Let's draw a directed graph, whose vertex set is the set of elements and there's an edge from each B[i] to A[i], for i=1..N, where B is sorted array A. When all elements are distinct, this graph is a collection of disjoint cycles — it's just the cyclic decomposition of permutation of elements. Each swap either splits a cycle into two (when swapped elements are part of the same cycle), or joins two cycles, and so it either increments or decrements number of cycles. Array becomes sorted when there are n cycles, so the lowest bound on number of swaps is n - c, where c is the initial number of cycles.

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

    Make two extra copies of the original array, lets say b[] and c[]. map<int,int> store elements to their index
    sort b in increasing and c in decreasing order Now for array b and a check for minimum swaps by iterating from 0 to n-1 and change the index stored in map when you swap. Do same for c and a. The answer is minimum of both cases.

    Here is my code

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

As contest is unrated now, will medals be still given ?
I was hoping for my first Gold medal :D

→ Reply