kaldiuo's blog

By kaldiuo, history, 21 month(s) ago, , It is well known that given points (x, y) and you need to calculate the Manhattan distances between them, instead of using |x1-x2|+|y1-y2| you can first convert all points (x, y) into (x+y, x-y) and the distances will become max(|x1-x2|, |y1-y2|) (also known as Chebyshev distance). Can this trick apply to higher dimensions? Comments (10)
 » Oh, interesting trick. Can you give me a link to a problem that can be solved using this trick?
•  » »
•  » »
•  » » » Oh, thanks! I solved this problem, But it's not about max(|x1-x2|, |y1-y2|)
•  » » » » Actually it is.
•  » » » » » sanya, luchshe sotku verni
 » 21 month(s) ago, # | ← Rev. 2 →   Yes, it can be extended to n number of dimensions as seen in this problem http://www.spoj.com/problems/DISTANCE/.6 Dimensions possible using all possible combinations of + — in place of |x1-x2|+|y1-y2|+...+|h1-h2| My accepted solution: https://ideone.com/obsrth
 » Well, the unit circles in and are both squares (although one of them rotated and shrinked by ) and therefore isomorphic as stated in the question. But, the unit circle in is an octahedron, while the unit circle in is just a regular cube. I don't see an elementary formal proof that this implies that there isn't a bijection with wanted properties in dimensions higher than 2, but intuitively it seems that this is the reason the trick doesn't work in higher dimensions.
•  » » That's a nice way to see it! Maybe someone who deals with topology can help here? There may be some kind of non-trivial isomorphism between the 2 spaces (not exactly the aforementioned manhattan distance one).
 » IOI 2007 pairs. As I can remember, to solve this problem you should consider 4D space. Transform point (x, y, z) to the point (x + y + z, x + y — z, x — y + z, -x + y + z).