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!

How to solve Cyclical Queries using segment tree?

Let's first make some observations:

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 bex — 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 bedistance 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

xand then insert in the queuex+wwherewis 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.

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

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.

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

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

2-3 days.

Still not updated.

So true... Everybody's on vacation?

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.