## 11252 - Take Me Home (To the Place I Belong)

Moderator: Board moderators

ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan

### 11252 - Take Me Home (To the Place I Belong)

I think it's a DP problem,
but I don't know why I got WAs.

Can some body give me some sample input/output?

Thank you very much!!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I don't think there's any trick. If your dp is correct, you'll probably get AC.
The main idea is that if there is a box i,j where mi<=mj and pi>pj, then box i can be ignored.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
I didn't use sclo's observation directly. I just thought about an O(n^3) implementation and then I found a clever reduction to an O(n^2) solution.

The idea I had originally was is in fact O(n(logn + n)) but I finally implemented it as plain O(n^2).

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm
I use dynamic O(n^3) implementation.

And I also find a reduction to an O(n^2) solution.

But it is WA. Anybody has some data cases?

My simple dynamic fomula is like this.

d[i, j] = d[i-1, k] + C (C is constant, and need calculating)

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
My algorithm uses O(n) memory.

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm
//jah thanks. I got ACC using O(n) memory. but It is confuse why my O(n^2) memory dynamic got WA. Code: Select all

``````#include <cstdio>
#include <algorithm>
using namespace std;

#define ll long long int

ll c;
int n, m;
ll mm, pp;
ll nn, rr;
ll data, track;
ll now_cost, now_where, n_box;

int main()
{
int i,j;
int loop = 0;

while(scanf("%lld", &c)==1)
{
scanf("%d %d", &m, &n);
if(c==0 && m==0 && n==0) break;
for(i=1; i<=m; i++)
{
scanf("%lld %lld", &mm[i], &pp[i]);
}
for(i=1; i<=n; i++)
{
scanf("%lld %lld", &nn[i], &rr[i]);
}
for(i=1; i<=m; i++) // sorting
{
for(j=i+1; j<=m; j++)
{
if(mm[i]<mm[j])
{
swap(mm[i], mm[j]);
swap(pp[i], pp[j]);
}
else if(mm[i]==mm[j] && pp[i]>pp[j])
{
swap(pp[i], pp[j]);
}
}
}
for(i=1; i<=n; i++) // sorting
{
for(j=i+1; j<=n; j++)
{
if(nn[i]>nn[j])
{
swap(nn[i], nn[j]);
swap(rr[i], rr[j]);
}
}
}
bool did;
for(i=1; i<=n; i++)
{
did = false;
for(j=1; j<=m; j++)
{
if(nn[i]<=mm[j])
{
if(now_cost[i]==0 || now_cost[i]>pp[j])
{
now_cost[i] = pp[j];
now_where[i] = j;
did = true;
}
}
}
if(did==false) break;
n_box[i] = n_box[i-1] + rr[i];
}
printf("case %d: ", ++loop);
if(did==false) printf("not possible\n");
else
{
for(i=1; i<=n; i++) data[i] = n_box[i] * now_cost[i] + c;
ll Min = data[n];
for(i=2; i<=n; i++)
{
if(i>n) break;
data[i][i] = data[i-1][i-1] + (n_box[i] - n_box[i-1]) * now_cost[i];
track[i][i] = i-1;
if(now_where[i]!=now_where[i-1]) data[i][i] += c;
for(j=i+1; j<=n; j++)
{
track[i][j] = track[i][j-1];
ll cc = 0;
if(now_where[track[i][j]]!=now_where[j]) cc = c;
data[i][j] = data[i-1][track[i][j]] + (n_box[j] - n_box[track[i][j]]) * now_cost[j] + cc;
cc = 0;
if(now_where[j-1]!=now_where[j]) cc = c;
if(data[i][j] > data[i-1][j-1] + (n_box[j] - n_box[j-1]) * now_cost[j] + cc)
{
data[i][j] = data[i-1][j-1] + (n_box[j] - n_box[j-1]) * now_cost[j] + cc;
track[i][j] = j-1;
}
}
if(Min>data[i][n])
Min = data[i][n];
}
printf("%lld\n", Min);
}
for(i=0; i<=m; i++)
{
for(j=0; j<=n; j++)
{
data[i][j] = track[i][j] = 0;
n_box[j] = now_cost[j] = now_where[j] = 0;
}
}
}

return 0;
}
``````
It is O(n^2) memory and O(n^2) time complexity.[/code]

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

### I have done using O(n^2) dp

I have done O(n^2) dp but it took 4.973 sec.
But in ranklist I have seen someone solved it within 0.082 sec.
Is there any O(n) soln? or greedy soln?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm