# need solution to this problem in c#- help RSS

## 17 replies

Last post Mar 09, 2012 02:12 PM by gerrylowry

Member

173 Points

123 Posts

### need solution to this problem in c#- help

hi all,

i came accross thisproblem from one web page, i have tried my best to resolve. i couldn't. i think i am lacking in the logic. can any one solve and tell me the logic with source code..

Problem is:

<div>Meeting Point (50 Points)</div> <div> </div>

There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting place, which is someone's house.
From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
eg: (x,y) can be reached from (x-1,y+1) in a single unit of time.
Find a common meeting place which minimises the sum of the travel times of all the persons.

Input Format:
N
The following N lines will contain two integers saying the x & y coordinate of the i-th person.

Output Format:
M M = min sum of all travel times;

Constraints:
N <= 10^5
The absolute value of each co-ordinate in the input will be atmost 109

HINT: Please use long long 64-bit integers;

```Input #00:
4
0 1
2 5
3 1
4 0

Output #00:
8

Explanation: Sums of travel times of the houses are 11, 13, 8 and 10. 8 is the minimum.
```
`Input #01:`
```6
12 -14
-3 3
-14 7
-14 -3
2 -12
-1 -6```
`Output #01:`
`54`
Ashokkumar

Contributor

4394 Points

1102 Posts

### Re: need solution to this problem in c#- help

It's basic math and basic looping.

It would be easier to understand if you drew a grid on a blank peice of paper with a pencil.

For the sake of comprehension, pretend the centermost cell is the closest to all random persons. Now randomly pick other cells and count  how many cells they're away from the center cell. Once you understand that, write the code for it.

All-Star

20577 Points

5721 Posts

### Re: need solution to this problem in c#- help

is this a homework assignment:

#### ashok2009cse

can any one solve and tell me the logic with source code

probably mathematicians who specialize in graph theory could mentor you; you might have to write the code yourself

#### ashok2009cse

There is an infinite integer grid

it's unsolvable if it's infinite.

#### ashok2009cse

From any given cell, all 8 adjacent cells are reachable in 1 unit of time.

no, edge cells can reach fewer houses ... look at a chess board

N.B.:  let's use a chess board, home position, as an example,

rowas are 1 to 8; columns are a to h

let's say that both White bishops (c1 and f1) wish to meet with their count parts (c8 and f8) at d4

if your cells are squares of the same size, like the chessboard, then your problem is simple ...

however, since you do not know where the meeting will take place, in pseudo code, your logic would be something like this ...

(a) create an arrary (Int32, Int32) of n by m where n is the total number of cells (64), m are the number of participants

[0, 0] would be the distance for the c1 bishop to a1 (2);
[0, 1] would be the distance for the f1 bishop to a1 (5);
et cetera

b) you'd also need to store your path ... for c1 to a1, the path is c1==>b1==> a1

(c) NOTE:  a1 is the White Queen Rook's house ... you said someone's house so according to your problem definition, that someone might not be one of the people who wish to meet.

(d) your problem is simpler if the someone's house must be a home of one of the meeting participants ... for this restricted case, the distance for one participant will always be zero.  so you basically would compute the routes from everybody to everybody else ...

note:  in the case of the four bishops, any house will do because of the symmetry of their positions on the chessboard.

g.

All-Star

20577 Points

5721 Posts

### Re: need solution to this problem in c#- help

graph theory shortest path algorithm

All-Star

15943 Points

2353 Posts

### Re: need solution to this problem in c#- help

#### gerrylowry

it's unsolvable if it's infinite.

Not true. It's only unsolvable if N is infinite.

#### gerrylowry

no, edge cells can reach fewer houses ... look at a chess board

Again, not true. Because the grid is infinite, there are no edges. The chessboard doesn't help here at all.

For the OP, the exam questioner (or homework assigner, if you like) has made life easier for you, as you can trivially calculate the distance between any two homes as the larger of dX and dY (where dX is the difference in the X coordinates, and dY is the difference in the Y coordinates) due to the fact that the cost of moving diagonally is (artificially) the same as moving horizontally or vertically.

To calculate which is the optimal, simply

Set a variable (call it average distance) to 0.

Loop through all N participants.

For each, calculate the average (Mean, Median or Mode is up to you to think about) distance to all the other houses. If it's less than the variable above, remember it (and remember which house you're currently processing)

Now this is a brute force approach (if you like), so it is clearly inefficient as N tends to large numbers. But it doesn't require you to hold more than one house identifier and two distances in memory at any time, so it's very memory efficient. Unfortunately, gerrylowry's approach cannot work due to the infinite nature of  the grid.

Regards

Dave

All-Star

20577 Points

5721 Posts

### Re: need solution to this problem in c#- help

@ DMW

#### DMW

gerrylowry "it's unsolvable if it's infinite."

Not true. It's only unsolvable if N is infinite.

the problem statement appears defective ...

the infinite grid may be a red herring.

The constraints are interesting.

N people constrained by N <= 10000 gives N == 0 | 1 | 2 | 3 | ... | 9998 | 9999 | 10000 since we can not have < 0 people.

N == 0 has no solution.

if we only meet at the home of a participant, N == 1 would meet in her/his own home, a distance of zero.a

OTOH, if the meeting home can be any home, given a infinity grid there is no solution ...

from cell c to cell c' is one unit,
from cell c to cell c'' is 2 units,
from cell c to cell c'" is 3 units,
from cell c to cell c'''' is 4 units,
from cell c to cell c''''' is 5 units,
from cell c to cell c'''''' is 6 units, ...

there will always be one cell further away from the previous cell in each of eight directions ...

... no solution     Q.E.D.

However, the O.P. stated a second constraint, no co-ordinate's absolute value > 10^9 ... imho, this is a bit of a silly constraint because the problem does not state the co-ordinate system to be used ... so let's invent one of our own:

x is the center of our Flatland-ish universe ...

```<=== oooo.ooooouooooo.oooo ===>
<=== ooooo.oooouoooo.ooooo ===>
<=== oooooo.ooouooo.oooooo ===>
<=== ooooooo.oouoo.ooooooo ===>
<=== oooooooo.ouo.oooooooo ===>
<=== ooooooooo.u.ooooooooo ===>
<=== llllllllllxrrrrrrrrrr ===>
<=== ooooooooo.d.ooooooooo ===>
<=== oooooooo.odo.oooooooo ===>
<=== ooooooo.oodoo.ooooooo ===>
<=== oooooo.ooodooo.oooooo ===>
<=== ooooo.oooodoooo.ooooo ===>
<=== oooo.ooooodooooo.oooo ===>```

from x we can move only in 8 directions (assuming our cells are uniform squares) ...

our directions are up, down, left, right, diagonally up left, diagonally up right, diagonally down left, and diagonally down right

this means that we can not always move in a straight line

so, our co-ordinate system much be a direction and a value

if x is at 0, 0, then we could have someone (harry) at 999 999 999 up

if x is at 0, 0, then we could have someone (mary) at 999 999 999 down

now, we have a problem ... (harry) and (mary) each meet the distance constraint (10^9) with x, but fail it with each other.

for simplicity, let's pretend that we have an edge corner, like a1 on the chessboard, and called it 0, 0 ... we can also have 0, 999 999 999 right and 0, 999 999 999 up ... the n,n diagonal would take us from 0, 0 to 999 999 999 diagonally up right, .... because we are measuring distance by cell count, 0, 0 to 999 999 999 up, 0, 0 to 999 999 999 diagonally up right, and 0, 0 to 999 999 999 right ALL seem to be the same distance, however, the diagonal (hypoteneuse) distance is larger (Pythagorous).

(again, keeping it less complex, every house would have to be in the centre of it's cell and every house would have to be the same size ... even that's a problem because the houses would have a front door, back door, and meybe one, even two side doors, but not likely also corner doors for people approaching diagonally).

back to the chessboard for a moment:  let''s move the white queen from d1 to a3;

d1, c1, b1, a1, a2, a3 == 5 cells away

d1, c2, b2, a3 == 3cells away

d1, c1, b1, a2, a3 == 4 cells away

of course, if we gave the queen a helicopter, she could fly directly to a3 but we'd have to add in the take off and landing distances because the queen's helicopter would not want to crash into other chess pieces on its way to a3.

i am not a mathemation .... however, it's reasonable to make some assumptions ...

(a) we will have 2 to 9999 houses distributed pseudo randomly in a 999 999 999 x 999 999 999 grid;

(b) we will not visit houses of strangers so we will ignore the houses on non-meeting participants

(c) our 999 999 999 x 999 999 999 grid is one of infinite 999 999 999 x 999 999 999 grids on our infinite super grid

(d) our problem is only solvable within the boundaries of any one or more 999 999 999 x 999 999 999 grids but if and only if we restrict the total number of grids to a finite number.

(e) the house(s) nearest the centre of the grid will not always be the ideal destination (back to the chessboard,  the black queen, if on d5 would have to travel towareds a1 if the other meeting participants were on a1, b1, and c2) ... occassionally, a home in the largest cluster of homes may turn out to be the best soulution.

(f) often, there will be multiple best solutions ... example, 4 participants, one each, at (0,0), (9,0), (0,9), and  (9,9).

All-Star

20577 Points

5721 Posts

### Re: need solution to this problem in c#- help

@ DMW continuing my reply to you ...

#### DMW

Because the grid is infinite, there are no edges

(i) if the grid is infinite, there is no solution

(ii) f the grid is finite, there are edges

(iii) unlike folding our universe*, our grid is and will remain Flatland-ish for this problem

example:  http://astronomy.nmsu.edu/geas/lectures/lecture28/slide02.html
"Does the Universe have an Edge?"

i am not a methematician ... so  DMW, either there are no edges in our infinite grid or there are infinite edges ...

likely you are correct when you state "Because the grid is infinite, there are no edges".

g.

All-Star

15943 Points

2353 Posts

### Re: need solution to this problem in c#- help

#### gerrylowry

the problem statement appears defective ...

the infinite grid may be a red herring.

gerry

Have you actually read the problem definition. It is really clear and really precise, and it is definitely solvable.

If you read the problem, you realise that

1. The universe is defined as a square grid of square cells. There is no need to try to invent a coordinate system, as one is defined.

2. Pythag doesn't apply. It VERY CLEARLY states that moving diagonally is IDENTICAL IN COST to moving horizontally or vertically. This means that the "distance" of moving from (0,0) to (5,5) is IDENTICAL to moving from (0,0) to (0,5) or (0,0) to (5,0).

3. The ABSOLUTE VALUE of a coordinate is 10^9 (or possibly 109, but I don't think so). There is no constraint as to the distance between houses.

4. The infinite distance that you refer to abve clearly doesn't apply, and there will be a definite solution, because you only need to work out the distance between the houses for the N people. The problem statement does NOT state that there is a house in every cell of the grid, so there is no need to calculate assuming that there is.

5. Introducing physical world concepts of front and back doors to houses is daft. It is clear from the problem statement that there is no orientation to the house, and that entering it from any direction is allowed, otherwise it would have been stated.

I really don't think that you're helping the OP by applying your own artificial constraints to a fairly well known and common algorithmic homework problem, albeit that the problem has absolutely nothing to do with ASP.NET(!). By announcing (incorrectly) that the problem statement is unsolvable or incorrect makes it much harder for the OP to tackle the problem and therefore complete their homework, as you're probably making them more, rather than less, confused.

Regards

Dave

All-Star

20577 Points

5721 Posts

### Re: need solution to this problem in c#- help

@ DMW concluding my reply to you ...

Dave, your brute force method for the O.P. is an over simplification ... it fails when the pseudo random distribution offers multiple solutions, such as my example wthere there will be multiple best solutions ... example, 4 participants, one each, at (0,0)(9,0)(0,9)and  (9,9)

Likewise, 12 participants, one each, at ((0,0)(0,1)(1,0)), ((9,0), (9,1), (8,0)), ((1,9), (0,8)(0,9))and ((9,8), (8,9)(9,9)).

```9 ##......##
8 #........#
7 ..........
6 ..........
5 ..........
4 ..........
3 ..........
2 ..........
1 #........#
0 ##......##

0123456789```

g.

All-Star

20577 Points

5721 Posts

### Re: need solution to this problem in c#- help

@ DMW

Hi Dave ... yes, i have read the problem definition many times from which i have concluded that the problem definition is defective because it allows for assumptions.

1. (a) the universe is definition by the O.P. as "an infinite integer grid".

(b) a co-ordinate system is not defined, only hinted at:

"The absolute value of each co-ordinate in the input will be at most 10^9"
{the O.P.'s choice of font size looks like 10_subscript 9;
i'm guessing the O.P. intended 10_superscript 9 ???}

2. Pythagoras could apply, i was giving Pythagorous as an example at to what i perceive as a flaw ...

```"eg: (x,y) can be reached from (x-1,y+1) in a single unit of time."
3,6                        2 , 7

9 ..........
8 ..........
7 ..o.......
6 ...o......
5 ..........
4 ..........
3 ..........
2 ..........
1 ..........
0 ..........

0123456789```

3. the problem definition, by constraining the ABSOLUTE VALUE of a coordinate is ipso facto constraining the distance.

4. one only needs "to work out the distance between the houses for the N people" BUT N can be 0 to 10000 houses ... i've made no assumption that every cell has a house (although every cell could have a house); from the set of ALL houses, at any given time, we will never select more that 10000 and those houses must be selected from houses within the implied distance constraint.

(we also are assuming varible speed because the problem definition speaks about uniform units of time rather that distance; thus moving diagonally from corner to corner takes the same time even though the Pythagorean distance is greater on the diagonal).

5. "daft" ??? ... maybe ... Dave, please note that this was introduced only to demonstate the weakness of the problem definition ... the problem definer imho should have left out houses and used something like "cell surface" instead.

----

Dave, the O.P.'s problem is looking for a c# solution and could be related to ASP.NET (albeit a stretch) if one is creating a web page to solve such problems.

As a former college teacher, and also as a tutor to university and college students, imho, when a problem is poorly defined, as this one is, the student needs to query the problem definer in order to have a clear problem statement

that may be difficult for the O.P. because the problem was simply found on some web page somewhere on the internet.

N.B.:  imho, the problem, as stated by the O.P., is unsolvable.

-----