Блог пользователя darkshadows

Автор darkshadows, история, 5 месяцев назад, По-английски,

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
  3. arsijo
  4. KrK
  5. kraskevich
  6. uwi
  7. LHiC
  8. m4ddie
  9. HellKitsune
  10. black_horse2014

Update 3: Editorials are up.

 
 
 
 
  • Проголосовать: нравится  
  • +95
  • Проголосовать: не нравится  

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Bump: Begins in 2 hours!

»
5 месяцев назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

Why it gives me a "Privacy Error" ?

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

»
5 месяцев назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

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.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    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.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    Just iterate over 10000 points :)

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is stack for "Summing in a Tree" small?

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It should be enough for 2 DFS.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I didn't have any trouble with recursive DFS.

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

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How did you solve it using Mo?

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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
    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      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.

»
5 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
5 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.