855 - Lunch in Grid City

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo » Tue Oct 31, 2006 4:38 pm

got it and got AC too. :D thanks for ur continuous help.

this world is weird! dont understand why the algorithm works! :(
Image

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Oct 31, 2006 5:52 pm

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|

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|)
Hope you understand.
Ami ekhono shopno dekhi...
HomePage

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo » Wed Nov 01, 2006 1:49 pm

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

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

Re: 855 - Lunch in Grid City

Post by apurba » Tue Jul 01, 2008 8:25 pm

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

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

Post by kbr_iut » Wed Jul 09, 2008 11:42 am

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

Post by sapnil » Thu Jul 17, 2008 12:47 am

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

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

Post by kbr_iut » Thu Jul 17, 2008 12:59 pm

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

Post by sapnil » Thu Jul 17, 2008 6:25 pm

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

Post by apurba » Sat Jul 19, 2008 9:23 am

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

Post by apurba » Sat Jul 19, 2008 9:27 am

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

Post by abid_iut » Mon Dec 15, 2008 9:47 pm

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:

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

Post by mf » Mon Dec 15, 2008 10:41 pm

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

Post by abid_iut » Tue Dec 16, 2008 7:11 pm

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

Post by newkid » Wed Dec 17, 2008 11:45 pm

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

Post by abid_iut » Thu Dec 18, 2008 11:51 am

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/

Post Reply

Return to “Volume 8 (800-899)”