OJ Board

Posted: **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

Posted: **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

Posted: **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

Posted: **Thu Feb 01, 2007 2:54 pm**

INPUT :

Code: Select all

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

Posted: **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??

Posted: **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.

Posted: **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;

}

Posted: **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;
}

Posted: **Tue Nov 24, 2009 5:52 am**

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

Posted: **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?

Posted: **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.

Posted: **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

Posted: **Wed Mar 06, 2013 3:54 pm**

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

Code: Select all

AC

Posted: **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.

Posted: **Fri Mar 08, 2013 1:31 pm**

thanks brainfry !!
AC

OJ Board

662 - Fast Food

662 - Fast Food

662 WA

Some cases ...

Can someone explain the output

Re: Can someone explain the output

Help Me

Is it DP?

Re: 662 - Fast Food

Re: 662 - Fast Food

Re: 662 - Fast Food

Re: 662 - Fast Food

Re: 662 - Fast Food

Re: 662 - Fast Food