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

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

855 - Lunch in Grid City

Post by howardcheng » Thu Nov 27, 2003 12:59 am

I must be braindead. I cannot see why my program gives WA:

#include <stdio.h>
#include <stdlib.h>

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

int main(void)
{
int T, F;
int s[50000], a[50000];
int i;
int meds, meda;

scanf("%d\n", &T);
while (T-- > 0) {
scanf("%*d %*d %d", &F);
for (i = 0; i < F; i++) {
scanf("%d %d", s+i, a+i);
}
qsort(s, F, sizeof(int), cmp);
qsort(a, F, sizeof(int), cmp);
if (F % 2) {
meds = s[F/2];
meda = a[F/2];
} else {
meds = (s[F/2-1]+s[F/2])/2;
meda = (a[F/2-1]+a[F/2])/2;
}
printf("(Street: %d, Avenue: %d)\n", meds, meda);
}
return 0;

}

go
New poster
Posts: 2
Joined: Sun Jul 04, 2004 1:44 pm
Contact:

Pleaseeeee Help Me

Post by go » Tue Sep 28, 2004 5:53 pm

I solved this problem in two ways but every time I got WA.Here is my source,my algorithm is dynamic,at first step I found the total distance from all points to (1,1) and then for every other points ,I find the distance
by the point just before it(it is a distance for last point+number of points in right side of the recent point - number of points left side the recent point) the distance with the recent point and points in it's right side decrease 1,in it's left side increase 1.
[cpp]
#include <iostream>
#include <string>
using namespace std;
#define int long long
int a,b,f,m[1001][1001],r[1001],l[1001],u[1001],d[1001];
int main()
{
int mm;
cin>>mm;
for(int tt=0;tt<mm;tt++)
{
cin>>a>>b>>f;
memset(m,0,sizeof m);
memset(r,0,sizeof r);
memset(l,0,sizeof l);
memset(u,0,sizeof u);
memset(d,0,sizeof d);
int s=0;

for(int i=0;i<f;i++)
{
int x,y;
cin>>x>>y;
m[x-1][y-1]=1;
s+=x-1+y-1;
}
int g[1001];
memset(g,0,sizeof g);
for(int i=0;i<b;i++)
for(int j=0;j<a;j++)
{
g+=m[j];
}
l[0]=0;
for(int i=1;i<b;i++)
{
l=l[i-1]+g[i-1];

}
for(int i=b-1;i>=0;i--)
r+=f-l;
/* for(int i=0;i<b;i++)
cout<<" righ "<<i<<" : "<<r;
cout<<endl;
for(int i=0;i<b;i++)
cout<<" left "<<i<<" : "<<l;
cout<<endl;*/
memset(g,0,sizeof g);
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
{
g+=m[j];
}
u[0]=0;
for(int i=1;i<a;i++)
u+=u[i-1]+g[i-1];
d[a-1]=g[a-1];
for(int i=a-2;i>=0;i--)
d[i]=f-u[i];
int mini=s;
int x=0,y=0;
int dis[1001];
dis[0]=s;
for(int i=1;i<a;i++)
{
dis[i]=dis[i-1]+u[i]-d[i];
}
int dd[1001];
for(int i=0;i<a;i++)
{
dd[0]=dis[i];
if(dis[i]<mini && m[i][0]==1)
{
mini=dis[i];
x=i;
y=0;
}
for(int j=1;j<b;j++)
{
dd[j]=dd[j-1]+l[j]-r[j];
if(dd[j]<mini && m[i][j]==1)
{
mini=dd[j];
x=i;
y=j;
}
}
}

cout<<"(Street: "<<x+1<<", Avenue: "<<y+1<<")"<<endl;

}

return 0;

}

Pleeeeeeeeeese HELP ME
Is there anyone solved this problem with sorting methode(and writhing the middle element of the sorted array)???[/cpp]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Re: Pleaseeeee Help Me

Post by little joey » Tue Sep 28, 2004 6:35 pm

go wrote: Is there anyone solved this problem with sorting methode(and writhing the middle element of the sorted array)???
Yes, that's the way to do it. Basically it's a two dimensional 'Vito's Family' (I just remember the title of the problem, not the number). In the discussion of that problem on the board, there is an excellent explanation (by Whinii F., if I'm correct) why the median method works in these cases.

go
New poster
Posts: 2
Joined: Sun Jul 04, 2004 1:44 pm
Contact:

Post by go » Wed Sep 29, 2004 8:21 am

At last I Accepted this problem, I understood how to write it with sorting. :D

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR » Thu Nov 18, 2004 5:00 pm

So what's wrong with howardchengs's algorithm?

I don't talk about array size, integer type and so on - just the algorithm.

added Nov 22

Perhaps somebody can tell me what's wrong with my program?

Code: Select all

#include <stdio.h>            /* scanf, printf */
#include <stdlib.h>           /* qsort */

/*******************************
 * ACM Contest - Problem 855   *
 * WA           *
 *******************************/

long STREETS[50002];
long AVENUES[50002];

int cmp(const void *ap, const void *bp)
{
  long a = *(long *)ap;
  long b = *(long *)bp;
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}

int main(void)
{
  int nc, cases;
  int ns, streets;
  int na, avenues;
  int nf, friends;
  long medst;
  long medav;
  scanf("%d",&cases);
  for (nc=0;nc<cases;nc++){
    scanf("%d %d %d",&streets,&avenues,&friends);
    for (nf=0;nf<friends;nf++)
      scanf("%ld %ld",&STREETS[nf],&AVENUES[nf]);
    if (friends == 1){
      medst = STREETS[0];
      medav = AVENUES[0];
    }  
    else if (friends == 2){
      medst = (STREETS[0]+STREETS[1])/2;
      medav = (AVENUES[0]+AVENUES[1])/2;
    }
    else{
      qsort(STREETS,friends,sizeof(long),cmp);
      qsort(AVENUES,friends,sizeof(long),cmp);
      if ((friends % 2) == 0){
        medst = (STREETS[friends/2]+STREETS[friends/2-1])/2;
        medav = (AVENUES[friends/2]+AVENUES[friends/2-1])/2;
      }
      else{
        medst = STREETS[friends/2];
        medav = AVENUES[friends/2];
      }
    }
    printf("(Street: %ld, Avenue: %ld)\n",medst,medav);
  }
  return 0;
}

Yaron Wittenstein
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

855 - WA

Post by Yaron Wittenstein » Wed Mar 02, 2005 7:02 pm

Code: Select all

#include <stdio.h>

#define   MAXN   1000

int median(int a[], int n) /* a[i] <= MAX_VAL */
{
  int i, sum, m;

  sum = 0;
  i = 1;
  m = (n % 2 == 0 ? (n / 2 - 1) : n / 2);

  while (sum < m) {
    sum += a[i];
    i++;
  }

  return i;
}

void init(int a[], int n)
{
  int i;
  for(i = 1; i <= n; i++)
    a[i] = 0;
}

int main()
{
  int y[MAXN + 1];
  int x[MAXN + 1];
  int T, A, S, F;
  int median_x, median_y;
  int i;
  int street, avenue;

  scanf("%d", &T);
  for(; T > 0; T--) {
    scanf("%d %d %d", &S, &A, &F);
    init(x, A);
    init(y, S);

    for(i = 0; i < F; i++) {
      scanf("%d %d", &street, &avenue);
      y[street]++;
      x[avenue]++;
    }

    median_x = median(x, F);
    median_y = median(y, F);
    printf("(Street: %d, Avenue: %d)\n", median_y, median_x);
  }

  return 0;
}
please try to help me out here!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Mar 03, 2005 6:28 pm

How does your median work?

You can solve this problem by sorting too, it's fast enough.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Help

Post by Raj Ariyan » Fri Mar 04, 2005 11:32 am

Hi Yaron,

I think your median function does not always give right answer for all cases. You can sort street and avenue and then just print out the median (Simple Median Knowledge n/2 or n/2-1). Bye.
Some Love Stories Live Forever ....

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

Post by Jan » Fri Jun 24, 2005 8:36 pm

I got Accepted after several wrong answers. And finally I found the bug
in my code.
My algorithm is simple....

Code: Select all

    1. First sort the streets.
    2. Sort the avenues.
    3. Suppose they are in an array p[][2],
        p[][0] is the street number, p[][1] is the avenue number
        starting from 1 to n (n is the total number)
    4. If n is odd assign j <- (n+1)/2
    5. Otherwise assign j <- n/2
    6. Print p[j][0] and p[j][1]......
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 » Mon Oct 30, 2006 1:53 pm

i think i'm doing the same thing but still getting wrong answer. here is my sample input and output:

Code: Select all

22 22 6
1 5
1 4
1 3
2 1
3 10
3 9

Code: Select all

(Street: 1, Avenue: 5)

Code: Select all

10 10 1
5 5

Code: Select all

(Street: 5, Avenue: 5)

Code: Select all

2 2 2
1 1
2 2

Code: Select all

(Street: 1, Avenue: 1)

Code: Select all

7 7 11
1 2
1 7
2 2
2 3
2 5
3 4
4 2
4 5
4 6
5 3
6 5

Code: Select all

(Street: 3, Avenue: 4)
is there anything tricky? please help me!
Image

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

Post by Jan » Mon Oct 30, 2006 3:12 pm

The problem is in multiple input format. So, your sets will be like

Input:

Code: Select all

4
22 22 6 
1 5 
1 4 
1 3 
2 1 
3 10 
3 9
10 10 1 
5 5 
2 2 2 
1 1 
2 2
7 7 11 
1 2 
1 7 
2 2 
2 3 
2 5 
3 4 
4 2 
4 5 
4 6 
5 3 
6 5
Output:

Code: Select all

(Street: 1, Avenue: 4)
(Street: 5, Avenue: 5)
(Street: 1, Avenue: 1)
(Street: 3, Avenue: 4)
And your first case is also wrong.
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 » Mon Oct 30, 2006 5:35 pm

i've arranged the multiple input set as u suggested. i used the previous style just to be crystal clear. :D

now, about the first case: my program sorts it like the following:

Code: Select all

1 3
1 4
1 5
2 1
3 9
3 10
why the median shud be (1 4) here?
Image

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

Post by Jan » Mon Oct 30, 2006 6:13 pm

If all the friends meet at (1, 4)

Code: Select all

1 3  => 0 + 1 = 1
1 4  => 0 + 0 = 0
1 5  => 0 + 1 = 1
2 1  => 1 + 3 = 4
3 9  => 2 + 5 = 7
3 10 => 2 + 6 = 8
Total Distance => 21
If all the friends meet at (1, 5)

Code: Select all

1 3  => 0 + 2 = 2
1 4  => 0 + 1 = 1
1 5  => 0 + 0 = 0
2 1  => 1 + 4 = 5
3 9  => 2 + 4 = 6
3 10 => 2 + 5 = 7
Total Distance => 21
So, they both are optimal ones. But the problem states
If there is more than one candidate point, the rule imposes that the meeting point is the one corresponding to the smaller number for street and avenue.
(1, 4) is smaller than (1, 5). So, the output should be (1, 4).
And if you are following my algorithm (as I described before) then I think that you haven't understood it correctly.
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 » Tue Oct 31, 2006 12:20 pm

yeah, u r right. i don't understand ur algorithm and cudn't find any mistake in my algorithm :( to me, both of the algorithms are same. i've corrected the flaw and still getting wrong answer. :(

can anyone give me any tricky input?
Image

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

Post by Jan » Tue Oct 31, 2006 1:39 pm

After sorting you will get

Code: Select all

1 1
1 3
1 4
2 5
3 9
3 10
from the above set. :wink:. And the median is (1, 4). Hope you understand my algorithm.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 8 (800-899)”