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
x1a + x2a + ... + xna <= x1b + x2b + ... + xnb
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
x1ax + x2ax + ... + xnax <= x1bx + x2bx + ... + xnbx
and
y1ay + y2ay + ... + ynay <= y1by + y2by + ... + ynby
Adding them both we obtain
x1ax + x2ax + ... + xnax + y1ay + y2ay + ... + ynay <=
x1bx + x2bx + ... + xnbx + y1by + y2by + ... + ynby
And we can rewrite
(x1ax+y1ay) + (x2ax+y2ay) + ... + (xnax+ynay) <=
(x1bx+y1by) + (x2bx+y2by) + ... + (xnbx+ynby)
Ami ekhono shopno dekhi...
HomePage
HomePage
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.
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...

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, 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 @@@
@@@ Jony @@@

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, 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/21], ave[f/21]);
else printf("(Street: %ld, Avenue: %ld)\n", str[f/2+1], ave[f/2+1]);
sapnil
"Dream Is The Key To Success"
@@@ Jony @@@
@@@ 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/21], ave[f/21]); 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.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
http://akanoi.webs.com/
Re: 855  Lunch in Grid City
sort(s, s+f) sorts elements s[0], s[1], ..., s[f1]. 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??
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
http://akanoi.webs.com/
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??
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
http://akanoi.webs.com/