## 855 - Lunch in Grid City

**Moderator:** Board moderators

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

Hope you understand.

Then for any element b

Code: Select all

`|x1-a| + |x2-a| + ... + |xn-a| <= |x1-b| + |x2-b| + ... + |xn-b|`

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|
Adding them both we obtain
|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|)
```

Ami ekhono shopno dekhi...

HomePage

HomePage

### 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**Location:**IUT-OIC, DHAKA, BANGLADESH-
**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...............................

It is more tough to become a good person.

I am trying both...............................

### Re: 855 - Lunch in Grid City

Code: Select all

```
int cmp(const void *a, const void *b){
return *(int *)a - *(int *)b;
}
```

Thanks

Sapnil

**"Dream Is The Key To Success"**

@@@ Jony @@@

- kbr_iut
- Experienced poster
**Posts:**103**Joined:**Tue Mar 25, 2008 11:00 pm**Location:**IUT-OIC, DHAKA, BANGLADESH-
**Contact:**

### Re: 855 - Lunch in Grid City

Sapnil wrote

I dont get ur point,,,previous code works well.I think cmp function is okay.>>>> I thing the problem on ur cmp function. sometimes it cross the range of intiger.

It is tough to become a good programmer.

It is more tough to become a good person.

I am trying both...............................

It is more tough to become a good person.

I am trying both...............................

### Re: 855 - Lunch in Grid City

>> Sorry i think the input be negetive number.

>> change here:
thanks

sapnil

>> 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]);
```

sapnil

**"Dream Is The Key To Success"**

@@@ Jony @@@

### Re: 855 - Lunch in Grid City

Code: Select all

`thanks kabir.........don't forget to remove that code`

Last edited by apurba on Sat Jul 19, 2008 9:29 am, edited 1 time in total.

Code: Select all

`keep dreaming...`

### Re: 855 - Lunch in Grid City

i have not used you output format, but got AC..........sapnil wrote:>> Sorry i think the input be negetive number.

>> change here:thanksCode: 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]);`

sapnil

Code: Select all

`keep dreaming...`

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

please check someone

here is the code:

pls help

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

please check someone

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.

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

### Re: 855 - Lunch in Grid City

I have sort out the problem mentioned above

But still WA

is there anything more to change??

But still WA

is there anything more to change??

### Re: 855 - Lunch in Grid City

problem description say..

1

2 2 2

1 1

3 3

the output should be (1, 1) not (2, 2)

hope this helps..

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

1

2 2 2

1 1

3 3

the output should be (1, 1) not (2, 2)

hope this helps..

hmm..

### 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 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??