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 10^{9}

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.

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.

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.

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

p.s.: via Google, or your favourite search engine:

graph theory shortest path algorithm

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

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

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

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, fromcell c to cell c'' is 2 units, fromcell c to cell c'" is 3 units, fromcell c to cell c'''' is 4 units, fromcell c to cell c''''' is 5 units, fromcell 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:

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 999up,
0, 0 to 999 999 999diagonally 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).

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

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.

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

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

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

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

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

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 hintedat:

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

Would you please share the link to the problem with us?

thnx/gerry

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

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

gerry

Why do you think that?

You know the coordinate of every "house".

(I know you don't believe there's a coordinate system, but everyone else will see it as a 2D grid, as confirmed by the sample input data.)

Therefore you can work out the distance or time (they're the same, in effect, as true distance doesn't matter) between every "house", just by looking at the larger value of deltaX or deltaY. I mean, forgive me if I'm wrong, but the input is just an array
of X,Y coordinates up to 10000 in length. (Although I grant you that they don't specify that N > 0).

Therefore, for each house you can sum the times, given that N is not infinite, and that no coordinate can be infinite.

Therefore you can work out which of these is the lowest. Sure, there might be more than one that has the same value, but that doesn't matter; you can choose any of them.

Therefore the problem is eminently solvable.

I'm not sure why you talk about selecting houses and implied distance constraints. You never select a house - all the house information is clearly provided to you - and there is no implied distance constraint, merely an absolute constraint on what the coordinate
values of X and Y will be for each of the N houses.

The trivial solution is just

struct House
{
public long X;
public long Y;
}

and given a read-in input translated to some House[]

House[] houses = // read in from input ;
long minTime = long.MaxValue;

for( int i = 0; i < houses.Length; i++ )
{

long time = 0L;
for( int j = 0; j < houses.Length; j++ )
{

Dave, the reason i think that the problem as stated
is not solvable, is because of the stated "infinite" grid.

the problem should not imho mentioned the infinite grid because there is no reference point for any give
grid slice.

N.B.: if we choose a rectangle or square of cells within the grid, we can work with that slice.

The O.P. wrote: "From any given cell, all 8 adjacent cells are reachable in 1 unit of time."
BUT when we choose a grid slice, FWIW, we do introduce
edges and corners. corners have only three adjacent cells and non-corner edges have only five adject cells.

a =. adjacent cell
c =. corner cell
e =. edge cell (non-corner)
x =. non-corner and non-edge cell
9 ..........
8 ......aaa.
7 ......axa.
6 aa....aaa.
5 ea........
4 aa........
3 ..........
2 ..........
1 aa........
0 ca.........
0123456789

Dave, you wrote: "there might be more than one that has the same value, but that doesn't matter; you can choose any of them."

Then, imho, the problem should state that any of the shortest solutions is acceptable.

of course, if Dave's house is one of any acceptable solution's, then an algoritm that spits out "Dave's house" will likely always spit out "Dave's house".

Have you tried your solution on this 10 x 10 example?:

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

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Then, imho, the problem should state that any of the shortest solutions is acceptable.

It does, very clearly. It states " find A common meeting place". Not THE common meeting place. A common meeting place.

gerrylowry

imho mentioned the infinite grid

It has to, to stop people doing daft things like attempting to allocate 2D arrays, and to stop them thinking about edges. I don't quite understand why you keep talking about edges and corners, because they are completely irrelevant to the problem (and they
don't exist, of course, in an infinite grid).

What possible reason is there for looking at a slice? It can't help you in any way solve the problem, which is about finding shortest distances/times (pythag excepted) between cells.

gerrylowry

Have you tried your solution on this 10 x 10 example

Yes. The desired output answer, M, is 77. You can choose any one of EIGHT possible houses - not one of the four at 0,0 9,0, 0,9, 9,9. Which of the other eight doesn't matter, as the questioner merely wants A house that minimises the sum of the journey times.

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

One further thought, and I implied this earlier in an earlier post.

I don't consider my approach to be efficient. It is, I guess, O(n^2) in nature. Now if I was offering 50 marks for a question, then unless the marking system is pretty nuts I'd expect to be looking for another algorithm that is far more efficient than my
brute force approach.

But that's why it's an exam question!

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

Dave, this is the question to be answer (see the O.P.):

Find a common meeting place which minimises the sum of the travel times of all the persons.

You have not shown the "common meeting place".

9 ##......##
8 #........#
7 .......... <== no houses here
6 .......... <== no houses here
5 .......... <== no houses here
4 .......... <== no houses here
3 .......... <== no houses here
2 .......... <== no houses here
1 #........#
0 ##......##
0123456789

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

g.

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

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

M is 77. This is exactly what was asked, and this is confirmed PRECISELY by the sample data.

And please, please read my post. I stated EXTREMELY CLEARLY that you can use ANY of the EIGHT, non-"corner" houses if you wish to define A COMMON MEETING PLACE as well. Pick one. IT DOESN"T MATTER WHICH! THEY ALL YIELD THE VALUE OF M at 77.

Why are you deliberately trying to make this difficult? I have provided a solution to the OP, and you are trying to obfuscate it. Why?

Regards

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

Dave, i'm amazed that you think that i'm "deliberately trying to make this difficult". Can you not admit that the problem is
very poorly stated?

So, i'm not trying to obfuscate ... i'm doing what you, i, and our peers would do, i.e., i'm seeking clarification of what i as a professional programmer since 1967 perceive as a very
muddy problem specification. as a former community college teacher, i had to prepare examination questions ... not in a million years would i have made such a imho
poorly worded question. For example, the part about an infinite grid which can imho be iinterpreted as an
accidental or deliberate red herring, i do not know whether i'd put that in. FWIW, to your credit,
using your solution, after much thought, i see where that point
may be relevant (it eliminates giving much thought to edge conditions),

i'm still troubled with "Find a common meeting place which minimises the sum of the travel times of all the persons."

i've been experimenting with your solution and modified it slightly (using LINQPad 4*).

N.B.: this solution improperly ignores the condition of < 2 houses.

void Main()
{ House[] houses;
houses = new House[12];
// (0,0), (0,1), (1,0)
houses[ 0].X=0; houses[ 0].Y=0;
houses[ 1].X=0; houses[ 1].Y=1;
houses[ 2].X=1; houses[ 2].Y=0;
// (9,0), (9,1), (8,0)
houses[ 3].X=9; houses[ 3].Y=0;
houses[ 4].X=9; houses[ 4].Y=1;
houses[ 5].X=8; houses[ 5].Y=0;
// (1,9), (0,8), (0,9)
houses[ 6].X=1; houses[ 6].Y=9;
houses[ 7].X=0; houses[ 7].Y=8;
houses[ 8].X=0; houses[ 8].Y=9;
// (9,8), (8,9), (9,9)
houses[ 9].X=9; houses[ 9].Y=8;
houses[10].X=8; houses[10].Y=9;
houses[11].X=9; houses[11].Y=9;
// foreach (House house in houses) house.Dump();
long minTime = getResult(houses);
Console.WriteLine ("minimum cumulative travel time == {0} units", minTime);
}
public struct House { public long X; public long Y; public long computedTime; }
public long getResult(House[] houses)
{
long minTime = long.MaxValue;
long time;
Int32 housesToCheck = houses.Length;
// checking ALL the houses ... it would be better if would check just the first half
for( int i = 0; i < housesToCheck; i++ )
{ time = 0L;
for( int j = 0; j < houses.Length; j++ ) // if we check half, the half must be checked against ALL
{ long timeInterval = Math.Max( Math.Abs( houses[i].Y - houses[j].Y ), Math.Abs( houses[i].X - houses[j].X ) );
time += timeInterval;
Console
.WriteLine ("i {0}, j {1} :: house {2},{3} :: house {4},{5} :: time {6}, cumulative {7}",
i, j, houses[i].X, houses[i].Y, houses[j].X, houses[j].Y, timeInterval, time );
} // for( int j = 0; j < houses.Length; j++ )
Console.WriteLine ("........................ {0}, {1}\r\n", time, minTime);
houses[i].computedTime = time;
if( time < minTime ) minTime = time;
} // for( int i = 0; i < housesToCheck; i++ )
Console.WriteLine ("Meeting Place(s)");
foreach (House house in houses)
{
if (house.computedTime <= minTime) // should never be <
{
Console.WriteLine ("house {0},{1} :: time {2}", house.X, house.Y, house.computedTime);
}
}
Console.WriteLine ("Non-Meeting Place(s)");
foreach (House house in houses)
{
if (house.computedTime > minTime)
{
Console.WriteLine ("house {0},{1} :: time {2}", house.X, house.Y, house.computedTime);
}
}
return minTime;
}

The last part of the output:

Meeting Place(s)
house 0,1 :: time 77
house 1,0 :: time 77
house 9,1 :: time 77
house 8,0 :: time 77
house 1,9 :: time 77
house 0,8 :: time 77
house 9,8 :: time 77
house 8,9 :: time 77
Non-Meeting Place(s)
house 0,0 :: time 81
house 9,0 :: time 81
house 0,9 :: time 81
house 9,9 :: time 81
minimum cumulative travel time == 77 units

g.

* if you do not have LINQPad 4:

TOOLS ... get yourself a FREE copy of LINQPad 4 (http://linqpad.net) .. Joe Albahari's LINQPad 4 is an awesome programmer's scratch pad that enables you to quickly check out code snippets you find in books and on web sites plus LINQPad also lets you rapidly experiment with c# ideas before committing them to vs2010.

LINQPad 4 supports c#, F#, SQL, vb.

first part of the output:

i 0, j 0 :: house 0,0 :: house 0,0 :: time 0, cumulative 0
i 0, j 1 :: house 0,0 :: house 0,1 :: time 1, cumulative 1
i 0, j 2 :: house 0,0 :: house 1,0 :: time 1, cumulative 2
i 0, j 3 :: house 0,0 :: house 9,0 :: time 9, cumulative 11
i 0, j 4 :: house 0,0 :: house 9,1 :: time 9, cumulative 20
i 0, j 5 :: house 0,0 :: house 8,0 :: time 8, cumulative 28
i 0, j 6 :: house 0,0 :: house 1,9 :: time 9, cumulative 37
i 0, j 7 :: house 0,0 :: house 0,8 :: time 8, cumulative 45
i 0, j 8 :: house 0,0 :: house 0,9 :: time 9, cumulative 54
i 0, j 9 :: house 0,0 :: house 9,8 :: time 9, cumulative 63
i 0, j 10 :: house 0,0 :: house 8,9 :: time 9, cumulative 72
i 0, j 11 :: house 0,0 :: house 9,9 :: time 9, cumulative 81
........................ 81, 9223372036854775807
i 1, j 0 :: house 0,1 :: house 0,0 :: time 1, cumulative 1
i 1, j 1 :: house 0,1 :: house 0,1 :: time 0, cumulative 1
i 1, j 2 :: house 0,1 :: house 1,0 :: time 1, cumulative 2
i 1, j 3 :: house 0,1 :: house 9,0 :: time 9, cumulative 11
i 1, j 4 :: house 0,1 :: house 9,1 :: time 9, cumulative 20
i 1, j 5 :: house 0,1 :: house 8,0 :: time 8, cumulative 28
i 1, j 6 :: house 0,1 :: house 1,9 :: time 8, cumulative 36
i 1, j 7 :: house 0,1 :: house 0,8 :: time 7, cumulative 43
i 1, j 8 :: house 0,1 :: house 0,9 :: time 8, cumulative 51
i 1, j 9 :: house 0,1 :: house 9,8 :: time 9, cumulative 60
i 1, j 10 :: house 0,1 :: house 8,9 :: time 8, cumulative 68
i 1, j 11 :: house 0,1 :: house 9,9 :: time 9, cumulative 77
........................ 77, 81
i 2, j 0 :: house 1,0 :: house 0,0 :: time 1, cumulative 1
i 2, j 1 :: house 1,0 :: house 0,1 :: time 1, cumulative 2
i 2, j 2 :: house 1,0 :: house 1,0 :: time 0, cumulative 2
i 2, j 3 :: house 1,0 :: house 9,0 :: time 8, cumulative 10
i 2, j 4 :: house 1,0 :: house 9,1 :: time 8, cumulative 18
i 2, j 5 :: house 1,0 :: house 8,0 :: time 7, cumulative 25
i 2, j 6 :: house 1,0 :: house 1,9 :: time 9, cumulative 34
i 2, j 7 :: house 1,0 :: house 0,8 :: time 8, cumulative 42
i 2, j 8 :: house 1,0 :: house 0,9 :: time 9, cumulative 51
i 2, j 9 :: house 1,0 :: house 9,8 :: time 8, cumulative 59
i 2, j 10 :: house 1,0 :: house 8,9 :: time 9, cumulative 68
i 2, j 11 :: house 1,0 :: house 9,9 :: time 9, cumulative 77
........................ 77, 77
i 3, j 0 :: house 9,0 :: house 0,0 :: time 9, cumulative 9
i 3, j 1 :: house 9,0 :: house 0,1 :: time 9, cumulative 18
i 3, j 2 :: house 9,0 :: house 1,0 :: time 8, cumulative 26
i 3, j 3 :: house 9,0 :: house 9,0 :: time 0, cumulative 26
i 3, j 4 :: house 9,0 :: house 9,1 :: time 1, cumulative 27
i 3, j 5 :: house 9,0 :: house 8,0 :: time 1, cumulative 28
i 3, j 6 :: house 9,0 :: house 1,9 :: time 9, cumulative 37
i 3, j 7 :: house 9,0 :: house 0,8 :: time 9, cumulative 46
i 3, j 8 :: house 9,0 :: house 0,9 :: time 9, cumulative 55
i 3, j 9 :: house 9,0 :: house 9,8 :: time 8, cumulative 63
i 3, j 10 :: house 9,0 :: house 8,9 :: time 9, cumulative 72
i 3, j 11 :: house 9,0 :: house 9,9 :: time 9, cumulative 81
........................ 81, 77
i 4, j 0 :: house 9,1 :: house 0,0 :: time 9, cumulative 9
i 4, j 1 :: house 9,1 :: house 0,1 :: time 9, cumulative 18
i 4, j 2 :: house 9,1 :: house 1,0 :: time 8, cumulative 26
i 4, j 3 :: house 9,1 :: house 9,0 :: time 1, cumulative 27
i 4, j 4 :: house 9,1 :: house 9,1 :: time 0, cumulative 27
i 4, j 5 :: house 9,1 :: house 8,0 :: time 1, cumulative 28
i 4, j 6 :: house 9,1 :: house 1,9 :: time 8, cumulative 36
i 4, j 7 :: house 9,1 :: house 0,8 :: time 9, cumulative 45
i 4, j 8 :: house 9,1 :: house 0,9 :: time 9, cumulative 54
i 4, j 9 :: house 9,1 :: house 9,8 :: time 7, cumulative 61
i 4, j 10 :: house 9,1 :: house 8,9 :: time 8, cumulative 69
i 4, j 11 :: house 9,1 :: house 9,9 :: time 8, cumulative 77
........................ 77, 77
i 5, j 0 :: house 8,0 :: house 0,0 :: time 8, cumulative 8
i 5, j 1 :: house 8,0 :: house 0,1 :: time 8, cumulative 16
i 5, j 2 :: house 8,0 :: house 1,0 :: time 7, cumulative 23
i 5, j 3 :: house 8,0 :: house 9,0 :: time 1, cumulative 24
i 5, j 4 :: house 8,0 :: house 9,1 :: time 1, cumulative 25
i 5, j 5 :: house 8,0 :: house 8,0 :: time 0, cumulative 25
i 5, j 6 :: house 8,0 :: house 1,9 :: time 9, cumulative 34
i 5, j 7 :: house 8,0 :: house 0,8 :: time 8, cumulative 42
i 5, j 8 :: house 8,0 :: house 0,9 :: time 9, cumulative 51
i 5, j 9 :: house 8,0 :: house 9,8 :: time 8, cumulative 59
i 5, j 10 :: house 8,0 :: house 8,9 :: time 9, cumulative 68
i 5, j 11 :: house 8,0 :: house 9,9 :: time 9, cumulative 77
........................ 77, 77
i 6, j 0 :: house 1,9 :: house 0,0 :: time 9, cumulative 9
i 6, j 1 :: house 1,9 :: house 0,1 :: time 8, cumulative 17
i 6, j 2 :: house 1,9 :: house 1,0 :: time 9, cumulative 26
i 6, j 3 :: house 1,9 :: house 9,0 :: time 9, cumulative 35
i 6, j 4 :: house 1,9 :: house 9,1 :: time 8, cumulative 43
i 6, j 5 :: house 1,9 :: house 8,0 :: time 9, cumulative 52
i 6, j 6 :: house 1,9 :: house 1,9 :: time 0, cumulative 52
i 6, j 7 :: house 1,9 :: house 0,8 :: time 1, cumulative 53
i 6, j 8 :: house 1,9 :: house 0,9 :: time 1, cumulative 54
i 6, j 9 :: house 1,9 :: house 9,8 :: time 8, cumulative 62
i 6, j 10 :: house 1,9 :: house 8,9 :: time 7, cumulative 69
i 6, j 11 :: house 1,9 :: house 9,9 :: time 8, cumulative 77
........................ 77, 77
i 7, j 0 :: house 0,8 :: house 0,0 :: time 8, cumulative 8
i 7, j 1 :: house 0,8 :: house 0,1 :: time 7, cumulative 15
i 7, j 2 :: house 0,8 :: house 1,0 :: time 8, cumulative 23
i 7, j 3 :: house 0,8 :: house 9,0 :: time 9, cumulative 32
i 7, j 4 :: house 0,8 :: house 9,1 :: time 9, cumulative 41
i 7, j 5 :: house 0,8 :: house 8,0 :: time 8, cumulative 49
i 7, j 6 :: house 0,8 :: house 1,9 :: time 1, cumulative 50
i 7, j 7 :: house 0,8 :: house 0,8 :: time 0, cumulative 50
i 7, j 8 :: house 0,8 :: house 0,9 :: time 1, cumulative 51
i 7, j 9 :: house 0,8 :: house 9,8 :: time 9, cumulative 60
i 7, j 10 :: house 0,8 :: house 8,9 :: time 8, cumulative 68
i 7, j 11 :: house 0,8 :: house 9,9 :: time 9, cumulative 77
........................ 77, 77
i 8, j 0 :: house 0,9 :: house 0,0 :: time 9, cumulative 9
i 8, j 1 :: house 0,9 :: house 0,1 :: time 8, cumulative 17
i 8, j 2 :: house 0,9 :: house 1,0 :: time 9, cumulative 26
i 8, j 3 :: house 0,9 :: house 9,0 :: time 9, cumulative 35
i 8, j 4 :: house 0,9 :: house 9,1 :: time 9, cumulative 44
i 8, j 5 :: house 0,9 :: house 8,0 :: time 9, cumulative 53
i 8, j 6 :: house 0,9 :: house 1,9 :: time 1, cumulative 54
i 8, j 7 :: house 0,9 :: house 0,8 :: time 1, cumulative 55
i 8, j 8 :: house 0,9 :: house 0,9 :: time 0, cumulative 55
i 8, j 9 :: house 0,9 :: house 9,8 :: time 9, cumulative 64
i 8, j 10 :: house 0,9 :: house 8,9 :: time 8, cumulative 72
i 8, j 11 :: house 0,9 :: house 9,9 :: time 9, cumulative 81
........................ 81, 77
i 9, j 0 :: house 9,8 :: house 0,0 :: time 9, cumulative 9
i 9, j 1 :: house 9,8 :: house 0,1 :: time 9, cumulative 18
i 9, j 2 :: house 9,8 :: house 1,0 :: time 8, cumulative 26
i 9, j 3 :: house 9,8 :: house 9,0 :: time 8, cumulative 34
i 9, j 4 :: house 9,8 :: house 9,1 :: time 7, cumulative 41
i 9, j 5 :: house 9,8 :: house 8,0 :: time 8, cumulative 49
i 9, j 6 :: house 9,8 :: house 1,9 :: time 8, cumulative 57
i 9, j 7 :: house 9,8 :: house 0,8 :: time 9, cumulative 66
i 9, j 8 :: house 9,8 :: house 0,9 :: time 9, cumulative 75
i 9, j 9 :: house 9,8 :: house 9,8 :: time 0, cumulative 75
i 9, j 10 :: house 9,8 :: house 8,9 :: time 1, cumulative 76
i 9, j 11 :: house 9,8 :: house 9,9 :: time 1, cumulative 77
........................ 77, 77
i 10, j 0 :: house 8,9 :: house 0,0 :: time 9, cumulative 9
i 10, j 1 :: house 8,9 :: house 0,1 :: time 8, cumulative 17
i 10, j 2 :: house 8,9 :: house 1,0 :: time 9, cumulative 26
i 10, j 3 :: house 8,9 :: house 9,0 :: time 9, cumulative 35
i 10, j 4 :: house 8,9 :: house 9,1 :: time 8, cumulative 43
i 10, j 5 :: house 8,9 :: house 8,0 :: time 9, cumulative 52
i 10, j 6 :: house 8,9 :: house 1,9 :: time 7, cumulative 59
i 10, j 7 :: house 8,9 :: house 0,8 :: time 8, cumulative 67
i 10, j 8 :: house 8,9 :: house 0,9 :: time 8, cumulative 75
i 10, j 9 :: house 8,9 :: house 9,8 :: time 1, cumulative 76
i 10, j 10 :: house 8,9 :: house 8,9 :: time 0, cumulative 76
i 10, j 11 :: house 8,9 :: house 9,9 :: time 1, cumulative 77
........................ 77, 77
i 11, j 0 :: house 9,9 :: house 0,0 :: time 9, cumulative 9
i 11, j 1 :: house 9,9 :: house 0,1 :: time 9, cumulative 18
i 11, j 2 :: house 9,9 :: house 1,0 :: time 9, cumulative 27
i 11, j 3 :: house 9,9 :: house 9,0 :: time 9, cumulative 36
i 11, j 4 :: house 9,9 :: house 9,1 :: time 8, cumulative 44
i 11, j 5 :: house 9,9 :: house 8,0 :: time 9, cumulative 53
i 11, j 6 :: house 9,9 :: house 1,9 :: time 8, cumulative 61
i 11, j 7 :: house 9,9 :: house 0,8 :: time 9, cumulative 70
i 11, j 8 :: house 9,9 :: house 0,9 :: time 9, cumulative 79
i 11, j 9 :: house 9,9 :: house 9,8 :: time 1, cumulative 80
i 11, j 10 :: house 9,9 :: house 8,9 :: time 1, cumulative 81
i 11, j 11 :: house 9,9 :: house 9,9 :: time 0, cumulative 81
........................ 81, 77

*** END ***

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

Would you please share the link to the problem with us?

Note: although Dave and i have some degree of disagreement regarding the
statement of the problem, Dave's solution works (http://forums.asp.net/post/4869762.aspx).

Dave and i both agree that his solution could be more efficient; however, imho, Dave's solution is sufficient for getting 50 points (because of the way the problem has been stated) since Dave's solution fulfils the requirement.

again, for my benefit, ashok, please share the link to the problem with us.

Thank you.
Gerry

B-) Gerry Lowry, Chief Training Architect, Paradigm Mentors Learning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it

## ashok2009cse

Member

119 Points

110 Posts

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

Mar 07, 2012 11:13 AM|ashok2009cse|LINK

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

Npeople 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:NThe following

Nlines will contain two integers saying the x & y coordinate of the i-th person.Output Format:MM = min sum of all travel times;Constraints:

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

^{9}HINT:Please use long long 64-bit integers;## adamturner34

Contributor

2789 Points

1294 Posts

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

Mar 07, 2012 02:04 PM|adamturner34|LINK

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.

## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 07, 2012 03:45 PM|gerrylowry|LINK

@ ashok2009cse

is this a homework assignment:

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

it's unsolvable if it's infinite.

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

somethinglike 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 houseso according toyourproblem definition, that someone might not be one of the people who wish to meet.(d) your problem is simpler if the someone's house

mustbe a home of one of the meeting participants ... for this restricted case, the distance for one participant will always bezero. 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.

B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 07, 2012 03:51 PM|gerrylowry|LINK

@ ashok2009cse

p.s.: via Google, or your favourite search engine:

graph theory shortest path algorithm

B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## DMW

Contributor

5024 Points

2404 Posts

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

Mar 07, 2012 08:19 PM|DMW|LINK

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

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.

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 08, 2012 08:23 AM|gerrylowry|LINK

@ DMW

the problem statement appears defective ...

the infinite grid may be a red herring.

The constraints are interesting.

Npeople constrained byN <= 10000givesN == 0 | 1 | 2 | 3 | ... | 9998 | 9999 | 10000since we can not have< 0people.N == 0has no solution.if we only meet at the home of a participant,

N == 1would meet in her/his own home, a distance ofzero.aOTOH, if the meeting home can be

, given a infinity grid there isany homeno solution...fromfromfrom

from

cell c to cell c' is one unit,

fromcell c to cell c'' is 2 units,

cell c to cell c'" is 3 units,

fromcell c to cell c'''' is 4 units,cell c to cell c''''' is 5 units,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 value10^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 ...from...xwe can move only in8 directions(assuming ourcellsareuniform squares)our directions are

up,down,left,right,diagonally up left,diagonally up right,, anddiagonally down leftdiagonally down rightthis means that we cannotalways move in a straight lineso, our co-ordinate system much be adirectionand avalueifxis at0, 0, then we could have someone (harry) at 999 999 999 upifxis at0, 0, then we could have someone (mary) at 999 999 999 downnow, we have a problem ... (harry) and (mary) each meet the distance constraint (10^9) withx, but fail it with each other.for simplicity, let'spretend that we have an edge corner, likea1on the chessboard, and called it0, 0... we can also have0, 999 999 999 rightand0, 999 999 999 up... then,n diagonalwould take us from0, 0 to 999 999 999 diagonally up right, .... because we are measuring distance by cell count,0, 0to999 999 999up,0, 0to999 999 999diagonally up right, and0, 0to999 999 999 rightALL seem to be the same distance, however, thediagonal (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 awayd1, c2, b2, a3 == 3cells awayd1, c1, b1, a2, a3 == 4 cells awayof 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).B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 08, 2012 08:40 AM|gerrylowry|LINK

@ DMW continuing my reply to you ...

(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

infinitegrid or there areinfinite edges ...likely you are correct when you state "Because the grid is infinite,there are no edges".g.B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## DMW

Contributor

5024 Points

2404 Posts

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

Mar 08, 2012 08:54 AM|DMW|LINK

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.

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 08, 2012 09:08 AM|gerrylowry|LINK

@ 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,

12participants, 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)).g.

B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 08, 2012 09:50 AM|gerrylowry|LINK

@ 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

notdefined, onlyat:hinted"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

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

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

ipso factoconstraining the distance.4. one only needs "to work out the distance between the houses for the N people" BUT N can be

0to10000houses ... 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 willneverselect more that10000and those houses must be selected from houses within the implied distance constraint.(we also are assuming

speed because the problem definition speaks aboutvaribleuniformunits oftimerather 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.-----@ashok2009cseWould you please share the link to the problem with us?

thnx/gerry

B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## DMW

Contributor

5024 Points

2404 Posts

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

Mar 08, 2012 10:43 AM|DMW|LINK

gerry

Why do you think that?

You know the coordinate of every "house".

(I know you don't believe there's a coordinate system, but everyone else will see it as a 2D grid, as confirmed by the sample input data.)

Therefore you can work out the distance or time (they're the same, in effect, as true distance doesn't matter) between every "house", just by looking at the larger value of deltaX or deltaY. I mean, forgive me if I'm wrong, but the input is just an array of X,Y coordinates up to 10000 in length. (Although I grant you that they don't specify that N > 0).

Therefore, for each house you can sum the times, given that N is not infinite, and that no coordinate can be infinite.

Therefore you can work out which of these is the lowest. Sure, there might be more than one that has the same value, but that doesn't matter; you can choose any of them.

Therefore the problem is eminently solvable.

I'm not sure why you talk about selecting houses and implied distance constraints. You never select a house - all the house information is clearly provided to you - and there is no implied distance constraint, merely an absolute constraint on what the coordinate values of X and Y will be for each of the N houses.

The trivial solution is just

struct House

{

public long X;

public long Y;

}

and given a read-in input translated to some House[]

House[] houses = // read in from input ;

long minTime = long.MaxValue;

for( int i = 0; i < houses.Length; i++ )

{

long time = 0L;

for( int j = 0; j < houses.Length; j++ )

{

time += Math.Max( Math.Abs( houses[i].Y - houses[j].Y ), Math.Abs( houses[i].X - houses[j].X ) );

}

if( time < minTime )

minTime = time;

}

I don't really see what's so difficult in that (and no, I've invested nothing in making the algorithm efficient)!

Dave

Provide an answer, and you enable a developer to code today. Show them how to find the answer using Google, and they can code forever.

## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 08, 2012 11:14 AM|gerrylowry|LINK

Dave, the reason i think that the problem

isas statednot solvable, is because of thestated ".infinite" gridthe problem should not imho mentioned the infinite grid because there is no reference point for any give

gridslice.N.B.: if we choose a rectangle or square of cells within the grid, we can work with that slice.The O.P. wrote: "From any given cell, all 8 adjacent cells are reachable in 1 unit of time."

BUTwhen we choose agridslice, FWIW, we do introduceedgesandcorners.cornershave only three adjacent cells and non-corner edges have only five adject cells.Dave, you wrote: "there might be more than one that has the same value, but

that doesn't matter; you can choose any of them."Then, imho, the problem should state that any of the shortest solutions is acceptable.

of course, if Dave's house is one of any acceptable solution's, then an algoritm that spits out "Dave's house" will likely always spit out "Dave's house".

Have you tried your solution on this 10 x 10 example?:

Likewise,

12participants, 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)).g.

B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## DMW

Contributor

5024 Points

2404 Posts

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

Mar 08, 2012 01:57 PM|DMW|LINK

It does, very clearly. It states " find A common meeting place". Not THE common meeting place. A common meeting place.

It has to, to stop people doing daft things like attempting to allocate 2D arrays, and to stop them thinking about edges. I don't quite understand why you keep talking about edges and corners, because they are completely irrelevant to the problem (and they don't exist, of course, in an infinite grid).

What possible reason is there for looking at a slice? It can't help you in any way solve the problem, which is about finding shortest distances/times (pythag excepted) between cells.

Yes. The desired output answer, M, is 77. You can choose any one of EIGHT possible houses - not one of the four at 0,0 9,0, 0,9, 9,9. Which of the other eight doesn't matter, as the questioner merely wants A house that minimises the sum of the journey times.

Dave

## DMW

Contributor

5024 Points

2404 Posts

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

Mar 08, 2012 02:31 PM|DMW|LINK

One further thought, and I implied this earlier in an earlier post.

I don't consider my approach to be efficient. It is, I guess, O(n^2) in nature. Now if I was offering 50 marks for a question, then unless the marking system is pretty nuts I'd expect to be looking for another algorithm that is far more efficient than my brute force approach.

But that's why it's an exam question!

Dave

## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 08, 2012 06:59 PM|gerrylowry|LINK

@ DMW

Dave, this is the question to be answer (see the O.P.):

Find a

common meeting placewhich minimises the sum of the travel times of all the persons.You have not shown the "

.common meeting place"12participants, 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)).g.

B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## DMW

Contributor

5024 Points

2404 Posts

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

Mar 08, 2012 08:30 PM|DMW|LINK

gerry

Please, please read the OP's question properly!

I will quote it for you

"

Output Format:MM = min sum of all travel times;"M is 77. This is exactly what was asked, and this is confirmed PRECISELY by the sample data.

And please, please read my post. I stated EXTREMELY CLEARLY that you can use ANY of the EIGHT, non-"corner" houses if you wish to define A COMMON MEETING PLACE as well. Pick one. IT DOESN"T MATTER WHICH! THEY ALL YIELD THE VALUE OF M at 77.

Why are you deliberately trying to make this difficult? I have provided a solution to the OP, and you are trying to obfuscate it. Why?

Dave

## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 09, 2012 01:54 PM|gerrylowry|LINK

@ DMW,

Dave, i'm amazed that you think that i'm "deliberately trying to make this difficult". Can you not admit that the problem is

very poorlystated?So, i'm not trying to obfuscate ... i'm doing what you, i, and our peers would do, i.e., i'm seeking clarification of what i as a professional programmer since 1967 perceive as a very

muddyproblem specification. as a former community college teacher, i had to prepare examination questions ... not in a million years would i have made such a imhopoorly wordedquestion. For example, the part about aninfinite gridwhich can imho be iinterpreted as anaccidentalordeliberate red herring, i do not know whether i'd put that in. FWIW, to your credit,using, after much thought, i see where that point may be relevant (it eliminates giving much thought to edge conditions),yoursolutioni'm still troubled with "Find a common meeting place which minimises the sum of the travel times of all the persons."

i've been experimenting with your solution and modified it slightly (using LINQPad 4*).

N.B.: this solutionimproperlyignores the condition of < 2 houses.The last part of the output:

g.

* if you do not have LINQPad 4:

TOOLS ... get yourself a FREE copy of LINQPad 4 (http://linqpad.net) .. Joe Albahari's LINQPad 4 is an awesome programmer's scratch pad that enables you to quickly check out code snippets you find in books and on web sites plus LINQPad also lets you rapidly experiment with c# ideas before committing them to vs2010.

LINQPad 4 supports c#, F#, SQL, vb.

first part of the output:

*** END ***

B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it## gerrylowry

Star

12990 Points

5547 Posts

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

Mar 09, 2012 02:12 PM|gerrylowry|LINK

@ashok2009cseWould you

please share the link to the problemwith us?Note: although Dave and i have some degree of disagreement regarding the

statementof the problem, Dave's solution works (http://forums.asp.net/post/4869762.aspx).aahok, at some point, i suggest that you mark Dave's answer (http://forums.asp.net/post/4869762.aspx) as "the answer" ...

Dave and i both agree that his solution could be more efficient; however, imho, Dave's solution is sufficient for getting 50 points (because of the way the problem has been stated) since Dave's solution fulfils the requirement.

again, for my benefit, ashok,

please share the link to the problemwith us.Thank you.

Gerry

B-) Gerry Lowry, Chief Training Architect,Paradigm MentorsLearning never ends... +1 705-999-9195 wasaga beach, ontario canada TIMTOWTDI =.there is more than one way to do it