darkshadows's blog

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

Hi everyone,

I'm excited to invite you to participate in 101 Hack 47. The contest starts at 1500 UTC, March 21. Note the unusual timing!

All problems have been prepared by me. You might have seen some problems and contests set by me on various platforms. This is my third round on HackerRank, after 101 Hack 26 and 101 Hack 40. 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 kevinsogo for testing the problems and his contribution towards fixing problem statements and editorials. It's always a pleasant experience to work with him.

I have tried to create a balanced and interesting problem set. I suggest you read all problems, since there are subtasks and partial scoring. Problems are very much on the easier side compared to previous contests and I bet a lot of full scores(like a lot, seriously!).

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

Update 1: Scoring will be 15 — 30 — 45 — 65 — 80. Update 2: Contest has ended. Congratulations to top 10 for getting full scores. Top 10 are:

  1. I_love_Tanya_Romanova
  2. dreamoon_love_AA
  3. arsijo
  4. KrK
  5. kraskevich
  6. uwi
  7. LHiC
  8. MadNick
  9. HellKitsune
  10. black_horse2014

Update 3: Editorials are up.

  • Vote: I like it
  • +95
  • 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 darkshadows (previous revision, new revision, compare).

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

Bump: Begins in 2 hours!

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

Why it gives me a "Privacy Error" ?

EDIT : Hackerrank opened on firefox and doesn't want to open on chrome.

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

How could you come up with such nice p4 & p5, and such a terrible p3? It is more fit to be in some physics textbook to make schoolers suffer.

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

    Luckily we aren't schoolers with pen&paper and we can write a code to solve a problem :) Applying ternary search allows you to avoid solving any equations and inequalities.

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

    Problem 3 can be cheesed by doing ternary search the point that the opponent should catch the ball.

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

    Just iterate over 10000 points :)

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

      Sadly I first coded this solution, got WA on all tests because I thought ball is moving from p1 to p2, not from p2 to p1, assumed "oh, so tests must be good there" and wrote a ternary search.

      In fact checking 100 points is already enough to get AC :D

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

        Damn, I looked at those submissions of yours and felt so proud! Thank you for bursting my bubble.

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

    Yes, I agree, it wasn't something ingenious. But, I loved how people didn't realize initially that you don't have to compare the time ball takes and the time player takes to reach the hoop.

    You can refer to other approaches in editorial, if you don't like pen/paper approaches. :)

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

      @darkshadows:Is the second approach flawed? How could inequality remain the same on squaring(what if time taken is less than 1)

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

Is stack for "Summing in a Tree" small?

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

    Presumably yes. I've lost 1 hour trying to find a bug in my solution until I wrote an iterative dfs after the contest.

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

    So sad to see this :( And with that binary scoring -_-

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

      I too was getting exactly the same cases passed.Was it because of stack limit?

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

        Yes most likely due to that. I compared output for one of the cases and it matched.

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

    Well I don't think so. I passed from first try with a recursive DFS.

    If you are interested here is the idea:

    My solution was just a couple of binary liftings + a fenwick tree — it is . I think just posting the code will be enough for you to understand it.

    Link: https://ideone.com/D5NDoT

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

    It should be enough for 2 DFS.

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

    I didn't have any trouble with recursive DFS.

    If you are interested, I used Mo algorithm to solve this problem.

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

      How did you solve it using Mo?

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

        First, renumber all the vertices by it's visiting order, and create a new array arr with arri is the level of the vertex with visiting order i. We will notice now that a subtree is actually a continuous segment on arr. So we will have something like "Given n queries, each queries require us to find the number x that there's at least ax elements in segment [l, r] equal to x". This can be solved by Mo algorithm.

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

          Can't this be solved by a simple dfs, with the HLD idea? When we are at node v, we want the information for all nodes in subtree(v) already computed, and then we know the contribution of this node to the final answer. This is O(n2) if implemented naively, but I think it can be made O(n log n) by doing something similar to HLD. Did anyone do this approach?

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

    I did some testing and it seems, it's in hundreds of MBs. Not sure about exact value. I'll ask admins.

    Edit: Admins say it's 32 MB.

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

    Weird thing is happening!
    If I create the adjacency list considering undirected edges i.e
    adj[u].push_back(v);
    adj[v].push_back(u);
    Segmentation fault occurs on above mentioned 3 cases most likely due to Stack overflow. But if i change the adjacency list to directed i.e just
    adj[u].push_back(v);
    The code gets accepted.
    Why does this happen ?

    Code -Segfault
    Code -AC
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I think it's because less parameters in recursion will decrease the usage of stack memory. So your second code needs less memory in stack and still fit in stack memory.

      My code also gets segmentation fault because I used some local variables. And after I change these local variables to global variables then gets accepted.

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

Task were great !

Whether someone has the same problem with understanding texts ? I am not sure that I understand third task correctly even after contest.

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

I was coding p3 in the last minutes, when I am nearly done the page suddenly refresh and wipe out all my work. Nice intercept hackerrank.

→ Reply