## 662 - Fast Food

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

Moderator: Board moderators

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

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
hardisck
New poster

Posts: 2
Joined: Mon Feb 17, 2003 8:38 pm
Location: Mexico

### 662 WA

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

Posts: 9
Joined: Sat Jun 25, 2005 9:26 am

### Some cases ...

INPUT :
Code: Select all
`6 356121920271 112 10100004 312343 31235 2123455 2-5-4-3-2-15 1123450 0`

OUTPUT :
Code: Select all
`Chain 1Depot 1 at restaurant 2 serves restaurants 1 to 3Depot 2 at restaurant 4 serves restaurants 5 to 6Depot 3 at restaurant 6 serves restaurant 6Total distance sum = 8Chain 2Depot 1 at restaurant 1 serves restaurant 1Total distance sum = 0Chain 3Depot 1 at restaurant 1 serves restaurants 2 to 3Total distance sum = 10000Chain 4Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 2 serves restaurant 2Depot 3 at restaurant 3 serves restaurants 4 to 5Total distance sum = 1Chain 5Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 2 serves restaurant 2Depot 3 at restaurant 3 serves restaurant 3Total distance sum = 0Chain 6Depot 1 at restaurant 1 serves restaurants 2 to 3Depot 2 at restaurant 4 serves restaurants 3 to 5Total distance sum = 3Chain 7Depot 1 at restaurant 1 serves restaurants 2 to 3Depot 2 at restaurant 4 serves restaurants 3 to 5Total distance sum = 3Chain 8Depot 1 at restaurant 3 serves restaurants 1 to 5Total distance sum = 6`
chuzpa
New poster

Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico

### 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??
tanaeem
New poster

Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET

### 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 1Depot 1 at restaurant 2 serves restaurants 1 to 3Depot 2 at restaurant 5 serves restaurants 4 to 5Depot 3 at restaurant 6 serves restaurant 6Total distance sum = 8Chain 2Depot 1 at restaurant 1 serves restaurant 1Total distance sum = 0Chain 3Depot 1 at restaurant 1 serves restaurants 1 to 2Total distance sum = 10000Chain 4Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 2 serves restaurant 2Depot 3 at restaurant 3 serves restaurants 3 to 4Total distance sum = 1Chain 5Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 2 serves restaurant 2Depot 3 at restaurant 3 serves restaurant 3Total distance sum = 0Chain 6Depot 1 at restaurant 2 serves restaurants 1 to 3Depot 2 at restaurant 4 serves restaurants 4 to 5Total distance sum = 3Chain 7Depot 1 at restaurant 2 serves restaurants 1 to 3Depot 2 at restaurant 4 serves restaurants 4 to 5Total distance sum = 3Chain 8Depot 1 at restaurant 3 serves restaurants 1 to 5Total distance sum = 6`

Some outputs are wrong posted by chuzpa.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

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

### Help Me

I am getting WA.
Please help me.
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;}`
tanaeem
New poster

Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET

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 99999999int 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
Bangladesh

Kallol
Learning poster

Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

### Is it DP?

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

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

### Re: 662 - Fast Food

Try to guess the space of subproblems. Some hints:
- I have dp[i][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?
pdwd
New poster

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

### 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
Foodfast04
New poster

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

### Re: 662 - Fast Food

Input:

Code: Select all
`15 32 3 6 16 36 39 42 44 64 66 79 80 87 93 9515 28 16 19 33 38 45 56 62 71 76 80 84 90 92 9315 101 27 31 42 46 48 56 59 61 62 73 74 79 85 9815 74 6 12 17 31 34 39 43 49 61 65 73 85 93 9515 87 12 19 22 24 28 35 38 41 50 53 65 76 78 8015 122 7 10 12 15 34 37 66 76 81 87 93 94 96 9915 91 9 10 38 40 41 48 49 55 62 65 68 81 82 8515 821 22 27 44 50 51 53 60 62 68 80 86 91 95 9615 23 25 30 38 43 58 61 65 66 67 84 85 86 93 9715 710 18 26 44 46 56 61 63 66 73 74 77 79 83 9515 35 6 14 17 21 25 44 56 62 69 78 80 90 93 9715 88 17 23 24 26 27 40 44 46 58 61 66 71 74 7715 316 23 26 34 35 37 45 50 53 79 81 84 90 91 9615 415 18 37 40 41 51 57 75 77 83 88 92 93 97 9915 911 14 19 25 37 45 54 56 65 77 79 84 85 92 940 0`

Code: Select all
`Chain 1Depot 1 at restaurant 3 serves restaurants 1 to 4Depot 2 at restaurant 7 serves restaurants 5 to 8Depot 3 at restaurant 12 serves restaurants 9 to 15Total distance sum = 94Chain 2Depot 1 at restaurant 4 serves restaurants 1 to 7Depot 2 at restaurant 12 serves restaurants 8 to 15Total distance sum = 166Chain 3Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 3 serves restaurants 2 to 3Depot 3 at restaurant 4 serves restaurant 4Depot 4 at restaurant 6 serves restaurants 5 to 6Depot 5 at restaurant 7 serves restaurant 7Depot 6 at restaurant 9 serves restaurants 8 to 10Depot 7 at restaurant 12 serves restaurants 11 to 12Depot 8 at restaurant 13 serves restaurant 13Depot 9 at restaurant 14 serves restaurant 14Depot 10 at restaurant 15 serves restaurant 15Total distance sum = 10Chain 4Depot 1 at restaurant 2 serves restaurants 1 to 2Depot 2 at restaurant 4 serves restaurants 3 to 4Depot 3 at restaurant 6 serves restaurants 5 to 6Depot 4 at restaurant 8 serves restaurants 7 to 9Depot 5 at restaurant 11 serves restaurants 10 to 12Depot 6 at restaurant 13 serves restaurant 13Depot 7 at restaurant 15 serves restaurants 14 to 15Total distance sum = 34Chain 5Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 2 serves restaurant 2Depot 3 at restaurant 4 serves restaurants 3 to 5Depot 4 at restaurant 6 serves restaurant 6Depot 5 at restaurant 8 serves restaurants 7 to 9Depot 6 at restaurant 11 serves restaurants 10 to 11Depot 7 at restaurant 12 serves restaurant 12Depot 8 at restaurant 14 serves restaurants 13 to 15Total distance sum = 18Chain 6Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 2 serves restaurant 2Depot 3 at restaurant 4 serves restaurants 3 to 4Depot 4 at restaurant 5 serves restaurant 5Depot 5 at restaurant 6 serves restaurant 6Depot 6 at restaurant 7 serves restaurant 7Depot 7 at restaurant 8 serves restaurant 8Depot 8 at restaurant 9 serves restaurant 9Depot 9 at restaurant 10 serves restaurant 10Depot 10 at restaurant 11 serves restaurant 11Depot 11 at restaurant 13 serves restaurants 12 to 14Depot 12 at restaurant 15 serves restaurant 15Total distance sum = 5Chain 7Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 3 serves restaurants 2 to 3Depot 3 at restaurant 5 serves restaurants 4 to 6Depot 4 at restaurant 8 serves restaurants 7 to 8Depot 5 at restaurant 9 serves restaurant 9Depot 6 at restaurant 11 serves restaurants 10 to 11Depot 7 at restaurant 12 serves restaurant 12Depot 8 at restaurant 14 serves restaurants 13 to 14Depot 9 at restaurant 15 serves restaurant 15Total distance sum = 9Chain 8Depot 1 at restaurant 2 serves restaurants 1 to 3Depot 2 at restaurant 4 serves restaurant 4Depot 3 at restaurant 6 serves restaurants 5 to 7Depot 4 at restaurant 9 serves restaurants 8 to 9Depot 5 at restaurant 10 serves restaurant 10Depot 6 at restaurant 11 serves restaurant 11Depot 7 at restaurant 12 serves restaurant 12Depot 8 at restaurant 14 serves restaurants 13 to 15Total distance sum = 16Chain 9Depot 1 at restaurant 3 serves restaurants 1 to 5Depot 2 at restaurant 11 serves restaurants 6 to 15Total distance sum = 181Chain 10Depot 1 at restaurant 2 serves restaurants 1 to 2Depot 2 at restaurant 3 serves restaurant 3Depot 3 at restaurant 5 serves restaurants 4 to 5Depot 4 at restaurant 8 serves restaurants 6 to 9Depot 5 at restaurant 11 serves restaurants 10 to 11Depot 6 at restaurant 13 serves restaurants 12 to 14Depot 7 at restaurant 15 serves restaurant 15Total distance sum = 29Chain 11Depot 1 at restaurant 4 serves restaurants 1 to 6Depot 2 at restaurant 9 serves restaurants 7 to 10Depot 3 at restaurant 13 serves restaurants 11 to 15Total distance sum = 101Chain 12Depot 1 at restaurant 1 serves restaurant 1Depot 2 at restaurant 2 serves restaurant 2Depot 3 at restaurant 5 serves restaurants 3 to 6Depot 4 at restaurant 7 serves restaurant 7Depot 5 at restaurant 9 serves restaurants 8 to 9Depot 6 at restaurant 11 serves restaurants 10 to 11Depot 7 at restaurant 12 serves restaurant 12Depot 8 at restaurant 14 serves restaurants 13 to 15Total distance sum = 17Chain 13Depot 1 at restaurant 4 serves restaurants 1 to 6Depot 2 at restaurant 8 serves restaurants 7 to 9Depot 3 at restaurant 13 serves restaurants 10 to 15Total distance sum = 82Chain 14Depot 1 at restaurant 2 serves restaurants 1 to 2Depot 2 at restaurant 5 serves restaurants 3 to 7Depot 3 at restaurant 9 serves restaurants 8 to 10Depot 4 at restaurant 13 serves restaurants 11 to 15Total distance sum = 58Chain 15Depot 1 at restaurant 2 serves restaurants 1 to 3Depot 2 at restaurant 4 serves restaurant 4Depot 3 at restaurant 5 serves restaurant 5Depot 4 at restaurant 6 serves restaurant 6Depot 5 at restaurant 8 serves restaurants 7 to 8Depot 6 at restaurant 9 serves restaurant 9Depot 7 at restaurant 11 serves restaurants 10 to 11Depot 8 at restaurant 13 serves restaurants 12 to 13Depot 9 at restaurant 15 serves restaurants 14 to 15Total distance sum = 15`
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster

Posts: 151
Joined: Fri May 06, 2011 11:37 am

### Re: 662 - Fast Food

Why am I getting WA?? :'(
please help!!
Code: Select all
`AC`
Last edited by Labib on Fri Mar 08, 2013 1:31 pm, edited 1 time in total.
Labib
New poster

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

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

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

### Re: 662 - Fast Food

thanks brainfry !!
AC
Labib
New poster

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

Return to Volume VI

### Who is online

Users browsing this forum: No registered users and 1 guest