Hello, Codeforces!

This is a blog on the $$$k$$$ shortest paths problem, and a neat algorithm by David Eppstein that can solve it very fast. You can find the original paper "Finding the $$$k$$$ Shortest Paths" here.

Given an edge-weighted directed graph $$$G$$$, the problem asks us to find the lengths of the $$$k$$$ shortest paths from a fixed vertex $$$s$$$ to a fixed vertex $$$t$$$.

This a very specific problem, and unlikely to show up in any programming contest. However, the ideas used to solve this may be useful in solving other problems.

Getting started

Prerequisites:

• Dijkstra's algorithm
• Persistent heaps

The most widely asked for Codeforces feature has arrived!
Yes, you can now play Bad Apple on your profile's activity graph.

This is just something I thought would be fun to make, seeing the countless other canvasses people have managed to play Bad Apple on.
The code is available on Github here.
I don't expect it to be robust, but it works and I'll try to make some improvements later.

Hello Codeforces community,

I would like to invite you all to Coders' Legacy 2019, the contest held annually by KeyGEnCoders, the programming club and CodeChef Campus Chapter of Kalyani Government Engineering College. This contest will be held on CodeChef and will be rated for both divisions.

The contest starts on 26 February at 21:30 IST. You will have 2.5 hours to solve 6 problems. The ranklist will be ACM style with the penalty set to 10 minutes.

The problems have been prepared and tested by sarthakmanna, avijit_agarwal, and myself. I would also like to thank arjunarul and vijju123 for providing feedback about the problems.

There are laddus for top performers. Please check the contest page for details.

Good luck to all and wish you high rating :)

UPD: The contest begins in 30 mins.

UPD 2: Hope you enjoyed the problems. Any feedback is welcome. The editorials are uploaded and can be found here.

UPD 3: Congratulations to the winners!

You can find the full ranklist here.

The problem

Let us consider the problem where we need to quickly calculate the following over some set S of j for some value x.

Additionally, insertion of new j into S must also be efficient.
This will most likely be encountered with DP problems. For example, the recent problem 1083E - The Fair Nut and Rectangles from Round #526 has the following DP formulation after sorting the rectangles by x.

The problem requires quick calculation of the above define maximum for each index i. How can this be done?

The idea

Notice the special form of m_j·x + c_j. This is identical to the equation of a straight line with slope m_j and Y-intercept c_j. So the problem is equivalent to being given a set of lines and asked for the maximum y value any of those lines can give at a particular x. If you draw a bunch of straight lines on a plane, you'll notice that the maximum values are along what appears to be a convex hull.

Some observations:

• Every line on the hull provides the maximum value on some contiguous range of x values. Conversely, every line not on the hull is useless and never provides the maximum.
• All the lines on the hull have different slopes. The order of slopes also determines their position on the hull. A line with lower slope appears on the hull to the left of one with a higher slope.

So, a possible strategy can be to only maintain the convex hull and not keep the useless lines

Hello Codeforces community,

On behalf of KeyGEnCoders, the programming club and CodeChef Campus Chapter of Kalyani Government Engineeing College, I would like to invite you all to Coders' Legacy 2018. The contest will be hosted on CodeChef and will be rated for both divisions.

The contest will start on Sunday 15 April at 21:30 IST and the duration will be of 3 hours. It will have an ACM style ranklist with the penalty set to 10 minutes. There will be 6 problems of varying difficulty.

The problem setting team includes avijit_agarwal, sarthakmanna, mayukh45, and myself. I would also like to thank arjunarul from CodeChef for helping out with the problems.

Top 5 Indian and top 5 non-Indian winners will receive 300 CodeChef laddus each.

Good luck to all and wish you high rating :)

UPDATE: The contest starts in 30 mins.

UPDATE 2: The contest has ended. Check out final standings and editorials. Hope everyone enjoyed the problems! The cakewalk problem turned out a little harder than we expected, we apologize for that :/ Thank you for your participation.