662 - Fast Food

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

Moderator: Board moderators

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

662 - Fast Food

Post by hardisck » Mon Feb 17, 2003 8:53 pm

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:

Post by hardisck » Tue Feb 25, 2003 4:20 am

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

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

662 WA

Post by gootsa » Sun Mar 26, 2006 7:15 pm

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

Post by chuzpa » Thu Feb 01, 2007 2:54 pm

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

Post by tanaeem » Sun May 27, 2007 10:08 am

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
Location: Dhaka, Bangladesh
Contact:

Re: Can someone explain the output

Post by Jan » Sun May 27, 2007 7:01 pm

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

Post by tanaeem » Mon May 28, 2007 9:45 am

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;

}

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Wed Dec 26, 2007 7:50 pm

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
Bangladesh

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

Is it DP?

Post by bongssi » Tue Nov 24, 2009 5:52 am

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

Post by pdwd » Fri Jul 30, 2010 12:18 am

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

Post by Foodfast04 » Wed Feb 01, 2012 7:06 am

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

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

Re: 662 - Fast Food

Post by plamplam » Fri Feb 22, 2013 8:41 am

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

Post by Labib » Wed Mar 06, 2013 3:54 pm

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.

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

Re: 662 - Fast Food

Post by brianfry713 » Thu Mar 07, 2013 3:36 am

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

Post by Labib » Fri Mar 08, 2013 1:31 pm

thanks brainfry !!
AC :)

Post Reply

Return to “Volume 6 (600-699)”