662 - Fast Food
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
5
6-
12
19
20-
27
But it not always works, and i don
Some cases ...
INPUT :
OUTPUT :
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
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
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??
Re: Can someone explain the output
You are correct. My accepted code returnstanaeem wrote:there is 4 resturents in case 4 but how "Depot 3 at restaurant 3 serves restaurants 4 to 5" is possible??
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
Ami ekhono shopno dekhi...
HomePage
HomePage
Help Me
I am getting WA.
Please help me.
Can someone probvide me some tricky test case.
Or alternatively check my code.
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;
}
I am getting CE ! God knows why !!
my code goes OK with the I/O given above. Here is my code..
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
CSE,BUET
Bangladesh
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?
- 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?
-
- 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
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
Re: 662 - Fast Food
Why am I getting WA?? :'(
please help!!
please help!!
Code: Select all
AC
Last edited by Labib on Fri Mar 08, 2013 1:31 pm, edited 1 time in total.
-
- 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.
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!
Re: 662 - Fast Food
thanks brainfry !!
AC
AC
