PPCTS - Editorial

cook67
editorial
geometry
implementation
maths
sorting

#1

Problem Link:

Practice
Contest

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

Difficulty:

Easy

Pre-Requisites:

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.

Explanation:

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|

or

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|

or

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

where,

  • 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;

		printf("%lld
", tot);
	}	
	return 0;
}

Time Complexity:

O(Nlog(M)+Mlog(M))

Space Complexity:

O(N)

Similiar Problems:

DEVPERF
MOSTDIST

Solution:

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.


#2

Can be done in O(1) per query

`LINK


#3

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


#4

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.


#5

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