Egalitarianism.cpp

#include <iostream>
#include <ctime>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cassert>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iterator>
#include <fstream>
using namespace std;

typedef long long 		int64;
typedef vector<int> 		vi;
typedef string 			ST;
typedef stringstream 		SS;
typedef vector< vector<int> > 	vvi;
typedef pair<int,int> 		ii;
typedef vector<string> 		vs;
/*
#if __cplusplus > 199711L	// for g++0x, value of __cplusplus must be greater thana 199711L.
	#define tr(i, c)	for(auto i = begin(c); i != end(c); i++)
#else
	#define tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#endif
*/
#define endl		("\n")
#define tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define PI		M_PI
#define E 		M_E
#define	eps		1e-9

#define	Sf		scanf
#define	Pf		printf

#define forn(i, n)	for(int i = 0, lets_stop_here = (int)n; i <  lets_stop_here; i++)
#define forab(i, a, b)	for(int i = a, lets_stop_here = (int)b; i <= lets_stop_here; i++)
#define rep(i, a, b)	for(int i = a, lets_stop_here = (int)b; i >= lets_stop_here; i--)

#define	all(c)		(c).begin(), (c).end()
#define	cl(a, b)	memset(a, b, sizeof(a))
#define mp		make_pair
#define pb		push_back

#define	present(x, c)	((c).find(x) != (c).end())	//map & set//
#define	cpresent(x, c)	(find( (c).begin(), (c).end(), x) != (c).end())	//vector & list//

#define read(n)		scanf("%d", &n)
#define write(n)	printf("%d ", n)
#define writeln(n)	printf("%d\n", n)

//#define debug(x)
#define debug(x)	cout << #x << " = " << x << "\n"

class Egalitarianism
{
public:
	int maxDifference(vector <string> isFriend, int d);
};

int Egalitarianism::maxDifference (vector <string> isFriend, int d) 
{
	const int oo = 1e7;
	int N = isFriend.size();
	vector <vector<int> > dist(N, vector <int> (N, oo));
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			if(isFriend[i][j] == 'Y')
				dist[i][j] = 1;
		}
		dist[i][i] = 0;
	}
	for(int k = 0; k < N; ++k) {
		for(int i = 0; i < N; ++i) {
			for(int j = 0; j < N; ++j) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	int ret = 0;
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			ret = max(ret, dist[i][j]);
		}
	}
	
	return ret == oo ? -1 : ret*d;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <string> p0, int p1, bool hasAnswer, int p2) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << "\"" << p0[i] << "\"";
	}
	cout << "}" << "," << p1;
	cout << "]" << endl;
	Egalitarianism *obj;
	int answer;
	obj = new Egalitarianism();
	clock_t startTime = clock();
	answer = obj->maxDifference(p0, p1);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p2 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p2;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <string> p0;
	int p1;
	int p2;
	
	{
	// ----- test 0 -----
	string t0[] = {"NYN","YNY","NYN"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 10;
	p2 = 20;
	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	string t0[] = {"NN","NN"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 1;
	p2 = -1;
	all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	string t0[] = {"NNYNNN","NNYNNN","YYNYNN","NNYNYY","NNNYNN","NNNYNN"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 1000;
	p2 = 3000;
	all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	string t0[] = {"NNYN","NNNY","YNNN","NYNN"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 584;
	p2 = -1;
	all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	string t0[] = {"NYNYYYN","YNNYYYN","NNNNYNN","YYNNYYN","YYYYNNN","YYNYNNY","NNNNNYN"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 5;
	p2 = 20;
	all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	string t0[] = {"NYYNNNNYYYYNNNN","YNNNYNNNNNNYYNN","YNNYNYNNNNYNNNN","NNYNNYNNNNNNNNN","NYNNNNYNNYNNNNN","NNYYNNYNNYNNNYN","NNNNYYNNYNNNNNN","YNNNNNNNNNYNNNN","YNNNNNYNNNNNYNN","YNNNYYNNNNNNNNY","YNYNNNNYNNNNNNN","NYNNNNNNNNNNNNY","NYNNNNNNYNNNNYN","NNNNNYNNNNNNYNN","NNNNNNNNNYNYNNN"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 747;
	p2 = 2988;
	all_right = KawigiEdit_RunTest(5, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 6 -----
	string t0[] = {"NY","YN"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 0;
	p2 = 0;
	all_right = KawigiEdit_RunTest(6, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// A kingdom has n citizens. Each one has some amount of money, a number of dollars denoted by a non-negative integer.
// 
// Citizens are numbered from 0 to n-1. Some citizens have friends. Their friendship network is described by a vector <string> called isFriend, such that if isFriend[i][j] == 'Y', the citizens numbered i and j are friends, and if isFriend[i][j] == 'N', these citizens are not friends.
// 
// The king decrees the following:
// 
// Each citizen's amount of money must be within d dollars of the amount of money belonging to any of his friends. In other words, a citizen with x dollars must not have any friends with less than x-d dollars or more than x+d dollars.
// 
// Given the number of citizens and their friendship network, what is the greatest possible money difference between any two people (not necessarily friends) in this kingdom? If there is a finite answer, return it. Otherwise, return -1.
// 
// DEFINITION
// Class:Egalitarianism
// Method:maxDifference
// Parameters:vector <string>, int
// Returns:int
// Method signature:int maxDifference(vector <string> isFriend, int d)
// 
// 
// CONSTRAINTS
// -n will be between 2 and 50, inclusive.
// -d will be between 0 and 1,000, inclusive.
// -isFriend will contain exactly n elements.
// -Each element of isFriend will contain exactly n characters, each of which is either 'Y' or 'N'.
// -For any i, isFriend[i][i] = 'N'.
// -For any i and j, isFriend[i][j] = isFriend[j][i].
// 
// 
// EXAMPLES
// 
// 0)
// {"NYN",
//  "YNY",
//  "NYN"}
// 10
// 
// Returns: 20
// 
// The kingdom has three citizens. Citizens 0 and 1 are friends. Also, citizens 1 and 2 are friends. The greatest possible money difference between any two citizens is $20, as in the following configuration: citizen 0 has $100; citizen 1 has $110; citizen 2 has $120.
// 
// 1)
// {"NN",
//  "NN"}
// 1
// 
// Returns: -1
// 
// Since citizens 0 and 1 are not friends, there are no constraints between them.
// 
// 2)
// {"NNYNNN",
//  "NNYNNN",
//  "YYNYNN",
//  "NNYNYY",
//  "NNNYNN",
//  "NNNYNN"}
// 1000
// 
// Returns: 3000
// 
// 
// 
// 3)
// {"NNYN",
//  "NNNY",
//  "YNNN",
//  "NYNN"}
// 584
// 
// Returns: -1
// 
// 
// 
// 4)
// {"NYNYYYN",
//  "YNNYYYN",
//  "NNNNYNN",
//  "YYNNYYN",
//  "YYYYNNN",
//  "YYNYNNY",
//  "NNNNNYN"}
// 5
// 
// Returns: 20
// 
// 
// 
// 5)
// {"NYYNNNNYYYYNNNN",
//  "YNNNYNNNNNNYYNN",
//  "YNNYNYNNNNYNNNN",
//  "NNYNNYNNNNNNNNN",
//  "NYNNNNYNNYNNNNN",
//  "NNYYNNYNNYNNNYN",
//  "NNNNYYNNYNNNNNN",
//  "YNNNNNNNNNYNNNN",
//  "YNNNNNYNNNNNYNN",
//  "YNNNYYNNNNNNNNY",
//  "YNYNNNNYNNNNNNN",
//  "NYNNNNNNNNNNNNY",
//  "NYNNNNNNYNNNNYN",
//  "NNNNNYNNNNNNYNN",
//  "NNNNNNNNNYNYNNN"}
// 
// 747
// 
// Returns: 2988
// 
// 
// 
// 6)
// {"NY",
//  "YN"}
// 0
// 
// Returns: 0
// 
// 
// 
// END KAWIGIEDIT TESTING


//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!