Problem Link:Author: Pavel Sheftelevich Difficulty:Easy PreRequisites: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 = xx_1 + yy_1 + xx_2 + yy_2 + xx_3 + yy_3 + ... ... +xx_N + yy_N$$ or $$d = xx_1 + xx_2 + xx_3 + ... +xx_N + yy_1 + yy_2 + yy_3 + ... +yy_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 = xx_1 + xx_2 + xx_3 + ... +xx_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,
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[i1] + 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))$. 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<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[i1]; Y[i] = y[i] + Y[i1]; } 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)$ Similiar Problems:Solution:Setter's solution can be found here Feel free to post comments if anything is not clear to you.
This question is marked "community wiki".
asked 09 Feb '16, 16:29

May be O(Nlog(N)+Mlog(N)) ? answered 22 Feb '16, 01:28
