CentaurCompany.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
#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;

#define DEBUG(x)	cout << #x << " = " << x << "\n"
#define endl 		("\n")

#define	ep		1e-9
#define PI		M_PI
#define E 		M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp		make_pair
#define	pb		push_back

#define	all(c)		(c).begin(), (c).end()
#define	tr(i, c)	for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

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

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

#define Pf		printf
#define	Sf		scanf

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

/*
#ifdef DEBUG
	#undef DEBUG
#endif
#define DEBUG
*/

class CentaurCompany
{
public:
	double getvalue(vector <int> a, vector <int> b);
};

double CentaurCompany::getvalue (vector <int> a, vector <int> b) 
{
	double ret;
	
	return ret;
}

// 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 <int> p0, vector <int> p1, bool hasAnswer, double p2) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p1.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p1[i];
	}
	cout << "}";
	cout << "]" << endl;
	CentaurCompany *obj;
	double answer;
	obj = new CentaurCompany();
	clock_t startTime = clock();
	answer = obj->getvalue(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 == answer && fabs(p2 - answer) <= 1e-9 * max(1.0, fabs(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 <int> p0;
	vector <int> p1;
	double p2;
	
	{
	// ----- test 0 -----
	int t0[] = {1};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 0.0;
	all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {1,1,1};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,3,4};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 0.125;
	all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {1,2,3,2,2};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,3,4,5,6};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 0.375;
	all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	int t0[] = {1,2,3,4,5,6,7,8,9};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,3,4,5,6,7,8,9,10};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 0.41796875;
	all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	int t0[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 15.500000001076842;
	all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	int t0[] = {10,7,2,5,6,2,4,9,7};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {8,10,10,4,1,6,2,2,3};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	p2 = 0.646484375;
	all_right = KawigiEdit_RunTest(5, 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
// The Centaur company has N servers, numbered 1 through N.
// These servers are currently connected into a network.
// The topology of the network is a tree.
// In other words, there are exactly N-1 bidirectional cables, each connecting some two servers in such a way that the entire network is connected.
// 
// The Centaur company is about to split into two new companies: the Human company and the Horse company.
// When this happens, the companies will divide the servers randomly.
// More precisely, for each of the N servers the two companies will flip a fair coin, and the winner of the coin flip gets the server.
// Once they divide the servers, each company will configure their own servers not to use the cables that lead to the servers of the other company.
// 
// Of course, it may then happen that some pairs of servers that belong to the same company will not be able to communicate any more.
// Therefore, each of the new companies will then use new, additional cables to connect all of its servers to the same network.
// New cables can be added for free.
// However, each of the servers currently only has one empty slot into which an end of a cable can be inserted.
// Adding one additional empty slot to a server costs 1.
// If desired, it is possible to add multiple slots to the same server.
// Each of the companies will connect their servers using a way with the smallest possible cost.
// 
// You are given two vector <int>s a and b, each containing N-1 elements.
// These two arrays describe the original cables:
// for each i, there is a cable that connects the servers a[i] and b[i].
// 
// Compute and return the expected value of the total cost paid by the two companies to connect their networks.
// (The expectation is taken over all possible ways in which they can divide the N servers.)
// 
// DEFINITION
// Class:CentaurCompany
// Method:getvalue
// Parameters:vector <int>, vector <int>
// Returns:double
// Method signature:double getvalue(vector <int> a, vector <int> b)
// 
// 
// NOTES
// -N can be determined as (1 + the length of a).
// -The expected value of a variable can be seen as the average value of the variable, where the average is taken over many rounds of the experiment. See http://en.wikipedia.org/wiki/Expected_value for a formal definition.
// -Your return value must have a relative or absolute error of at most 1e-9.
// 
// 
// CONSTRAINTS
// -N will be between 2 and 36, inclusive.
// -a and b will contain exactly N-1 elements.
// -Each element of a and b will be between 1 and N, inclusive.
// -The network defined by a and b will be a tree (as explained in the problem statement).
// 
// 
// EXAMPLES
// 
// 0)
// {1}
// {2}
// 
// Returns: 0.0
// 
// Regardless of the result of the coin flips, the companies don't need additional cables to connect their own servers. Therefore, the expected cost is zero.
// 
// 1)
// {1,1,1}
// {2,3,4}
// 
// Returns: 0.125
// 
// If the Horse company gets only the server 1 and the Human company gets the other servers, the Human company must add one empty slot. For example, the Human company can add one empty slot to the server 2 and add new cables to connect the server 2 with the servers 3 and 4. Similarly, if the Human company gets only the server 1 and the Horse company gets the other servers, the cost will also be 1. In all other cases the cost will be 0. The expected cost is 1/(2^4) + 1/(2^4) = 1/8.
// 
// 2)
// {1,2,3,2,2}
// {2,3,4,5,6}
// 
// Returns: 0.375
// 
// For example, if the Horse company gets only the server 2 and the Human company gets the other servers, the Human company must add one empty slot. In the picture below, initially each server has one empty slot (blue). The Human company adds one extra slot (yellow) to the server 5. The Human company also adds cables that connect the servers 1 and 5, 3 and 5, and 4 and 6.
// 
// 
// 
// 
// 3)
// {1,2,3,4,5,6,7,8,9}
// {2,3,4,5,6,7,8,9,10}
// 
// Returns: 0.41796875
// 
// 
// 
// 4)
// {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
// {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36}
// 
// Returns: 15.500000001076842
// 
// 
// 
// 5)
// {10, 7, 2, 5, 6, 2, 4, 9, 7}
// {8, 10, 10, 4, 1, 6, 2, 2, 3}
// 
// Returns: 0.646484375
// 
// 
// 
// END KAWIGIEDIT TESTING

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