×

PPCTS - Editorial

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

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[i] = sumX[i-1] + X[i];
}

// 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))$.

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<int> x(n+1), y(n+1);

for(int i=1; i<=N; i++) {
sc2(x[i], y[i]);
}

sort(x.begin()+1, x.end());
sort(y.begin()+1, y.end());

for(int i=1; i<=N; i++) {
X[i] = x[i] + X[i-1];
Y[i] = y[i] + Y[i-1];
}

int u, v;
u = v = 0;

scanf("%s", s+1);

for(int i=1; i<=M; i++) {

switch( s[i] ) {
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\n", tot);
}
return 0;
}


Time Complexity:

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

Space Complexity:

$O(N)$

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.

This question is marked "community wiki".

1.7k11730
accept rate: 11%

 3 Can be done in O(1) per query `LINK answered 22 Feb '16, 01:05 141●1●5 accept rate: 4% 1 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. (22 Feb '16, 02:29) likecs6★
 0 May be O(Nlog(N)+Mlog(N)) ? answered 22 Feb '16, 01:28 4★pipa 11●1 accept rate: 0% corrected. It should be O(Nlog(M)+Mlog(M)) (23 Feb '16, 10:42)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,186
×832
×790
×637
×81

question asked: 09 Feb '16, 16:29

question was seen: 2,339 times

last updated: 23 Feb '16, 10:42