# Competition - Qualifications - E - Matrix distance

2 types of query:

1. add value to x y
2. output the sum of $value*(|a - x|+|b-y|)$ for every pair(a, b, v).

In the start you are given $n$ (number of querys), $m$ (maximal dimension for square matrix).

In the next $n$ lines you are given either:

1. 1 x y v, you should add value v to x y coordinate, or
2. 2 x y calculate the $distance * value$ between every $a$ and $b$ that have some values (distance is being calculated: $|a- x| + |b - y|$). So the formula for one spot in matrix would be $v * (|a - x| + |b - y|)$ for a given $a$ and $b$.

My code works, but it is too slow.

Constraints:
$n <= 250'000$
$m <= 10^9$
$X_i$ and $Y_i <= m$
$V_i$ <= $10^4$

time limit: 2.5s

My code:

for (int i = 0; i < n; ++i){

int el;
cin >> el;

if (el == 1){
int a, b, c;
cin >> a >> b >> c;

x.push_back(a);
y.push_back(b);
v.push_back(c);
}

if (el == 2){
int a, b;
cin >> a >> b;

ll sol = 0;
for (int j = 0; j < x.size(); ++j){
sol += v[j] * (abs(a - x[j]) + abs(b - y[j]));
}
cout << sol << "\n";

}

}


Your explanation is difficult to follow, but your code explains it. It's simple and clear.

The main thing I want to advise is to not use using namespace std. See this Stack Overflow question for reasons.

You don't show what ll is, I presume it's a long long int type?

For a newline, use '\n' rather than "\n". There's not a huge difference, but it's slightly faster to output a single character than a string containing a single character.

In terms of improving performance, you might want to keep a single vector with a struct:

struct Data {
int x, y, v;
}
std::vector<Data> data;
// ...
data.emplace_back(a, b, c);


This gives you at least two advantages:

1. You call malloc/realloc (on push_back) three times as frequently if you have three vectors. If you have only one vector on the stack, there is a good possibility that realloc will simply add space to the end of your block, rather than creating a new block and copying the data over. If you have three vectors, trying to expand one will invariably have another be in the way, forcing the copy.

Of course you could do data.reserve(n) and be sure you'll never call realloc.

2. Data locality: In your second case, where you iterate over the data, you would read the three values from consecutive locations in memory, rather than from disjoint locations. This will allow a better use of cache. Since you iterate over these frequently, it could make a big difference.

Finally, you can improve your distance computation and do away with one of the calls to std::abs. Note that, for the L-1 norm that you use, distance(p1,p2) == abs(distance(0,p1)-distance(0,p2)). And, given your text "m (maximal dimension for square matrix)", I presume that the coordinates indicate a location within this matrix, and therefore are always larger or equal to 0. If so, computing the distance to the origin requires no std::abs. then your distance

abs(a - x[j]) + abs(b - y[j]) // distance(p1,p2)


can be rewritten as

abs(a + b - (x[j] + y[j])) // abs(distance(0,p1)-distance(0,p2))


The thing that still bothers me is that you are given m, but you don't need it. Maybe we're missing another possibility for optimization there?

# (EDIT) Reducing complexity from O(n²) to O(n log n)

It is possible to reduce the complexity of step 2 by adding some (a lot of) complexity to step 1. Both steps (adding a point and computing the weighted distance of a point to all previous points) should turn into operations of logarithmic complexity w.r.t. the number of points seen so far.

sum( v[j] * ( abs(a - x[j]) + abs(b - y[j]) ) )


can we rewritten as

sum(v[j] * abs(a - x[j])) + sum(v[j] * abs(b - y[j]))


That is, the two dimensions can be tackled independently. From here on we'll look only at the x-coordinate, and presume we repeat the same operations for the y-coordinate.

Next, we note that we can write

sum(v[j] * abs(a - x[j])) == sum(v[j] * (a - x[j])) // for x[j]<=a
== sum(v[j] * (x[j]) - a) // for x[j]>=a


Thus, we need to separate incoming points in step 1 into those that are to the left of a future query point, and those to the right. (Note that if x[j]==a, the distance will be 0, and the point can be ignored or used twice without affecting the output.

So how do we separate incoming points around a coordinate we don't know yet? Use a tree. R-trees are the tool for spatial indexing like this. We need a simplified version, since we don't need to store bounding boxes, only split locations. Maybe it's more similar to a quadree.

Because

sum(v[j] * (a - x[j])) == sum(v[j])*a - sum(v[j]*x[j])


it seems that we need to accumulate sum(v) and sum(v*x) for all points to the left of x (and also for those to the right). Thus our tree needs to store these values. The tree further needs to indicate what the coordinate is that splits its left and right branches. Thus, we can easily find in the tree the nodes that are to the left or to the right when computing a distance in step 2.

I think the tree should have each input point as a leaf node. Each non-leaf node (can I call those branch nodes?) would contain the sum of v and v*x for its two children, as well as the x-coordinate half-way between the two children's x-coordinates. Something like this:

struct Node {
Node* left;
Node* right;
std::uint64 sumV;
std::uint64 sumXV;
std::uint32 x;
}


During step 1, it's simply a matter of inserting nodes:

void Node::insert(std::uint32 x, std::uint32 v) {
if (isLeaf()) {
// turn this leaf node into a branch node
// create a new leaf node with {sumV,sumXV,x}
// create a new leaf node with {v,x*v,x}
sumV = left->sumV + right->sumV;
sumXV = left->sumXV + right->sumXV;
x = (left->x + right->x) / 2;
}
if (x <= node->x) {
left->insert(x,v);
} else {
right->insert(x,v);
}
}


During step 2, find the position of a in the tree, and obtain sumV and sumXV for all nodes to the left, and all those to the right:

std::uint64 Node::sum(std::uint32 a) {
if (isLeaf()) {
return std::abs(sumV*a - sumVX);
}
if (a>=x) {
return left->sumV*a - left->sumXV + right->sum(a);
} else {
return right->sumXV - right->sumV*a + left->sum(a);
}
}


I don't have time to write a full implementation and test it, but it was to think about this problem!

• Can something be done with the abs? The main problem in this code because its complexity is O(n^2) and that is too slow. Can in less time the distance beetwen every coordinates be calculated with some prefix sum, or some tree structure, or maybe graphs? – Justin Somper Jan 21 '18 at 7:09
• Sorry for spaming. Can I make this matrix in to array? Since the distance is being calculated abs(a + b - x[j] - y[j]), I can do this: 1) if the query 1 appears - I put in a vector a pair {x + y, v} 2) if the query 2 appears - I can maybe with some prefix sums to calculate – Justin Somper Jan 21 '18 at 7:14
• @JustinSomper : Yes, you're right, I wasn't thinking about this earlier. You have a fairly small range for V. You can factor out the sum over v*(a+b) for each possible value of v. In step 2 you then loop over v rather than each point given. Not sure how the one last abs will play into that, though. Maybe this is where the m comes into play? – Cris Luengo Jan 21 '18 at 15:09
• @JustinSomper, I think I figured it out. There's a concept of R-trees for spatial indexing. This can make computation much faster by taking together groups of points. But since we're using the L-1 norm, it's even simpler: build two binary trees, one for x-coordinates and one for y-coordinates. In step 1 you add points to the trees, incrementing parent nodes with the weight of the point and keeping a center of gravity. (Continued) – Cris Luengo Jan 21 '18 at 17:03
• (Continued) In step 2 you find the nodes to le left and to the right of your input point. Using the tree you can summarize their weight and distance, reducing the computation to an operation of order log(n) rather than order n. The x and y distances are computed independently. – Cris Luengo Jan 21 '18 at 17:05