10448 - Unique World

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

10448 - Unique World

Post by Larry » Tue Feb 25, 2003 12:15 pm

What's the approach to this problem? I tried a simple BFS, but it times out..

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Tue Feb 25, 2003 1:22 pm

Hi!

I solved this task...
it quite tricky and BFS is really too slow..

You have to do 2 things :

1. Find the minimum distance beetween these 2 points and which edges the shortest path contains..
2. Here you have to use dynammic programming ;-) to count the minimum number of those edges whose lengths + the lenght of that path is equal to the cost we look for..

Did you understand it or not ?? :D

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Feb 25, 2003 3:35 pm

I see you're reducing it to the knapsack problem, but I don't get this part:

to count the minimum number of those edges whose lengths

Maybe you can give a little more on that? I think I see it, but not really.. =) Thanks!

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Tue Feb 25, 2003 5:09 pm

So now we have this problem reduced to such a problem:

we have a path with consists of edges... We have to get from the first vertex to the last one. It will cost us n kilometres. So if we have to travel m kilometres then we have to do something with those m-n kilometres...

So we do this like this:

Let presume that our path is 1->2->3->4->5.
So if you want to have a longer path you have to go throught some edges more then one, but always an odd number of times. And that's the idea. So in the value of n, each edge is counted once. So now you have to "create" the value m-n using as less edges as possible, but remember that each one must be used now even number of times (maybe 0).
And there you have a knapsack problem ;-)

I hope that you understood :-)

Good Luck :wink:

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm

Post by Tomson » Thu May 01, 2003 10:35 am

who can give me some test cases about this problem.
I always got WA, but I don't know why.
:cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry:

Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm

Post by Tomson » Thu May 01, 2003 1:21 pm

for this test case:

Code: Select all

1
2 1
1 2 1
1
1 1 2
should output "No" or "Yes" ??

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Sun Jun 15, 2003 7:13 pm

can anybody explain little more about this problem. im not clear about what cyfra had written.
Rakeb

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Mon Aug 25, 2003 6:59 am

Tomson wrote:for this test case:

Code: Select all

1
2 1
1 2 1
1
1 1 2
should output "No" or "Yes" ??
It should be "No"
because you must repeat the last road on the path if you want to go out and return to the same node,
which does not satisfy the problem's requirement.

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10448 - Unique World

Post by red_apricot » Sun Aug 30, 2015 12:12 pm

OK, any help on how to convert the below TLE to AC is appreciated...

Code: Select all

/*
 * 10448. Unique World
 * TOPIC: dp
 * status: 
 */
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
using namespace std;
#define N 0x40
#define oo 0xfffffffful
#define M (100100)
#define bubble (swap(pos[heap[i]],pos[heap[j]]),swap(heap[i],heap[j]))

queue<int> q;
bool precalc[N][N];
int n,m,g[N][N],p[N][N],heap[M],pos[M/2],cn;
vector<pair<int,int> > adj[N],v[N][N];
unsigned int d[N][N],z[M/2],dp[N][M/2];

void push( int x ) {
	int i,j;
	if ( pos[x] < 0 )
		pos[heap[cn]=x]=cn, ++cn;
	for ( j = pos[x]; j && z[heap[i=(j-1)>>1]] > z[heap[j]]; bubble, j = i );
}

int pop() {
	int x = *heap,i,j;
	if ( (pos[x]=-1,--cn) )
		pos[heap[0]=heap[cn]] = 0;
	for ( j = 0; (i=j,j<<=1,++j) < cn; bubble ) {
		if ( j < cn-1 && z[heap[j+1]] < z[heap[j]] ) ++j;
		if ( z[heap[i]] <= z[heap[j]] ) break ;
	}
	return x;
}

void dump( int src, int dst, int x ) {
	if ( x == src ) 
		return ;
	assert( p[src][x] != -1 );
	dump(src,dst,p[src][x]);
	assert( g[p[src][x]][x] < (1<<29) );
	v[src][dst].push_back(make_pair(x,g[p[src][x]][x]));
}

bool f( int src, int dst, int diff, int *res ) {
	vector<int> c;
	set<pair<unsigned int,int> > s;
	set<pair<unsigned int,int> >::iterator it;
	int i,j,k,t,total = 0;
	unsigned int w = +oo;
	if ( diff&1 ) {
		return false;
	}
	diff >>= 1;

	for ( i = 0; i <= n; ++i )
		for ( k = 0; k <= diff; ++k )
			dp[i][k] = +oo;
	set<int> e,h[2];
	set<int> :: iterator jt,l[2];
	e.clear();
	for ( c.clear(), cn = 0, i = 0; i+1 < (int)v[src][dst].size(); ++i )
		e.insert(v[src][dst][i].second);
	for ( c.clear(), jt = e.begin(); jt != e.end(); ++jt )
		c.push_back(*jt);

	n = c.size();
	for ( dp[0][0] = 0, i = 0; i <= n; ++i )
		for ( k = 0; k <= diff; ++k )
			dp[i][k] = +oo;
	for ( dp[0][0] = 0, t = 0, h[t].insert(0), i = 0; i < n; ++i )
		for ( t ^= 1, h[t].clear(), l[t^1] = h[t^1].begin(); l[t^1] != h[t^1].end(); ++l[t^1]  )
			if ( dp[i][k=*l[t^1]] < w )
				for ( j = 0; j*c[i]+k <= diff && dp[i][k]+j < w; ++j )
					if ( dp[i+1][j*c[i]+k] > dp[i][k]+j ) {
						dp[i+1][j*c[i]+k] = dp[i][k]+j, h[t].insert(j*c[i]+k);
						if ( j*c[i]+k == diff && w < dp[i+1][j*c[i]+k] )
							w = dp[i+1][j*c[i]+k];
					}
	if ( dp[n][diff] == +oo ) {
		return false;
	}
	*res = dp[n][diff]*2;
	return true;

	for ( k = 0; k <= diff; ++k )
		z[k] = +oo, pos[k] = -1;
	for ( z[0]=0, push(0); cn;) {
		for ( k = pop(), jt = e.begin(); jt != e.end() && k != diff; ++jt ) 
			for ( j = 0; j*(*jt)+k <= diff; ++j )
				if ( z[j*(*jt)+k] > z[k]+j )
					z[j*(*jt)+k]=z[k]+j,push(j*(*jt)+k);
		if ( k == diff ) break ;
	}
	if ( z[diff] < +oo ) {
		*res = z[diff]*2;
		return true;
	}
	return false;
}

int main() {
	int i,j,k,l,ts,qr,diff;
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif
	for ( scanf("%d",&ts); ts--; ) {
		scanf("%d %d",&n,&m);
		for ( i = 0; i < n; adj[i++].clear() );
		for ( i = 0; i < n; ++i )
			for ( j = 0; j < n; ++j )
				g[i][j]=(1<<29),p[i][j]=-1;
		for ( l = m; l--; ) {
			scanf("%d %d %d",&i,&j,&k), --i, --j;
			adj[i].push_back(make_pair(j,k));
			adj[j].push_back(make_pair(i,k));
			g[i][j]=g[j][i]=min(g[i][j],k),p[i][j]=i;
		}
		for ( i = 0; i < n; ++i )
			p[i][i] = i, g[i][i] = 0;
		memset(d,0xff,sizeof d);
		for ( i = 0; i < n; ++i )
			for ( j = 0; j < n; ++j )
				if ( g[i][j] < (1<<29) )
					d[i][j] = g[i][j], p[i][j] = i;
		for ( k = 0; k < n; ++k )
			for ( i = 0; i < n; ++i )
				for ( j = 0; j < n && i != k; ++j )
					if ( k != j && d[i][k] < +oo && d[k][j] < +oo )
						if ( (d[i][j]=min(d[i][j],d[i][k]+d[k][j]))==d[i][k]+d[k][j] )
							p[i][j] = p[k][j];
		/*
		for ( i = 0; i < n; ++i )
			for ( j = 0; j < n; ++j )
				if ( i != j ) {
					v[i][j].clear();
					if ( d[i][j] < +oo )
						dump(i,j,j);
				}
				*/
		memset(precalc,0,sizeof precalc);
		for ( scanf("%d",&qr); qr--; ) {
			scanf("%d %d %d",&i,&j,&k), --i, --j;
			if ( k == d[i][j] ) {
				if ( !precalc[i][j] ) dump(i,j,j), precalc[i][j] = true;
				printf("Yes %lu\n",v[i][j].size());
				continue ;
			}
			if ( k < d[i][j] ) {
				puts("No");
				continue ;
			}
			diff = k-d[i][j];
			if ( !precalc[i][j] ) dump(i,j,j), precalc[i][j] = true;
			if ( f(i,j,diff,&k) ) {
				printf("Yes %lu\n",v[i][j].size()+k);
				continue ;
			}
			puts("No");
		}
		if ( ts ) putchar('\n');
	}
    return 0;
}



Post Reply

Return to “Volume 104 (10400-10499)”