Problem Link: contest, practice Difficulty: Easy Prerequisites: 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:
It's required to implement an online 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(f_{1}(P1)  f_{1}(P2), f_{2}(P1)  f_{2}(P2), f_{3}(P1)  f_{3}(P2), f_{4}(P1)  f_{4}(P2)), where
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 f_{1}(P), f_{2}(P), f_{3}(P) and f_{4}(P) from S. So, we can maintain S as four separate binary heaps H_{1}, H_{2}, H_{3} and H_{4}, each point of S belongs to each of H_{i}. The points are ordered according to f_{i}(P) in heap H_{i}. Now, if we want to add a new point to S, then we add it to each of H_{i}. 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 f_{1}(P), f_{2}(P), f_{3}(P) and f_{4}(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

Transformation is as follows. Hopefully when shown that way, all steps are clear enough... Just two possibilities for each absolute value ...tried both all possibilities... ...reordered and grouped... f_{1}..f_{4} are defined in editorial above, we can skip f_{x}(P) at the end, because it is the same for all points in S... answered 25 Nov '14, 03:00

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 : answered 24 Nov '14, 01:19
Wow, with
(24 Nov '14, 01:29)
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)
Not surprised since cout is usually more slower than printf.
(24 Nov '14, 01:32)
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)
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)
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 copypaste 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 cinrelated problems.
(25 Nov '14, 08:09)
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 answered 25 Nov '14, 03:38

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. answered 24 Nov '14, 11:08

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. answered 24 Nov '14, 12:01
@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 upperright side of the plane, whereas the f2 function returns the point which is in the most bottomright 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)

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? answered 26 Nov '14, 12:31
It might be I/O problem, if there is one
(26 Nov '14, 21:07)
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)
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
(28 Nov '14, 12:32)
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)

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. answered 28 Nov '14, 18:44

Can someone provide a working link to Setter's/Tester's Solution? answered 16 Dec '16, 13:22
