darkshadows's blog

101 Hack 40 — HackerRank
By darkshadows, 8 years ago, In English

Hi everyone,

I'm excited to invite you to participate in 101 Hack 40. The contest starts at 1630 UTC, August 23.

All problems have been prepared by me. You might have seen some problems and contests set by me on various platforms. This is my second round on HackerRank, after 101 Hack 26. Also, here is an old collection of my problems.

There will be five tasks and two hours for you to solve them. Contest will be rated and top-10 contestants on the leaderboard will receive amazing HackerRank T-shirts!

I'd like to thank wanbo for testing the problems and his contribution. It's always a pleasant experience to work with him. Also, I'm thankful to my friends karanaggarwal and Baba for invaluable discussions on few of the problems.

I have tried to create a balanced and interesting problem set. I suggest you read all problems, since there are subtasks and partial scoring. I think problems are a little on the easier side compared to previous contests.

Editorials(written by me) will be published right after the contest.

PS: Announcement format has been shamelessly copied from previous entries by muratt and malcolm. :)

UPD 1: Bump. 12 hours to go!
UPD 2: Scoring will be 20-30-50-80-100.
UPD 3: Contest has ended. Congratulations to top 2 for getting full scores. Top 10 are:

  1. tourist
  2. uwi
  3. kcm1700
  4. Vercingetorix
  5. Nerevar
  6. I_love_Tanya_Romanova
  7. Xellos
  8. FatalEagle
  9. TeaPot
  10. yosupo
  • Vote: I like it
  • +201
  • Vote: I do not like it

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

50 minutes to go! :) After the contest, I am very interested to hear your feedback about the problem set i.e. the difficulty, distribution, type of problems etc.

Also, you can see my solution approaches in the editorial. But it would be great if you can share your approach if it's different. :)

Regarding problem "Sherlock and Dropping Ball", due to a mistake by me, some files which were designed just to increase the height of the tree formed, were given more score than they deserved. Due to which, some people with solutions that weren't completely correct got a good score. I apologize for it. But thankfully, it didn't affect the top 10.

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

Nice round, the third problem is very interesting to me :)

I was increadibly slow, I spent a lot of time for second task ( 30 minutes ?! ). Maybe that task should be a litle harder, but balance between all other problems was great to me.

Also one more thing, I am usually getting some strange compilation errors on HR with C++, I don't know reason for it...

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

Nice and Balanced Problemset :) More importantly the editorials are excellent!! Got to know alternative approaches for same problem

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

Isn't the complexity of 3rd problem that is given before "Better algorithm" wrong? We can find the largest f(i) which is true in . As every element in our open set goes in the open set only once and is deleted only once. Correct me if I'm wrong.

Edit: Why is there a need for binary search? In every call to check if mid is valid or not, everything is reapplied(meaning to get the state of open elements after mid elements of topological sorting are known) again and again. We can do this incrementally too. In worst case it is . Isn't it?

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

    If you want to check f(i), step1: you'll first reach the state Si and step2: you'll find the smallest possible topo-sort from this position and step3: compare with p. Notice that step2 is independent for each i and requires complexity O(m + nlogn).

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

      What I am doing is the following:

      I keep an open set of vertices that can be taken in the topological order next. Initially it will be all elements with inDegree = 0.

      Then I build the given permutation in the problem, that is at ith step, I take the element at ith position of the given permutation which will be present in the current open set.

      Before doing that I check if the largest element in the current set is greater than the element that I will take. If it is greater then this position can be a candidate answer for the maximum f(i) which is true. Is this what you are trying to say? Doesn't this take only . Please clarify :)

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

        You're right. I very subtly overkill my solutions :)

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

          Btw, this could fetch me only 40 points, I have no idea why! Can anyone help me? Code

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

            Use std::set::lower_bound instead of std::lower_bound

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

It was quite easy for me, 7th place with a crippling headache and crashing computer :D. I find the 4th and 5th problem about equally hard, there probably just wasn't enough time for everyone and the 5th is somewhat more implementation-heavy.

In the 4th problem, I used a line sweep by x and defined a segment comparison operator for a segment struct that utilises the current x-coordinate; two segments are compared by finding their y-coordinates at that x and comparing those. This is a valid, unique ordering if no two segments intersect/touch and only segments which actually contain a point at the current x are compared; with non-horizontal and non-vertical segments, the implementation is trivial and the point to which the ball will fall from any (xi, yi) can be found using upper_bound().

In the 5th problem, I deal with y-coordinates in the same way as in segment tree modify/get (with precomputed subtree widths and "edge" lengths); when looking for an answer for a y-covered subtree in the range [x1, x2], it's enough to look at each level of N-s and splitting it into two queries from the root to x1 and to x2 also helps. It's O(H2) per query.

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

I am having some problem understanding the solution of the task 3 "next-topological-sorting". Can anyone explain his solution please ?

→ Reply