CHEFPRD - Editorial

The set of values where the matching can be change will be where c_i + x - d_i = e, i.e. x = e + d_i - c_i. There can be \mathcal{O}(n^2) such values of x. For each x, we can calculate the maximum matching greedily in \mathcal{O}(n) time. Overall time complexity is \mathcal{O}(n^3).

//