meooow's blog

By meooow, 5 weeks ago, In English,

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.

f(i) = xi·yi - ai + max1 ≤ j < i{ - xj·yi + f(j)}

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 mj·x + cj. This is identical to the equation of a straight line with slope mj and Y-intercept cj. 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

Read more »

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

By meooow, history, 9 months ago, In English,

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.

alt text

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.

Read more »

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