Currently I'm writing an article for my school in algorithm. I pick the topic about Manhattan distance, thus I need your help of finding problems in this topic. Any sources (past Codeforcces, ACMs, OIs, SRM, etc.) would be accepted, and I'd appreciate if you could give some hints for some difficult problems.

Thank you for your help!

http://acm.timus.ru/problem.aspx?space=1&num=1726&locale=en

This one you should have probably solved, but anyway:

http://www.spoj.pl/MIT072/problems/DISTANCE/

Here is a similar problem from topcoder Manhattan and its editorial

Any hint to solve this problem , please ..

roypalacios can you please give a hint for the problem above(DISTANCE-spoj)

City Houses

Meeting Point (Interviewstreet) https://www.interviewstreet.com/challenges/dashboard/#problem/4e14b2cc47f78

This is not a problem about Manhattan distance.

I solved that problem by using Manhattan distance. So i think this problem is also about Manhattan distance. Anyway, this might not be a good problem...

http://ioi2007.hsin.hr/tasks/day2/pairs.pdf

I've already used all of those problems in my article. Could anybody suggest more? (maybe past ACM problems can be a good try). Anyway thanks for your help so far.

Well, if you really need an interesting problem on this topic, look at problem 4 from here. If you'll be interested, I'll send you the tests. This problem was given on Petrozavodsk Winter Camp 2012 and nobody has solved it. Moreover, the authors put a wrong solution to the archive, so I'm myself interested how to solve this problem.

This is an excellent problem!

The only solution I can think of requires solving an LP with 2

^{n}variables. The idea is that every embedding can be decomposed into a convex combination of cut metrics.Check SWERC2011 Problem C

Little Adam from z-trening

Any hint to solve this problem? I'm trying to solve it and I get nothing...

just open all the modulo write 8 formulas and we want max among them.So find max of all formulas for each of 8 possibilities.

Sorry for asking again, but how can I get the maximum above the 8 formulas in O(n)?, I think I could do it by fixing a point but... if I do this then how could I know given a point P what's the formula P belongs to?

Problem Restaurant from ACM ICPC Daejeon 2010

Not sure if it is actually relevant to Manhattan distance.

IOI 2012, Day 2: City. Involved Manhattan Distance. I've only solved the 55pt solution, though, so don't know what the 100% involves. Hints can be found here, but I haven't looked at them myself, so can't be sure whether or not they actually help! Best wishes for your article!

http://codeforces.com/problemset/problem/185/E

http://coj.uci.cu/24h/problem.xhtml?abb=1982 and it is in USACO 2011 (BRONZE DIVISION)

Sorry for a bit delaying, as I had a picnic last weekend. Now I'm back :)

Great problems so far! My current favorite is flashmt's problem. It took me a while to find its solution (I'll write the solution soon, in case of interest).

By the way, one of the problems I found recently in Polish OI is a difficult Manhattan problem. I encourage you to try this problem (I haven't solved it, anyway).

Remaining problems: (given by havaliza) http://codeforces.com/problemset/problem/185/E and the problem given by AlexanderBolshakov. Can you two give some hints? :)

I just knew this problem is somehow related to Manhattan Distance. I have no idea how it can be solved! Unfortunately this match has no editorial. You might want to ask one of these coders who have accepted this problem or read their codes. http://codeforces.com/contest/185/status/E

Alright, I'll try to explain my code. Hopefully I won't miss anything important.

The first case is when we don't need to use the subway at all. We can check this separately.

The second case is when some dwarf will use the subway. To solve it, let's find the closest station for each dwarf and then sort dwarves in the decreasing order of this distance. This part is quite standart so I'll skip its explanation.

Now, let's replace our coordinate system with the following substitution: (

x' =x+y,y' =x-y). We'll use it later.Obviously, if some dwarf uses the subway, then all dwarves with smaller distance to the closest subway station will also use the subway. Let's do a binary search over the answer. Now we need to find such K that the first

Kdwarves will walk to the meeting point and the restN-Kdwarves will use the subway and then walk to the meeting point. If such value of K exists, then we need to move the right bound in our binary search, otherwise we need to move the left bound.Suppose we want to check whether the answer is ≤

X. Remember that we replaced the original coordinate system with the new one. In this new coordinate system each dwarf can walk to every point of the square with side 2Xcentered at its original location. It means that if we fix someKand ask the firstKdwarves to walk to some point then this point should lie in the intersection of all described squares for these dwarves. The intersection of several squares is obviously a rectangle. So now for the fixedKwe need to check whether the restN-Kdwarves can reach this rectangle using the subway. Obviously it's enough to check only theK+ 1-th dwarf since all other dwarves will reach the closest subway station at least as fast as theK+ 1-th one. Suppose it takestseconds for theK+ 1-th dwarf to reach the subway station. It means that he will haveX-tseconds to get to our rectangle after getting out of the subway. Thus we can simply extend our rectangle byX-tunits in each direction and check whether there's a subway station inside it.Now we have the following problem: given many rectangles we need to check whether there exists at least one rectangle containing the subway station inside it. This can be solved with a simple scan-line algorithm so I'll skip its explanation as well.

The overall complexity is

O(Nlog^{2}N).Here are 3 related problems: http://www.lightoj.com/volume_showproblem.php?problem=1071 (DP,manhattan distance as state) http://codeforces.com/problemset/problem/213/C (DP keeping manhattan distance as state) http://www.lightoj.com/volume_showproblem.php?problem=1349 (Binary/ternary search on manhattan distance)

10660 Citizen attention offices https://uva.onlinejudge.org/external/106/10660.pdf

This one is quite nice https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/practice-problems/algorithm/big-travel-icpc-9/ I wrote the editorial for this one, which is also available under that url.

The problem is from ICPC Practice Contest

Optimal Point

It took me more than one month to figure out how to solve this problem :)

Grid MST from ICPC SG Preliminary Contest 2015

I didn't notice that this post is 4 years old :(, and the author is a MIT student :).

Problem B, Airports

2015-2016 Petrozavodsk Winter Training Camp, Makoto rng_58 Soejima Сontest 4

MST on points with Manhattan distance.

https://open.kattis.com/problems/gridmst