PPCTS - Editorial



Problem Link:


Author: Pavel Sheftelevich
Tester: Kanstantsin Sokal
Editorialist: Sunny Aggarwal




Sorting, Geometry, Dynamic Programming, Prefix sums, Theory of Distances.

Problem Statement:

Given 2 lists L_1 and L_2 containing of M and N pairs of 2 dimensional coordinates (x, y). For each coordinate in list L_1, calculate the sum of manhattan distances from each point in list L_2 to this point.

Brief Explanation:

For each coordinate in list L_1, calculate its manhattan distance along X axis and Y axis separately from all coordinates in list L_2 and sum them up to get the actual answer.


Manhattan distance d between the 2 coordinates say (x_1, y_1) and (x_2, y_2) is given by following expression.

d = |x_1 - x_2| + |y_1 - y_2|

similary, manhattan distance d of a coordinate (x, y) from N other coordinates (x_1, y_1), (x_2, y_2) ... (x_N, y_N) is given by the following expression

d = |x-x_1| + |y-y_1| + |x-x_2| + |y-y_2| + |x-x_3| + |y-y_3| + ... ... +|x-x_N| + |y-y_N|


d = |x-x_1| + |x-x_2| + |x-x_3| + ... +|x-x_N| + |y-y_1| + |y-y_2| + |y-y_3| + ... +|y-y_N|

It is easy to notice that we can get the actual manhattan distance by calculating the distance along X axis and Y axis separately.

Lets calculate the distance of a point (x, y) from all N points along X axis. Calculating distance along Y axis is identical.

distance along X axis (say d_x) is given by

d_x = |x-x_1| + |x-x_2| + |x-x_3| + ... +|x-x_N|


d_{x} = \sum_{\substack{ x_i <= x}}{x - x_i} + \sum_{\substack{ x_i > x}}{x_i - x}

More formally, for a given x, d_x can be calculated as follows:

d_x = c_1 * x - sum_1 + sum2 - (N - c_1) * x


  • c_1 denotes the count of $x_i$s \le x.

  • sum_1 denotes the sum of $x_i$s \le x.

  • sum_2 denotes the sum of $x_i$s \gt x.

for a given x, c_1, sum_1 and sum_2 can be efficiently computed using binary search over sorted list of $ x_i$s as follows.

int X[N+1]; // given x_i s
long long int sumX[N+1]; // extra array to compute sum1 and sum2 efficiently

sort(X+1, X+1+N); // sort all the x_i s

for(int i=1; i<=N; i++) {
      sumX* = sumX[i-1] + X*;

// now for a given x, calculate d_x as shown below

int id = upper_bound(X+1, X+1+N, x) - (X+1); // id denotes the count c1

long long int sum1 = sumX[id]; // calculating sum1 

long long int sum2 = sumX[n] - sum1; // calculating sum2

long long int dx = c1 * x - sum1 + (n - c1) * sum2; // calculating dx

Note that we need to sort and maintain sum just once and thereafter, every d_x and d_y can be computed in O(log(N)). So overall complexity is O(N\log(N)+M\log(N)).

You can read more about upper_bound function here.

Complete C++ code:

const int maxn = 3 * 1e5 + 10;

long long int X[ maxn ], Y[ maxn ];
char s[ maxn ];

int main() {

	int N, M;
	cin >> N >> M;
	vector x(n+1), y(n+1);

	for(int i=1; i<=N; i++) {
		sc2(x*, y*);
	sort(x.begin()+1, x.end());
	sort(y.begin()+1, y.end());
	for(int i=1; i<=N; i++) {
		X* = x* + X[i-1];
		Y* = y* + Y[i-1];
	int u, v;
	u = v = 0;

	scanf("%s", s+1);
	for(int i=1; i<=M; i++) {

		switch( s* ) {
			case 'L': u --; break;
			case 'R': u ++; break;
			case 'U': v ++; break;
			case 'D': v --; break;

		int cntx, cnty; 

		long long int tot = 0;

		cntx = upper_bound(x.begin()+1, x.end(), u)-x.begin()-1;

		cnty = upper_bound(y.begin()+1, y.end(), v)-y.begin()-1;

		tot += 1LL * cntx * u - X[cntx];

		tot += X[n] - X[cntx] - 1LL * ( n - cntx ) * u;

		tot += 1LL * cnty * v - Y[cnty];

		tot += Y[n] - Y[cnty] - 1LL * ( n - cnty ) * v;

", tot);
	return 0;

Time Complexity:


Space Complexity:


Similiar Problems:



Setter’s solution can be found here
Tester’s solution can be found here

Feel free to post comments if anything is not clear to you.


Can be done in O(1) per query



May be O(Nlog(N)+Mlog(N)) ?


Nice solution but it works only when the coordinates given in the question consist of only integers. The solution in editorial is a more generalised one.


corrected. It should be O(Nlog(M)+Mlog(M))