You are not logged in. Please login at www.codechef.com to post your questions!

×

PPCTS - Editorial

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

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[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)$

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.

This question is marked "community wiki".

asked 09 Feb '16, 16:29

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

edited 23 Feb '16, 10:40


Can be done in O(1) per query

`LINK

link

answered 22 Feb '16, 01:05

ayushtomar's gravatar image

5★ayushtomar
14115
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★

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

link

answered 22 Feb '16, 01:28

pipa's gravatar image

4★pipa
111
accept rate: 0%

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

(23 Feb '16, 10:42) ma5termind3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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