4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: vector<double> solve_linear_eq( int n, vector< vector<double> > M, const vector<double>& V )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	vector<double> A(V);
4fd800b3a8 2011-02-23        kinaba: 	for(int i=0; i<n; ++i)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		// pivot
4fd800b3a8 2011-02-23        kinaba: 		if( M[i][i] == 0 )
4fd800b3a8 2011-02-23        kinaba: 			for(int j=i+1; j<n; ++j)
4fd800b3a8 2011-02-23        kinaba: 				if( M[j][i] != 0 )
4fd800b3a8 2011-02-23        kinaba: 					{swap(M[i], M[j]); swap(A[i], A[j]); break;}
4fd800b3a8 2011-02-23        kinaba: 		if( M[i][i] == 0 )
4fd800b3a8 2011-02-23        kinaba: 			throw "no anser";
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// M[i][i] <-- 1
4fd800b3a8 2011-02-23        kinaba: 		double p = M[i][i];
4fd800b3a8 2011-02-23        kinaba: 		for(int j=i; j<n; ++j)
4fd800b3a8 2011-02-23        kinaba: 			M[i][j] /= p;
4fd800b3a8 2011-02-23        kinaba: 		A[i] /= p;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// M[*][i] <-- 0
4fd800b3a8 2011-02-23        kinaba: 		for(int j=0; j<n; ++j) if(j!=i)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			double r = M[j][i];
4fd800b3a8 2011-02-23        kinaba: 			for(int k=i; k<n; ++k)
4fd800b3a8 2011-02-23        kinaba: 				M[j][k] -= M[i][k] * r;
4fd800b3a8 2011-02-23        kinaba: 			A[j] -= A[i] * r;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	return A;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // Check the given list can be a degree list of some graph
4fd800b3a8 2011-02-23        kinaba: //   O(n^2 log n)
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   - SRM 398 Div1 LV3
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: //((
4fd800b3a8 2011-02-23        kinaba: // Havel-Hakimi
4fd800b3a8 2011-02-23        kinaba: //   If G[0], ..., G[n] (decreasing) is graphical,
4fd800b3a8 2011-02-23        kinaba: //   then G[1]-1, G[2]-1, ..., G[G[0]]-1, G[G[0]+1], .., G[n]
4fd800b3a8 2011-02-23        kinaba: //   is also graphical.
4fd800b3a8 2011-02-23        kinaba: //))
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: bool isGraphical( vector<int> G )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	sort( G.begin(), G.end() );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	vector<int>::iterator b = lower_bound( G.begin(), G.end(), 1 );
4fd800b3a8 2011-02-23        kinaba: 	vector<int>::iterator e = G.end();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	while( b < e )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int n = *(--e);
4fd800b3a8 2011-02-23        kinaba: 		if( e-b < n )
4fd800b3a8 2011-02-23        kinaba: 			return false;
4fd800b3a8 2011-02-23        kinaba: 		for(vector<int>::iterator i=e-n; i!=e; ++i)
4fd800b3a8 2011-02-23        kinaba: 			--*i;
4fd800b3a8 2011-02-23        kinaba: 		inplace_merge( b, e-n, e );
4fd800b3a8 2011-02-23        kinaba: 		b = lower_bound( G.begin(), G.end(), 1 );
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	return true;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct MyFriends
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	string calcFriends(vector <int> sumFriends, int k)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int n = sumFriends.size();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		vector< vector<double> > M(n, vector<double>(n));
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<n; ++i)
4fd800b3a8 2011-02-23        kinaba: 			for(int j=0; j<n; ++j)
4fd800b3a8 2011-02-23        kinaba: 				M[i][j] = (i==j || (i+k)%n==j ? 0 : 1);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// calc #friends of each kid
4fd800b3a8 2011-02-23        kinaba: 		vector<double> V( sumFriends.begin(), sumFriends.end() );
4fd800b3a8 2011-02-23        kinaba: 		vector<double> Ad = solve_linear_eq( n, M, V );
4fd800b3a8 2011-02-23        kinaba: 		vector<int> A;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<n; ++i)
4fd800b3a8 2011-02-23        kinaba: 			A.push_back( (int)floor(Ad[i]+0.5) );
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// verify
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<n; ++i)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int sum = 0;
4fd800b3a8 2011-02-23        kinaba: 			for(int j=0; j<n; ++j)
4fd800b3a8 2011-02-23        kinaba: 				sum += (i==j || (i+k)%n==j ? 0 : A[j]);
4fd800b3a8 2011-02-23        kinaba: 			if( sum != sumFriends[i] )
4fd800b3a8 2011-02-23        kinaba: 				return "IMPOSSIBLE";
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return isGraphical(A) ? "POSSIBLE" : "IMPOSSIBLE";
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };