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

×

MOSTDIST - Editorial

Problem Link: contest, practice

Difficulty: Easy

Pre-requisites: Binary heap, Geometry, Manhattan distance

Problem:

Let's consider a set of points S. Your task is to implement a data structure that can process the following queries efficiently:

  1. "+ X Y" - add a new point P with coordinates (X, Y) to S;
  2. "- N" - remove the point that was added during the N'th adding query from S;
  3. "? X Y" - calculate the maximal Manhattan distance between a point P with coordinates (X, Y) and any point from S.

It's required to implement an on-line solution, i.e. which processes queries in the order of their appearance.

Explanation:

Let's transform the formula of Manhattan distance a little bit:

dist(P1, P2) = |X1 - X2| + |Y1 - Y2| = max(X1 - X2, X2 - X1) + max(Y1 - Y2, Y2 - Y1) = max((X1 + Y1) - (X2 + Y2), (X1 - Y1) - (X2 - Y2), (-X1 + Y1) - (-X2 + Y2), (-X1 - Y1) - (-X2 - Y2)) = max(f1(P1) - f1(P2), f2(P1) - f2(P2), f3(P1) - f3(P2), f4(P1) - f4(P2)), where

  • f1(P) = X + Y;
  • f2(P) = X - Y;
  • f3(P) = -X + Y;
  • f4(P) = -X - Y.

In other words, dist(P1, P2) equals to the maximum of four values, that don't contain abs() function anymore.

It's time to make the key observation of this problem:

Let's suppose that we are to find the maximal Manhattan distance between a point P and any point from S. The key fact is that there are only four candidates to be the most distant one: the ones with the maximal f1(P), f2(P), f3(P) and f4(P) from S.

So, we can maintain S as four separate binary heaps H1, H2, H3 and H4, each point of S belongs to each of Hi. The points are ordered according to fi(P) in heap Hi.

Now, if we want to add a new point to S, then we add it to each of Hi. If we want to calculate the maximal Manhattan distance between a point P and any point from S, then we find the most distant point from S(as the most distant one among ones with the maximal f1(P), f2(P), f3(P) and f4(P)).

What about removing points from S? As we know, a binary heap doesn't provide any kind of removing except removing from the top of the heap. But that's OK, we won't remove them for real until they affect the answers. We can just mark removed points somehow and every time, when a 'removed' point is on the top of one of the binary heaps, we remove it from this heap for real. The reason why we are not removing a point from S until it is not on the top is that such a point doesn't affect the answers, since only the ones on the tops are considered as candidite for being the most distant point every time we are interested to know that information.

The total complexity of the solution is O(Q log Q).

Please, check out Setter's and Tester's solutions for your better understanding.

Setter's Solution: link

Tester's Solution: link

This question is marked "community wiki".

asked 24 Nov '14, 00:05

kostya_by's gravatar image

6★kostya_by ♦♦
166143235
accept rate: 0%

edited 29 Jul '15, 20:54

admin's gravatar image

0★admin ♦♦
15.9k347484508


Transformation is as follows.

Hopefully when shown that way, all steps are clear enough...

Just two possibilities for each absolute value

alt text

...tried both all possibilities...

alt text

...reordered and grouped...

alt text

f1..f4 are defined in editorial above, we can skip fx(P) at the end, because it is the same for all points in S...

link

answered 25 Nov '14, 03:00

betlista's gravatar image

3★betlista ♦♦
16.8k49115224
accept rate: 11%

1

@betlista thanks

(25 Nov '14, 15:08) ashwini007k4★

Codechef should try and fix their Time limits.

My first solution printing answers using cout: http://www.codechef.com/viewplaintext/5453096

Second solution printing answers using printf: http://www.codechef.com/viewplaintext/5453133

First one TLE and second one passed :|

link

answered 24 Nov '14, 01:19

pranavr93's gravatar image

4★pranavr93
570338
accept rate: 11%

Wow, with sync_with_stdio(0)... Noticed, thanks

(24 Nov '14, 01:29) betlista ♦♦3★
2

I don't think it's about cout, but endl. When you use endl instead of "\n", it flushes the output, which is incredibly slow. (Also, sometimes the output is flushed when reading with cin, so you should put cin.tie(0) at the beginning of your code to avoid it in situations such as this one.)

(24 Nov '14, 01:29) xellos07★

Not surprised since cout is usually more slower than printf.

(24 Nov '14, 01:32) flaminrage4★

yea, maybe its because of endl..! cin, cout with sync_with_stdio(0) works faster than scanf printf. Endl seems to be the only issue here.

(24 Nov '14, 12:10) pranjalranjan4★

Point noted. Though cin.tie(0) still doesn't solve the issue. Either way ,should try and avoid endl on codechef. One point which I would like to raise would be that online judges like codeforces never have such problems. In codechef, even if you get the complexities right, there is a possibility of getting a TLE. Why involve border line time limits in the first place? I guess reducing the time limit a bit wouldn't hurt or let higher complexity solutions pass.

(25 Nov '14, 02:49) pranavr934★

Yeah well, if you only use cin.tie(0) but don't replace endl by "\n", it will have no effect - that's why I listed the steps to take in order of priority. Just copy-paste the first 2 lines from my main() and don't use endl (except for debugging), and you'll be fine from the vast majority of cin-related problems.

(25 Nov '14, 08:09) xellos07★
showing 5 of 6 show all

Actually, max for F2 is min for F3. And max for F1 is min for F4... But my solution doesn't pass. Weird NZEC...Grmph

link

answered 25 Nov '14, 03:38

beroul's gravatar image

6★beroul
1113
accept rate: 6%

The candidates for distant point are from the maximum of each of the functions. It will be true if we find the minimum too right? Just for a better understanding. Or can someone explain how it is the maximum? I assumed from the formula written for 2 points as f1(P1) - f1(P2) ... , we take P2 to be the point given and P1 the points on the set.

EDIT: I used the minimum instead of maximum and it accepted. Hence i could just use a map and do deletions easily too.

link

answered 24 Nov '14, 11:08

prashantmahesh's gravatar image

5★prashantmahesh
5612
accept rate: 25%

edited 24 Nov '14, 11:44

can you explain how you have made the transformation and its validity? I can't seem to understand it and it's bugging me a lot.

link

answered 24 Nov '14, 12:01

ashwini007k's gravatar image

4★ashwini007k
78791528
accept rate: 6%

@ashwini007k, another way of seeing all of this, which made the understanding easier for me, is that you can consider each fi function as maintaining the most distant point of a particular quadrant from the center. Although all of the points coordinates are positive, and then are in the same quadrant, the f1 function returns the point which is in the most upper-right side of the plane, whereas the f2 function returns the point which is in the most bottom-right side of the plane, and so on. From that you could assume that the most distant point from P is some point which is in one of the four corners of the plane.

(26 Nov '14, 23:07) cristhianr3★

There are no accepted solution to this problem in python. I implemented the log(Q) per query approach, but it still gives TLE error. Can you check if the problems time constraints are too strict for python?

link

answered 26 Nov '14, 12:31

gauravsc's gravatar image

2★gauravsc
1
accept rate: 0%

It might be I/O problem, if there is one + 0 0 and 500,000 times ? 1000000000 1000000000 (109 both) how quick you got response on your local PC?

(26 Nov '14, 21:07) betlista ♦♦3★

I take each query using raw_input() command and give the input as you asked above. It takes 38.27s for the code to finish. I also try by reading the entire input in one attempt using sys.readlines(), but it takes even longer 86.6s. I now think that the bitwise xor operator is the only cause of delay in the output.

Here is my code http://www.codechef.com/viewsolution/5458355

(28 Nov '14, 12:16) gauravsc2★

almost 40 seconds is too slow, I don't think it is because of xor, it's slow I/O I'm afraid...

Other python guys, are there quicker I/O methods?

One more thing you can try, what I'm doing in Java... Instead of print answer for each query, use string concatenation and print this huge string once at the end...

(28 Nov '14, 12:32) betlista ♦♦3★

Something interesting, I mask the output of each xor with 0xFFFFFFFF & (query ^ answer) and because of this the time reduces to 4.3s on my PC, but it still says TLE on codechef.

(28 Nov '14, 13:26) gauravsc2★

This problem definitely has too strict time constraints for python. I think the time constraint of 3*1.5=4.5s for python is a little off the mark. It is near impossible for me to bring the time below 5.5s. I think the time limit for python should be at least 6.5s. Please reset the time limit for python or else a lot of other people would end up being frustrated.

link

answered 28 Nov '14, 18:44

gauravsc's gravatar image

2★gauravsc
1
accept rate: 0%

Can someone provide a working link to Setter's/Tester's Solution?

link

answered 16 Dec '16, 13:22

adityavk's gravatar image

3★adityavk
1
accept rate: 0%

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:

×11,590
×2,610
×365
×113
×51
×25

question asked: 24 Nov '14, 00:05

question was seen: 3,762 times

last updated: 16 Dec '16, 13:22