4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: template<typename T> 4fd800b3a8 2011-02-23 kinaba: struct DP2 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int N1, N2; 4fd800b3a8 2011-02-23 kinaba: vector<T> data; 4fd800b3a8 2011-02-23 kinaba: DP2(){} 4fd800b3a8 2011-02-23 kinaba: DP2(int N1, int N2, const T& t = T()) 4fd800b3a8 2011-02-23 kinaba: : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); } 4fd800b3a8 2011-02-23 kinaba: T& operator()(int i1, int i2) 4fd800b3a8 2011-02-23 kinaba: { return data[ (i1*N2)+i2 ]; } 4fd800b3a8 2011-02-23 kinaba: void swap(DP2& rhs) 4fd800b3a8 2011-02-23 kinaba: { data.swap(rhs.data); } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class FriendTour { public: 4fd800b3a8 2011-02-23 kinaba: double tourProbability(vector <string> friends, int K) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int N = (int)friends.size(); 4fd800b3a8 2011-02-23 kinaba: vector< vector<int> > f(N); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<N; ++i) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: stringstream sin( friends[i] ); 4fd800b3a8 2011-02-23 kinaba: for(int v; sin>>v; ) 4fd800b3a8 2011-02-23 kinaba: f[i].push_back(v-1); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: map<int,int> rename; 4fd800b3a8 2011-02-23 kinaba: rename[0] = 0; 4fd800b3a8 2011-02-23 kinaba: for(int k=0; k<f[0].size(); ++k) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int newid = rename.size(); 4fd800b3a8 2011-02-23 kinaba: rename[f[0][k]] = newid; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector< vector<int> > ff(rename.size()); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<N; ++i) 4fd800b3a8 2011-02-23 kinaba: if( rename.count(i) ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int k = rename[i]; 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<f[i].size(); ++j) 4fd800b3a8 2011-02-23 kinaba: if( f[i][j]!=0 && rename.count(f[i][j]) ) 4fd800b3a8 2011-02-23 kinaba: ff[k].push_back( rename[f[i][j]] ); 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: ff[k].push_back( -1 ); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return solve(ff, K); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double solve(vector<vector<int> >& f, int K) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: memo = DP2<double>(f.size(), 1<<f.size(), -1); 4fd800b3a8 2011-02-23 kinaba: return rec(f, K, 0, 1); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double C(int N, int K) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: double p = 1.0; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<min(K,N-K); ++i) 4fd800b3a8 2011-02-23 kinaba: p = p * (N-i) / (1+i); 4fd800b3a8 2011-02-23 kinaba: return p; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: DP2<double> memo; 4fd800b3a8 2011-02-23 kinaba: double rec(vector<vector<int> >& f, int K, int v, int mask) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( memo(v,mask) != -1 ) 4fd800b3a8 2011-02-23 kinaba: return memo(v,mask); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: if( mask == (1<<f.size())-1 ) 4fd800b3a8 2011-02-23 kinaba: return 1.0; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<double> nxt; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<f[v].size(); ++i) 4fd800b3a8 2011-02-23 kinaba: if( f[v][i]==-1 || (mask & (1<<f[v][i])) ) 4fd800b3a8 2011-02-23 kinaba: nxt.push_back(0); 4fd800b3a8 2011-02-23 kinaba: else 4fd800b3a8 2011-02-23 kinaba: nxt.push_back( rec(f,K,f[v][i],mask|(1<<f[v][i])) ); 4fd800b3a8 2011-02-23 kinaba: sort(nxt.rbegin(), nxt.rend()); 4fd800b3a8 2011-02-23 kinaba: int N = nxt.size(); 4fd800b3a8 2011-02-23 kinaba: if( N == 0 ) 4fd800b3a8 2011-02-23 kinaba: return memo(v,mask) = 0.0; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: if( N <= K ) 4fd800b3a8 2011-02-23 kinaba: return memo(v,mask) = nxt[0]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double p = 0.0; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<nxt.size(); ++i) { 4fd800b3a8 2011-02-23 kinaba: if( N-1-i < K ) { 4fd800b3a8 2011-02-23 kinaba: p += C(N-i,K) / C(N,K) * nxt[i]; 4fd800b3a8 2011-02-23 kinaba: break; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: p += (C(N-i,K) - C(N-1-i,K)) / C(N,K) * nxt[i]; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return memo(v,mask) = p; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const double& Expected, const double& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, FriendTour().tourProbability(friends, K));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: string friends_[] = {"2 3 4", 4fd800b3a8 2011-02-23 kinaba: "1 3 4", 4fd800b3a8 2011-02-23 kinaba: "1 2 4", 4fd800b3a8 2011-02-23 kinaba: "1 2 3"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> friends(friends_, friends_+sizeof(friends_)/sizeof(*friends_)); 4fd800b3a8 2011-02-23 kinaba: int K = 1; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.2222222222222222; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: string friends_[] = {"2 3 4", 4fd800b3a8 2011-02-23 kinaba: "1 3 4", 4fd800b3a8 2011-02-23 kinaba: "1 2 4", 4fd800b3a8 2011-02-23 kinaba: "1 2 3"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> friends(friends_, friends_+sizeof(friends_)/sizeof(*friends_)); 4fd800b3a8 2011-02-23 kinaba: int K = 2; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.6666666666666666; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: string friends_[] = {"3 2 4", 4fd800b3a8 2011-02-23 kinaba: "3 5 1", 4fd800b3a8 2011-02-23 kinaba: "5 2 1 4", 4fd800b3a8 2011-02-23 kinaba: "3 1 5", 4fd800b3a8 2011-02-23 kinaba: "3 2 4"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> friends(friends_, friends_+sizeof(friends_)/sizeof(*friends_)); 4fd800b3a8 2011-02-23 kinaba: int K = 2; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.3333333333333333; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: string friends_[] = {"3 2 4", 4fd800b3a8 2011-02-23 kinaba: "3 5 1", 4fd800b3a8 2011-02-23 kinaba: "5 2 1 4", 4fd800b3a8 2011-02-23 kinaba: "3 1 5 6", 4fd800b3a8 2011-02-23 kinaba: "3 2 4", 4fd800b3a8 2011-02-23 kinaba: "4"} 4fd800b3a8 2011-02-23 kinaba: ; 4fd800b3a8 2011-02-23 kinaba: vector <string> friends(friends_, friends_+sizeof(friends_)/sizeof(*friends_)); 4fd800b3a8 2011-02-23 kinaba: int K = 2; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.3055555555555556; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: string friends_[] = {"6 5 4 2", 4fd800b3a8 2011-02-23 kinaba: "1 6 3 5", 4fd800b3a8 2011-02-23 kinaba: "5 4 2", 4fd800b3a8 2011-02-23 kinaba: "3 1 5", 4fd800b3a8 2011-02-23 kinaba: "2 4 3 1 6", 4fd800b3a8 2011-02-23 kinaba: "1 2 5"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> friends(friends_, friends_+sizeof(friends_)/sizeof(*friends_)); 4fd800b3a8 2011-02-23 kinaba: int K = 3; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.73125; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: string friends_[] = {"2 3 4 5 6 7 8 9 10 11 12 13 14 15 16", "1 3 4 5 6 7 8 9 10 11 12 13 14 15 16", "1 2 4 5 6 7 8 9 10 11 12 13 14 15 16", "1 2 3 5 6 7 8 9 10 11 12 13 14 15 16", "1 2 3 4 6 7 8 9 10 11 12 13 14 15 16", "1 2 3 4 5 7 8 9 10 11 12 13 14 15 16", "1 2 3 4 5 6 8 9 10 11 12 13 14 15 16", "1 2 3 4 5 6 7 9 10 11 12 13 14 15 16", "1 2 3 4 5 6 7 8 10 11 12 13 14 15 16", "1 2 3 4 5 6 7 8 9 11 12 13 14 15 16", "1 2 3 4 5 6 7 8 9 10 12 13 14 15 16", "1 2 3 4 5 6 7 8 9 10 11 13 14 15 16", "1 2 3 4 5 6 7 8 9 10 11 12 14 15 16", "1 2 3 4 5 6 7 8 9 10 11 12 13 15 16", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 16", "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> friends(friends_, friends_+sizeof(friends_)/sizeof(*friends_)); 4fd800b3a8 2011-02-23 kinaba: int K = 3; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.010989546288518458; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE