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

[ferng1021]

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]

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]

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]

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]

My algorithm uses O(n) memory.

[ibroker]

//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[1010], pp[1010];
ll nn[1010], rr[1010];
ll data[1010][1010], track[1010][1010];
ll now_cost[1010], now_where[1010], n_box[1010];

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[1][i] = n_box[i] * now_cost[i] + c;
			ll Min = data[1][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]

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]

My dp is O(n^2), too. But it takes .6 seconds and can be modified. May be your implementation is not efficient enough.

[tanaeem]

After optimizing various ways ( like ignoring smaller but costlier boxes) I have got AC in .12 sec.
But I am still wandering is there any O(nlogn) soln.