## 855 - Lunch in Grid City

Moderator: Board moderators

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
got it and got AC too. thanks for ur continuous help.

this world is weird! dont understand why the algorithm works!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Don't you understand? You should read about median. Suppose 'a' is the median of a set {x1,x2,..,xn}
Then for any element b

Code: Select all

``|x1-a| + |x2-a| + ... + |xn-a| <= |x1-b| + |x2-b| + ... + |xn-b|``
But in this problem you have to consider it in a 2*D plane. So, you can think of them seperately. The proof is given below:

Consider a set containing all the streets, and another containing all the avenues. Then you can count different medians from the two sets. Suppose the two sets are {x1,x2,...,xn}, {y1,y2,...,yn} and ax and ay are the medians respectively. Then for any point (bx,by) we get

Code: Select all

``````|x1-ax| + |x2-ax| + ... + |xn-ax| <= |x1-bx| + |x2-bx| + ... + |xn-bx|
and
|y1-ay| + |y2-ay| + ... + |yn-ay| <= |y1-by| + |y2-by| + ... + |yn-by|

|x1-ax| + |x2-ax| + ... + |xn-ax| + |y1-ay| + |y2-ay| + ... + |yn-ay| <=
|x1-bx| + |x2-bx| + ... + |xn-bx| + |y1-by| + |y2-by| + ... + |yn-by|

And we can rewrite

(|x1-ax|+|y1-ay|) + (|x2-ax|+|y2-ay|) + ... + (|xn-ax|+|yn-ay|) <=
(|x1-bx|+|y1-by|) + (|x2-bx|+|y2-by|) + ... + (|xn-bx|+|yn-by|)``````
Hope you understand.
Ami ekhono shopno dekhi...
HomePage

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
i understand why median is the answer. but i though it in a different way. i keep track of every friend in a structure, which contains the street and avenue numbers. then i first sort the array of the structure by street. then, i sort the elements of array whose street number are same. this time i sort by avenue. resulted in WA many times. my assumption was wrong. it is the way u did it.

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

### Re: 855 - Lunch in Grid City

Code: Select all

``use quick sort for avoiding TLE``
Last edited by apurba on Sat Jul 19, 2008 9:11 am, edited 1 time in total.

Code: Select all

``keep dreaming...``

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 855 - Lunch in Grid City

use quick sort.
Last edited by kbr_iut on Sat Jul 19, 2008 11:41 am, edited 1 time in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

### Re: 855 - Lunch in Grid City

Code: Select all

``````int cmp(const void *a, const void *b){
return *(int *)a - *(int *)b;
}``````
>>>> I thing the problem on ur cmp function. sometimes it cross the range of intiger.

Thanks
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 855 - Lunch in Grid City

Sapnil wrote
>>>> I thing the problem on ur cmp function. sometimes it cross the range of intiger.
I dont get ur point,,,previous code works well.I think cmp function is okay.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

### Re: 855 - Lunch in Grid City

>> Sorry i think the input be negetive number.

>> change here:

Code: Select all

``````if(f%2==0) printf("(Street: %ld, Avenue: %ld)\n", str[f/2-1], ave[f/2-1]);
else printf("(Street: %ld, Avenue: %ld)\n", str[f/2+1], ave[f/2+1]);
``````
thanks
sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

### Re: 855 - Lunch in Grid City

Code: Select all

``thanks kabir.........don't forget to remove that code``
[/b]
Last edited by apurba on Sat Jul 19, 2008 9:29 am, edited 1 time in total.

Code: Select all

``keep dreaming...``

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

### Re: 855 - Lunch in Grid City

sapnil wrote:>> Sorry i think the input be negetive number.

>> change here:

Code: Select all

``````if(f%2==0) printf("(Street: %ld, Avenue: %ld)\n", str[f/2-1], ave[f/2-1]);
else printf("(Street: %ld, Avenue: %ld)\n", str[f/2+1], ave[f/2+1]);
``````
thanks
sapnil
i have not used you output format, but got AC..........

Code: Select all

``keep dreaming...``

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

### Re: 855 - Lunch in Grid City WA

Why I am getting WA
I think I have passed all the I/O given in the board
is there any more critical I/O or the problem is somewhere else
here is the code:

Code: Select all

``````Removed
``````

pls help
Last edited by abid_iut on Sat Dec 20, 2008 12:01 pm, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 855 - Lunch in Grid City

sort(s, s+f) sorts elements s[0], s[1], ..., s[f-1]. But your data is in s[1]...s[f], so you're off by one there.

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

### Re: 855 - Lunch in Grid City

I have sort out the problem mentioned above
But still WA
is there anything more to change??
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 855 - Lunch in Grid City

problem description say..
Please note that if we add another friend located at, say street 3 and avenue 5, making a total of 12 friends, then we would have two candidate meeting points, pairs (3,4) and (3,5). The rule clearly defines that street 3 and avenue 4 is the meeting point.
for test
1
2 2 2
1 1
3 3
the output should be (1, 1) not (2, 2)

hope this helps..
hmm..

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

### Re: 855 - Lunch in Grid City

I am sorry
I don't understand how the output for the input

1
2 2 2
1 1
3 3

become 1,1
it should be 2,2
i think we have to find the median.
can U pls explain a bit more??
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/