kevinsogo's blog

HackerRank — Week of Code 38
By kevinsogo, history, 7 years ago, In English

Hello, CodeForces Community!

HackerRank's Week of Code 38 is starting today, June 18th 7:00am UTC.

Each day, from Monday to Saturday, we'll unlock a new challenge for you to solve. The contest is rated and the top 10 hackers will win HackerRank T-shirts.

The maximum score for each problem decreases by 10% at the end of every 24 hours. Also, your submissions will run on hidden test cases at the end of every 24 hours.

The contest problems are written and tested by kevinsogo, koca_kodza, ashmelev, saurabh42, VastoLorde95, nonsequitur, shashank21j, zemen, pkacprzak, boleyn.su, niyaznigmatul. (I assume these people use the same CF and HR handles.)

Good luck and happy coding!

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

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

How to solve Cyclical Queries using segment tree?

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

    Let's first make some observations:

    1. the graph has a form of a cycle and every node may have one or more chains which are connected to it
    2. the furthest node to some node u will always be a node from the cycle or a node which is the end of the longest chain connected to some node from the cycle

    So with this observations we can make a segment tree where for each node u from the cycle nodes we will keep the distance from 1 to u + the length of the longest chain starting at u. Now we can easily find the furthest node to a given node u by doing two maximum queries on this segment tree — the first one will be in the interval [u, n] so if the max there is x then the distance to furthest node will be x — distance from 1 to u. The other query will be in the interval [1, u — 1] and if the maximum there is y then the distance to the furthest node will be distance from u to 1 + x. So you choose the maximum between these two values and voilà there it is the furthest node. You can keep not only the distances in the segment tree but also the node indices so that you find the node itself not only the distance to it.

    Now the other question is how to keep the longest chains for each node and also be able to make insert and delete queries to this chains. As we said we will only delete ending nodes in this chains and also we will only insert at the end of some chain. So we can maintain a priority queue for each node from the cycle and when we have an insert query we just take the top of the queue x and then insert in the queue x+w where w is the weight of the new edge. When we have a delete query we just need to remove the top of the queue.

    The complexity is .

    Here is my code. Hope it was helpful. If you have some questions feel free to ask.

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

      Thank you so much JustInCase ! Above explanation is crystal clear to me. :)

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

      I am doing exactly the same to what you have described, yet I am getting TLE in this code. Can you see why this is failing despite having Q*(logN)^2 complexity.

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

Very happy there was a flow problem. First time actually seeing one in a non-virtual contest. Thanks ashmelev!

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

How much time it generally takes for rating update on HackerRank?

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

    2-3 days.

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

      Still not updated.

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

        So true... Everybody's on vacation?

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

          Nope, they are just updating ratings manually for every individual person and now their calculator is broken. This seems to be the only logical reason.

          → Reply