ll931110's blog

Looking for problems about Manhattan distance

By ll931110, 12 years ago, In English

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!

  • Vote: I like it
  • +26
  • Vote: I do not like it

Comments Comments (31)
| Write comment?
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This one you should have probably solved, but anyway:

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

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

City Houses

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is not a problem about Manhattan distance.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is an excellent problem!

      The only solution I can think of requires solving an LP with 2n variables. The idea is that every embedding can be decomposed into a convex combination of cut metrics.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Check SWERC2011 Problem C

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Little Adam from z-trening

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        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?

        → Reply
»
12 years ago, # |
← Rev. 5   Vote: I like it +8 Vote: I do not like it

Problem Restaurant from ACM ICPC Daejeon 2010

Not sure if it is actually relevant to Manhattan distance.

→ Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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!

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

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.net/problemset/problem/185/E and the problem given by AlexanderBolshakov. Can you two give some hints? :)

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.net/contest/185/status/E

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      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 K dwarves will walk to the meeting point and the rest N - K dwarves 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 2X centered at its original location. It means that if we fix some K and ask the first K dwarves 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 fixed K we need to check whether the rest N - K dwarves can reach this rectangle using the subway. Obviously it's enough to check only the K + 1-th dwarf since all other dwarves will reach the closest subway station at least as fast as the K + 1-th one. Suppose it takes t seconds for the K + 1-th dwarf to reach the subway station. It means that he will have X - t seconds to get to our rectangle after getting out of the subway. Thus we can simply extend our rectangle by X - t units 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(Nlog2N).

      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Here are 3 related problems: http://www.lightoj.com/volume_showproblem.php?problem=1071 (DP,manhattan distance as state) http://codeforces.net/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)

→ Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Optimal Point

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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 :).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Сan you explain the solution to this problem plz?

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem B, Airports

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

MST on points with Manhattan distance.

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

→ Reply