662 - Fast Food

[hardisck]

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]

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]

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

[chuzpa]

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]

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]

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.

[tanaeem]

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;

}

[Kallol]

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;
}

[bongssi]

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

[pdwd]

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]

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.

[plamplam]

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

[Labib]

Why am I getting WA?? :'(
please help!!

Code: Select all

AC

[brianfry713]

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.

[Labib]

thanks brainfry !!
AC