10828 - Back to Kernighan-Ritchie

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

Moderator: Board moderators

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Wed Aug 16, 2006 10:34 am

I get the correct result for all test-cases posted here. but i still get WA. Can somebody give some more test-cases?
Maybe i get a precision error. I use Gauss method for solving system of equations. Does it make lots of errors? what's a better way?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sat Sep 09, 2006 9:07 am

I have a question, how many equations do we need to solve?

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Sep 09, 2006 9:05 pm

sclo wrote:I have a question, how many equations do we need to solve?
My solution solves n equations with n unknowns.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Nov 07, 2007 8:43 pm

I use Gaussian Elimination with global pivoting strategy:

Code: Select all

#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 128
#define xchg(x,y) (((x)==(y))||((x)^=(y),(y)^=(x),(x)^=(y)))
#define tol (1e-10)

double max( double x, double y ) { return x < y ? y : x; }

int n,ts,deg[N],adj[N][N],id[N],is_inf[N];
double w[N][N],x[N];

int got_input() {
	int i,j,k;
	if ( scanf("%d",&n) != 1 || !n )
	   return 0;
	memset(deg,0,sizeof(deg));
	while ( scanf("%d %d",&i,&j) == 2 && (--i >= 0) )
		  adj[i][deg[i]++] = --j;
	return 1;
}

void init() {
	int i,j,k;

	for ( i = 0; i < n; i++ )
		for ( j = 0; j < n; j++ )
			w[i][j] = .0;

	for ( i = 0; i < n; i++ )
		for ( k = 0; k < deg[i]; k++ ) {
			j = adj[i][k];
			w[j][i] += (1.00 / deg[i]);
		}

	for ( i = 1; i < n; i++ )
		w[i][n] = .0;

	w[0][n] = -1.0;

	for ( i = 0; i < n; i++ ) {
		id[i] = i;
		is_inf[i] = 0;
	}
	for ( i = 0; i < n; i++ )
		w[i][i] -= 1.0;
}

int find_pivot( int m, int *r, int *c ) {
	int i,j,k;
	double tmp = .0;

	for ( i = m; i < n; i++ )
		for ( j = m; j < n; j++ )
			if ( tmp < fabs(w[i][j]) ) {
				tmp = fabs(w[i][j]);
				if ( r && c ) *r = i, *c = j;
			}
	return tmp > tol;
}

void swap_cols( const int c1, const int c2 ) {
	int i;
	double tmp;
	for ( i = 0; i < n; i++ )
		tmp = w[i][c1], w[i][c1] = w[i][c2], w[i][c2] = tmp;
}

void swap_rows( const int r1, const int r2 ) {
	int j;
	double tmp;
	for ( j = 0; j <= n; j++ )
		tmp = w[r1][j], w[r1][j] = w[r2][j], w[r2][j] = tmp;
}

void elim() {
	int i,j,k,t,r,c;
	double cf;

	for ( i = 0; i < n && find_pivot(i,&r,&c); i++ ) {
		swap_cols(i,c);
		swap_rows(i,r);
		xchg(id[i],id[c]);
		for ( t = i+1; t < n; t++ ) {
			cf = (w[t][i] / w[i][i]);
			for ( j = i; j <= n; j++ )
				w[t][j] -= w[i][j]*cf;
		}
	}
}

void back() {
	int i,j,k,t;
	double sum;

	for ( i = n-1; i >= 0 && fabs(w[i][i]) < tol; --i )
		is_inf[id[i]] = 1;
	for ( ;i >= 0; --i ) {
 		for ( sum = .0, j = n-1; j > i; --j )
 			if ( fabs(w[i][j]) > tol ) {
				if ( is_inf[id[j]] ) {
					is_inf[id[i]] = 1;
					goto next;
				}
				else
					sum += w[i][j]*x[id[j]];
	   		}
		x[id[i]] = ((w[i][n] - sum) / w[i][i]);
		next: continue;
	}
}

int main() {
	int i,j,k;
#ifndef ONLINE_JUDGE
	freopen("10828.in","r",stdin);
#endif
	while ( got_input() ) {
		printf("Case #%d:\n",++ts);
		init();
		elim();
		back();
		for ( scanf("%d",&k); k-- && scanf("%d",&i) == 1 && --i >= 0; )
			if ( is_inf[i] )
			   puts("infinity");
			else
				printf("%.3lf\n",x[i]+tol);
	}
	return 0;
}
but WA. Anyone who got it with the same algo, or you used some fancy algorithms?

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Thu Nov 08, 2007 12:21 pm

How to deal with multiple edges?

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Re: 10828 - Back to Kernighan-Ritchie

Post by 898989 » Fri Oct 16, 2009 2:43 pm

Hmmm, How to handle the infinity case?, My Gaussian either says (we have sol, no sol, infinite ones)
I passed all the samples with wrong judging on infinity case.
Sleep enough after death, it is the time to work.
Mostafa Saad

Post Reply

Return to “Volume 108 (10800-10899)”