## 662 - Fast Food

Moderator: Board moderators

hardisck
New poster
Posts: 2
Joined: Mon Feb 17, 2003 8:38 pm
Location: Mexico
Contact:

### 662 - Fast Food

I tried it spliting the arrange in 2, looking for the medium (n/2), for example:

5
6-
12
19
20-
27

But it not always works, and i don

hardisck
New poster
Posts: 2
Joined: Mon Feb 17, 2003 8:38 pm
Location: Mexico
Contact:
I solved it, thank you anyways.

The solution for some who wants help is

You have to do a matrix with the distance and then seek for the low cost, like this:

restaurants 1 2 3 4 5
1 0 1 2 3 4
2 1 0 1 2 3
3 2 1 0 1 2
4 3 2 1 0 1
5 4 3 2 1 0

gootsa
New poster
Posts: 9
Joined: Sat Jun 25, 2005 9:26 am

### 662 WA

I used dynamic for solving this problem, but I got WA,
can you give me some input output

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

### Some cases ...

INPUT :

Code: Select all

``````6 3
5
6
12
19
20
27

1 1
1

2 1
0
10000
4 3
1
2
3
4

3 3
1
2
3

5 2
1
2
3
4
5

5 2
-5
-4
-3
-2
-1

5 1
1
2
3
4
5
0 0
``````
OUTPUT :

Code: Select all

``````Chain 1
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 4 serves restaurants 5 to 6
Depot 3 at restaurant 6 serves restaurant 6
Total distance sum = 8

Chain 2
Depot 1 at restaurant 1 serves restaurant 1
Total distance sum = 0

Chain 3
Depot 1 at restaurant 1 serves restaurants 2 to 3
Total distance sum = 10000

Chain 4
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 2 serves restaurant 2
Depot 3 at restaurant 3 serves restaurants 4 to 5
Total distance sum = 1

Chain 5
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 2 serves restaurant 2
Depot 3 at restaurant 3 serves restaurant 3
Total distance sum = 0

Chain 6
Depot 1 at restaurant 1 serves restaurants 2 to 3
Depot 2 at restaurant 4 serves restaurants 3 to 5
Total distance sum = 3

Chain 7
Depot 1 at restaurant 1 serves restaurants 2 to 3
Depot 2 at restaurant 4 serves restaurants 3 to 5
Total distance sum = 3

Chain 8
Depot 1 at restaurant 3 serves restaurants 1 to 5
Total distance sum = 6

``````

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

### Can someone explain the output

I may have some problem in understanding this problem, can someone explain case 3 and 4 of the output in previous post. there is 4 resturents in case 4 but how "Depot 3 at restaurant 3 serves restaurants 4 to 5" is possible??

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

### Re: Can someone explain the output

tanaeem wrote:there is 4 resturents in case 4 but how "Depot 3 at restaurant 3 serves restaurants 4 to 5" is possible??
You are correct. My accepted code returns

Output:

Code: Select all

``````Chain 1
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 5 serves restaurants 4 to 5
Depot 3 at restaurant 6 serves restaurant 6
Total distance sum = 8

Chain 2
Depot 1 at restaurant 1 serves restaurant 1
Total distance sum = 0

Chain 3
Depot 1 at restaurant 1 serves restaurants 1 to 2
Total distance sum = 10000

Chain 4
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 2 serves restaurant 2
Depot 3 at restaurant 3 serves restaurants 3 to 4
Total distance sum = 1

Chain 5
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 2 serves restaurant 2
Depot 3 at restaurant 3 serves restaurant 3
Total distance sum = 0

Chain 6
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 4 serves restaurants 4 to 5
Total distance sum = 3

Chain 7
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 4 serves restaurants 4 to 5
Total distance sum = 3

Chain 8
Depot 1 at restaurant 3 serves restaurants 1 to 5
Total distance sum = 6``````
Some outputs are wrong posted by chuzpa.
Ami ekhono shopno dekhi...
HomePage

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

### Help Me

I am getting WA.
Can someone probvide me some tricky test case.
Or alternatively check my code.

Code: Select all

``````#include<stdio.h>

int abs(int a)
{
return a>0 ? a:-a;
}

int d;
int cache[250][35];
int where[250][35];
char what[250][35];
int pos[250];
int minimize(int n,int k)
{

if(n==0)
return 0;
if(k==0)
return -1;
if(cache[n][k]!=-2)
return cache[n][k];

int j;

cache[n][k]=-1;
int res=0;
int val=0;

for(j=n-1;j>=0;j--)
{
res+=abs(pos[j]-pos[(j+n)/2]);

if(minimize(j,k-1)!=-1)
{

if(cache[n][k]==-1)
{

cache[n][k]=res+minimize(j,k-1);
where[n][k]=(j+n-1)/2;
what[n][k]=j;
}
else if(cache[n][k]>(res+minimize(j,k-1)))
{
cache[n][k]=res+minimize(j,k-1);
where[n][k]=(j+n-1)/2;
what[n][k]=j;
}
}

}

return cache[n][k];
}
void init()
{
int i,j;
for(i=0;i<245;i++)
for(j=0;j<33;j++)
cache[i][j]=-2;

}

void track(int n,int k)
{

if(n==0||k==0)
return;

int p=where[n][k];

int q=what[n][k];

track(q,k-1);
d++;

printf("Depot %d at restaurant %d serves ",d,p+1);

if(q==(n-1))
printf("restaurant %d\n",q+1);
else
printf("restaurants %d to %d\n",q+1,n);

}
int main()
{
int n,k,i,val;
int t=0;

scanf("%d%d",&n,&k);
while(n||k)
{
t++;

for(i=0;i<n;i++)
scanf("%d",&pos[i]);

init();

val=minimize(n,k);
d=0;

printf("Chain %d\n",t);
track(n,k);
printf("Total distance sum = %d\n",val);
putchar('\n');
scanf("%d%d",&n,&k);

}

return 0;

}``````

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
I am getting CE ! God knows why !!

my code goes OK with the I/O given above. Here is my code..

Code: Select all

``````#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>

using namespace std;

#define SIZE 205
#define INF 99999999

int D[SIZE];
int memo[SIZE][SIZE][35];
int dis[SIZE][SIZE];
int sc[SIZE][SIZE];
int brk[SIZE][SIZE];
int N,K;

int disf(int start,int end)
{
int i,j,sum,p,minx;
if(dis[start][end]!=-1)
{
return dis[start][end];
}

minx=INF;
for(i=start;i<=end;i++)
{
sum=0;
for(j=start;j<=end;j++)
{
sum+=abs(D[i]-D[j]);
}

if(sum<minx)
{
minx=sum;
p=i;
}
}

sc[start][end]=p;
dis[start][end]=minx;
return minx;
}

int countdis(int start,int end,int k)
{
int i,x,minx;

if((end-start+1)<k)
return INF;

if(memo[start][end][k]!=-1)
return memo[start][end][k];

if(k==1)
{
brk[start][end]=end;
return disf(start,end);
}

minx=INF;
for(i=start;i<end;i++)
{
x=disf(start,i)+countdis(i+1,end,k-1);
if(x<minx)
{
minx=x;
brk[start][end]=i;
}
}

memo[start][end][k]=minx;
return minx;

}

int main(void)
{
int ch=0,i,d,p,j,k,q;
while(true)
{
scanf("%d%d",&N,&K);
if(N==0 && K==0)break;
ch++;
for(i=0;i<N;i++)
{
scanf("%d",&D[i]);
}
//initialization
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
for(k=0;k<=K;k++)
memo[i][j][k]=-1;
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
dis[i][j]=-1;

//dp call
d=countdis(0,N-1,K);

//output
printf("Chain %d\n",ch);
p=0;
q=N-1;
for(i=1;i<=K;i++)
{
if(p!=brk[p][q])
{
printf("Depot %d at restaurant %d serves restaurants %d to %d\n",i,sc[p][brk[p][q]]+1,p+1,brk[p][q]+1);
}
else
{
printf("Depot %d at restaurant %d serves restaurant %d\n",i,sc[p][brk[p][q]]+1,p+1);
}

p=brk[p][q]+1;
}
printf("Total distance sum = %d\n",d);
printf("\n");
}
return 0;
}

``````
Syed Ishtiaque Ahmed Kallol
CSE,BUET

bongssi
New poster
Posts: 14
Joined: Mon Jul 31, 2006 10:35 am

### Is it DP?

I tried to find the recurrence equation but I failed... plz explain the algorithm for it...

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

### Re: 662 - Fast Food

Try to guess the space of subproblems. Some hints:
- I have dp[j], where i - number of restaurant, j - amount of depots I want to install
- Time complexity is O(n^2*k), does anyone have a better solution?

Foodfast04
New poster
Posts: 1
Joined: Fri Jan 27, 2012 8:02 am

### Re: 662 - Fast Food

brother your problem is solved which is very good and now I would like to inform you that your written post helped me a lot. I was in trouble but now I'm clear.
I'm John and this is my blog alegria shoe shop

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 662 - Fast Food

Input:

Code: Select all

``````15 3
2 3 6 16 36 39 42 44 64 66 79 80 87 93 95

15 2
8 16 19 33 38 45 56 62 71 76 80 84 90 92 93

15 10
1 27 31 42 46 48 56 59 61 62 73 74 79 85 98

15 7
4 6 12 17 31 34 39 43 49 61 65 73 85 93 95

15 8
7 12 19 22 24 28 35 38 41 50 53 65 76 78 80

15 12
2 7 10 12 15 34 37 66 76 81 87 93 94 96 99

15 9
1 9 10 38 40 41 48 49 55 62 65 68 81 82 85

15 8
21 22 27 44 50 51 53 60 62 68 80 86 91 95 96

15 2
3 25 30 38 43 58 61 65 66 67 84 85 86 93 97

15 7
10 18 26 44 46 56 61 63 66 73 74 77 79 83 95

15 3
5 6 14 17 21 25 44 56 62 69 78 80 90 93 97

15 8
8 17 23 24 26 27 40 44 46 58 61 66 71 74 77

15 3
16 23 26 34 35 37 45 50 53 79 81 84 90 91 96

15 4
15 18 37 40 41 51 57 75 77 83 88 92 93 97 99

15 9
11 14 19 25 37 45 54 56 65 77 79 84 85 92 94

0 0
``````

Code: Select all

``````Chain 1
Depot 1 at restaurant 3 serves restaurants 1 to 4
Depot 2 at restaurant 7 serves restaurants 5 to 8
Depot 3 at restaurant 12 serves restaurants 9 to 15
Total distance sum = 94

Chain 2
Depot 1 at restaurant 4 serves restaurants 1 to 7
Depot 2 at restaurant 12 serves restaurants 8 to 15
Total distance sum = 166

Chain 3
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 3 serves restaurants 2 to 3
Depot 3 at restaurant 4 serves restaurant 4
Depot 4 at restaurant 6 serves restaurants 5 to 6
Depot 5 at restaurant 7 serves restaurant 7
Depot 6 at restaurant 9 serves restaurants 8 to 10
Depot 7 at restaurant 12 serves restaurants 11 to 12
Depot 8 at restaurant 13 serves restaurant 13
Depot 9 at restaurant 14 serves restaurant 14
Depot 10 at restaurant 15 serves restaurant 15
Total distance sum = 10

Chain 4
Depot 1 at restaurant 2 serves restaurants 1 to 2
Depot 2 at restaurant 4 serves restaurants 3 to 4
Depot 3 at restaurant 6 serves restaurants 5 to 6
Depot 4 at restaurant 8 serves restaurants 7 to 9
Depot 5 at restaurant 11 serves restaurants 10 to 12
Depot 6 at restaurant 13 serves restaurant 13
Depot 7 at restaurant 15 serves restaurants 14 to 15
Total distance sum = 34

Chain 5
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 2 serves restaurant 2
Depot 3 at restaurant 4 serves restaurants 3 to 5
Depot 4 at restaurant 6 serves restaurant 6
Depot 5 at restaurant 8 serves restaurants 7 to 9
Depot 6 at restaurant 11 serves restaurants 10 to 11
Depot 7 at restaurant 12 serves restaurant 12
Depot 8 at restaurant 14 serves restaurants 13 to 15
Total distance sum = 18

Chain 6
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 2 serves restaurant 2
Depot 3 at restaurant 4 serves restaurants 3 to 4
Depot 4 at restaurant 5 serves restaurant 5
Depot 5 at restaurant 6 serves restaurant 6
Depot 6 at restaurant 7 serves restaurant 7
Depot 7 at restaurant 8 serves restaurant 8
Depot 8 at restaurant 9 serves restaurant 9
Depot 9 at restaurant 10 serves restaurant 10
Depot 10 at restaurant 11 serves restaurant 11
Depot 11 at restaurant 13 serves restaurants 12 to 14
Depot 12 at restaurant 15 serves restaurant 15
Total distance sum = 5

Chain 7
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 3 serves restaurants 2 to 3
Depot 3 at restaurant 5 serves restaurants 4 to 6
Depot 4 at restaurant 8 serves restaurants 7 to 8
Depot 5 at restaurant 9 serves restaurant 9
Depot 6 at restaurant 11 serves restaurants 10 to 11
Depot 7 at restaurant 12 serves restaurant 12
Depot 8 at restaurant 14 serves restaurants 13 to 14
Depot 9 at restaurant 15 serves restaurant 15
Total distance sum = 9

Chain 8
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 4 serves restaurant 4
Depot 3 at restaurant 6 serves restaurants 5 to 7
Depot 4 at restaurant 9 serves restaurants 8 to 9
Depot 5 at restaurant 10 serves restaurant 10
Depot 6 at restaurant 11 serves restaurant 11
Depot 7 at restaurant 12 serves restaurant 12
Depot 8 at restaurant 14 serves restaurants 13 to 15
Total distance sum = 16

Chain 9
Depot 1 at restaurant 3 serves restaurants 1 to 5
Depot 2 at restaurant 11 serves restaurants 6 to 15
Total distance sum = 181

Chain 10
Depot 1 at restaurant 2 serves restaurants 1 to 2
Depot 2 at restaurant 3 serves restaurant 3
Depot 3 at restaurant 5 serves restaurants 4 to 5
Depot 4 at restaurant 8 serves restaurants 6 to 9
Depot 5 at restaurant 11 serves restaurants 10 to 11
Depot 6 at restaurant 13 serves restaurants 12 to 14
Depot 7 at restaurant 15 serves restaurant 15
Total distance sum = 29

Chain 11
Depot 1 at restaurant 4 serves restaurants 1 to 6
Depot 2 at restaurant 9 serves restaurants 7 to 10
Depot 3 at restaurant 13 serves restaurants 11 to 15
Total distance sum = 101

Chain 12
Depot 1 at restaurant 1 serves restaurant 1
Depot 2 at restaurant 2 serves restaurant 2
Depot 3 at restaurant 5 serves restaurants 3 to 6
Depot 4 at restaurant 7 serves restaurant 7
Depot 5 at restaurant 9 serves restaurants 8 to 9
Depot 6 at restaurant 11 serves restaurants 10 to 11
Depot 7 at restaurant 12 serves restaurant 12
Depot 8 at restaurant 14 serves restaurants 13 to 15
Total distance sum = 17

Chain 13
Depot 1 at restaurant 4 serves restaurants 1 to 6
Depot 2 at restaurant 8 serves restaurants 7 to 9
Depot 3 at restaurant 13 serves restaurants 10 to 15
Total distance sum = 82

Chain 14
Depot 1 at restaurant 2 serves restaurants 1 to 2
Depot 2 at restaurant 5 serves restaurants 3 to 7
Depot 3 at restaurant 9 serves restaurants 8 to 10
Depot 4 at restaurant 13 serves restaurants 11 to 15
Total distance sum = 58

Chain 15
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 4 serves restaurant 4
Depot 3 at restaurant 5 serves restaurant 5
Depot 4 at restaurant 6 serves restaurant 6
Depot 5 at restaurant 8 serves restaurants 7 to 8
Depot 6 at restaurant 9 serves restaurant 9
Depot 7 at restaurant 11 serves restaurants 10 to 11
Depot 8 at restaurant 13 serves restaurants 12 to 13
Depot 9 at restaurant 15 serves restaurants 14 to 15
Total distance sum = 15
``````
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Labib
New poster
Posts: 12
Joined: Tue Mar 05, 2013 4:49 pm

### Re: 662 - Fast Food

Why am I getting WA?? :'(

Code: Select all

``````AC
``````
Last edited by Labib on Fri Mar 08, 2013 1:31 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 662 - Fast Food

Your code is wrong for the sample I/O.
You're printing Depot 1 at restaurant 3 serves restaurants 1 to 3, which has a sum of 7+6+0=13.
Check input and AC output for thousands of problems on uDebug!

Labib
New poster
Posts: 12
Joined: Tue Mar 05, 2013 4:49 pm

### Re: 662 - Fast Food

thanks brainfry !!
AC