Artifact 19f42a31025a41f778ec26e9277c557f48db7659

• File SRM/398/1C.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

vector<double> solve_linear_eq( int n, vector< vector<double> > M, const vector<double>& V )
{
	vector<double> A(V);
	for(int i=0; i<n; ++i)
	{
		// pivot
		if( M[i][i] == 0 )
			for(int j=i+1; j<n; ++j)
				if( M[j][i] != 0 )
					{swap(M[i], M[j]); swap(A[i], A[j]); break;}
		if( M[i][i] == 0 )
			throw "no anser";

		// M[i][i] <-- 1
		double p = M[i][i];
		for(int j=i; j<n; ++j)
			M[i][j] /= p;
		A[i] /= p;

		// M[*][i] <-- 0
		for(int j=0; j<n; ++j) if(j!=i)
		{
			double r = M[j][i];
			for(int k=i; k<n; ++k)
				M[j][k] -= M[i][k] * r;
			A[j] -= A[i] * r;
		}
	}
	return A;
}

//-------------------------------------------------------------
// Check the given list can be a degree list of some graph
//   O(n^2 log n)
//
// Verified by
//   - SRM 398 Div1 LV3
//
//((
// Havel-Hakimi
//   If G[0], ..., G[n] (decreasing) is graphical,
//   then G[1]-1, G[2]-1, ..., G[G[0]]-1, G[G[0]+1], .., G[n]
//   is also graphical.
//))
//-------------------------------------------------------------

bool isGraphical( vector<int> G )
{
	sort( G.begin(), G.end() );

	vector<int>::iterator b = lower_bound( G.begin(), G.end(), 1 );
	vector<int>::iterator e = G.end();

	while( b < e )
	{
		int n = *(--e);
		if( e-b < n )
			return false;
		for(vector<int>::iterator i=e-n; i!=e; ++i)
			--*i;
		inplace_merge( b, e-n, e );
		b = lower_bound( G.begin(), G.end(), 1 );
	}
	return true;
}

struct MyFriends
{
	string calcFriends(vector <int> sumFriends, int k)
	{
		int n = sumFriends.size();

		vector< vector<double> > M(n, vector<double>(n));
		for(int i=0; i<n; ++i)
			for(int j=0; j<n; ++j)
				M[i][j] = (i==j || (i+k)%n==j ? 0 : 1);

		// calc #friends of each kid
		vector<double> V( sumFriends.begin(), sumFriends.end() );
		vector<double> Ad = solve_linear_eq( n, M, V );
		vector<int> A;
		for(int i=0; i<n; ++i)
			A.push_back( (int)floor(Ad[i]+0.5) );

		// verify
		for(int i=0; i<n; ++i)
		{
			int sum = 0;
			for(int j=0; j<n; ++j)
				sum += (i==j || (i+k)%n==j ? 0 : A[j]);
			if( sum != sumFriends[i] )
				return "IMPOSSIBLE";
		}

		return isGraphical(A) ? "POSSIBLE" : "IMPOSSIBLE";
	}
};