fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <random>
  3.  
  4. const int N = 100;
  5. const int M = 10000;
  6. const double CHEAT_FRAC = 0.5;
  7.  
  8. int solve(std::vector<std::vector<bool>> scores) {
  9. 	using namespace std;
  10. 	assert(int(scores.size()) == N);
  11. 	assert(int(scores[0].size()) == M);
  12.  
  13. 	vector<double> people(N);
  14. 	vector<double> cheat_people(N);
  15. 	for (int i = 0; i < N; i++) {
  16. 		int num_solves = std::accumulate(scores[i].begin(), scores[i].end(), 0);
  17. 		double frac_solves = double(num_solves) / double(M);
  18. 		// if our score is v, then our solve fraction should be 1/6 integral_{-3+v}^{3+v} 1/1+e^{-x} dx = log(e^(v+3) + 1) - log(e^(v-3) + 1) = log((e^3 * e^v + 1) / (e^-3 * e^v + 1))
  19. 		people[i] = std::clamp(exp(3) * (exp(6 * frac_solves - 3) - exp(-3)) / (exp(3) - exp(6 * frac_solves - 3)), exp(-3), exp(3));
  20.  
  21. 		double cheat_frac_solves = std::clamp((frac_solves - CHEAT_FRAC) / (1 - CHEAT_FRAC), 0., 1.);
  22. 		cheat_people[i] = std::clamp(exp(3) * (exp(6 * cheat_frac_solves - 3) - exp(-3)) / (exp(3) - exp(6 * cheat_frac_solves - 3)), exp(-3), exp(3));
  23. 	}
  24. 	vector<double> probs(M);
  25. 	{
  26. 		vector<char> cur_scores(N);
  27. 		for (int j = 0; j < M; j++) {
  28. 			for (int i = 0; i < N; i++) {
  29. 				cur_scores[i] = scores[i][j];
  30. 			}
  31. 			auto eval_prob = [&](double v) {
  32. 				double res = 1;
  33. 				for (int i = 0; i < N; i++) {
  34. 					res *= (cur_scores[i] ? people[i] : v) / (people[i] + v);
  35. 				}
  36. 				return res;
  37. 			};
  38.  
  39. 			// estimate the difficulty
  40. 			double mi = exp(-3), ma = exp(3);
  41. 			for (int z = 0; z < 30; z++) {
  42. 				double md1 = (2 * mi + ma) / 3;
  43. 				double md2 = (mi + 2 * ma) / 3;
  44. 				if (eval_prob(md1) < eval_prob(md2)) {
  45. 					mi = md1;
  46. 				} else {
  47. 					ma = md2;
  48. 				}
  49. 			}
  50. 			probs[j] = (mi+ma)/2;
  51. 		}
  52. 	}
  53.  
  54. 	/*
  55. 	cerr << "Inferred values" << '\n';
  56. 	for (int i = 0; i < N; i++) {
  57. 		cerr << showpos << fixed << setprecision(2) << log(people[i]) << " \n"[i+1==N];
  58. 	}
  59. 	for (int j = 0; j < M; j++) {
  60. 		cerr << showpos << fixed << setprecision(2) << log(probs[j]) << " \n"[j+1==M];
  61. 	}
  62. 	*/
  63.  
  64. 	vector<double> cheater_vals(N);
  65. 	for (int i = 0; i < N; i++) {
  66. 		double cheater_odds = 1;
  67. 		for (int j = 0; j < M; j++) {
  68. 			cheater_odds *= (scores[i][j] ? (cheat_people[i] + CHEAT_FRAC * probs[j]) : ((1-CHEAT_FRAC) * probs[j])) / (cheat_people[i] + probs[j]);
  69. 			cheater_odds /= (scores[i][j] ? people[i] : probs[j]) / (people[i] + probs[j]);
  70. 		}
  71. 		cheater_vals[i] = cheater_odds;
  72. 	}
  73.  
  74. 	return int(max_element(cheater_vals.begin(), cheater_vals.end()) - cheater_vals.begin());
  75. }
  76.  
  77. std::mt19937 mt(48);
  78. bool run_test() {
  79. 	using namespace std;
  80. 	std::uniform_real_distribution<double> dist(-3, 3);
  81. 	vector<double> people(N);
  82. 	for (auto& v : people) v = exp(dist(mt));
  83. 	vector<double> probs(M);
  84. 	for (auto& v : probs) v = exp(dist(mt));
  85.  
  86. 	/*
  87. 	cerr << "Original values" << '\n';
  88. 	for (int i = 0; i < N; i++) {
  89. 		cerr << showpos << fixed << setprecision(2) << log(people[i]) << " \n"[i+1==N];
  90. 	}
  91. 	for (int j = 0; j < M; j++) {
  92. 		cerr << showpos << fixed << setprecision(2) << log(probs[j]) << " \n"[j+1==M];
  93. 	}
  94. 	*/
  95.  
  96. 	vector<vector<bool>> scores(N, vector<bool>(M));
  97. 	for (int i = 0; i < N; i++) {
  98. 		for (int j = 0; j < M; j++) {
  99. 			scores[i][j] = std::bernoulli_distribution(people[i] / (people[i] + probs[j]))(mt);
  100. 		}
  101. 	}
  102.  
  103. 	int cheater = std::uniform_int_distribution(0, N-1)(mt);
  104. 	for (int j = 0; j < M; j++) {
  105. 		if (std::bernoulli_distribution(CHEAT_FRAC)(mt)) scores[cheater][j] = true;
  106. 	}
  107. 	int found_cheater = solve(scores);
  108. 	cerr << "Actual cheater" << ' ' << cheater << '\n';
  109. 	cerr << "Guessed cheater" << ' ' << found_cheater << '\n';
  110. 	return cheater == found_cheater;
  111. }
  112.  
  113. void test() {
  114. 	using namespace std;
  115. 	int tot_tests = 0;
  116. 	int tot_pass = 0;
  117. 	for (int z = 0; z < 100; z++) {
  118. 		tot_tests++;
  119. 		tot_pass += run_test();
  120. 		cerr << "Ratio: " << tot_pass << "/" << tot_tests << " = " << fixed << setprecision(4) << double(tot_pass)/double(tot_tests) << '\n';
  121. 	}
  122. }
  123.  
  124. int main() {
  125. 	using namespace std;
  126. 	ios_base::sync_with_stdio(false), cin.tie(nullptr);
  127.  
  128. 	//test();
  129.  
  130. 	int T; cin >> T;
  131. 	int P; cin >> P;
  132. 	for (int case_num = 1; case_num <= T; case_num ++) {
  133. 		vector<vector<bool>> v(N, vector<bool>(M));
  134. 		for (auto& r : v) {
  135. 			string s; cin >> s;
  136. 			assert(int(s.size()) == M);
  137. 			for (int j = 0; j < M; j++) r[j] = s[j] - '0';
  138. 		}
  139.  
  140. 		int ans = solve(v);
  141. 		cout << "Case #" << case_num << ": " << ans+1 << '\n';
  142. 	}
  143.  
  144. 	return 0;
  145. }
  146.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int solve(std::vector<std::vector<bool> >)’:
prog.cpp:19:20: error: ‘clamp’ is not a member of ‘std’
   people[i] = std::clamp(exp(3) * (exp(6 * frac_solves - 3) - exp(-3)) / (exp(3) - exp(6 * frac_solves - 3)), exp(-3), exp(3));
                    ^~~~~
prog.cpp:21:35: error: ‘clamp’ is not a member of ‘std’
   double cheat_frac_solves = std::clamp((frac_solves - CHEAT_FRAC) / (1 - CHEAT_FRAC), 0., 1.);
                                   ^~~~~
prog.cpp:22:26: error: ‘clamp’ is not a member of ‘std’
   cheat_people[i] = std::clamp(exp(3) * (exp(6 * cheat_frac_solves - 3) - exp(-3)) / (exp(3) - exp(6 * cheat_frac_solves - 3)), exp(-3), exp(3));
                          ^~~~~
prog.cpp: In function ‘bool run_test()’:
prog.cpp:103:45: error: missing template arguments before ‘(’ token
  int cheater = std::uniform_int_distribution(0, N-1)(mt);
                                             ^
stdout
copy 
Standard output is empty
https://ideone.com/nRYKXS
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!