#include <bits/stdc++.h> | |
using namespace std; | |
using i128 = __int128_t; | |
string str(i128 x){ | |
if(x == 0) return "0"; | |
string s = ""; | |
while(x){ | |
s += char('0' + int(x % 10)); | |
x /= 10; | |
} | |
reverse(s.begin(), s.end()); | |
return s; | |
} | |
const int N = 128; | |
vector<vector<i128> > ncr(N, vector<i128>(N, 0)); | |
void init(){ | |
ncr[0][0] = 1; | |
for(int i = 1; i < N; i++){ | |
for(int j = 0; j < N; j++){ | |
ncr[i][j] += ncr[i-1][j]; | |
if(j > 0) ncr[i][j] += ncr[i-1][j-1]; | |
} | |
} | |
} | |
i128 gcd(i128 a, i128 b){ | |
while(a > 0){ | |
b %= a; | |
swap(a, b); | |
} | |
return b; | |
} | |
void solve(int t){ | |
int n, q; | |
cin >> n >> q; | |
vector<string> students(n); | |
vector<int> score(3); | |
for(int i = 0; i < n; i++){ | |
cin >> students[i] >> score[i]; | |
} | |
vector<int> omask(q, 0); | |
for(int i = 0; i < n; i++){ | |
for(int j = 0; j < q; j++){ | |
if(students[i][j] == 'T'){ | |
omask[j] ^= (1 << i); | |
} | |
} | |
} | |
vector<int> mask = omask; | |
for(int j = 0; j < q; j++){ | |
if(mask[j] >> 2){ | |
mask[j] ^= 7; | |
} | |
assert(mask[j] < 4); | |
} | |
auto get_ways = [&](vector<int> freq, vector<int> des) -> i128 { | |
i128 ans = 0; | |
for(int a = 0; a <= freq[0]; a++){ | |
for(int b = 0; b <= freq[1]; b++){ | |
for(int c = 0; c <= freq[2]; c++){ | |
int d = freq[3] - (des[0] - (a+(freq[1]-b)+c)); | |
if(d < 0 || d > freq[3]) continue; | |
int p0 = a+(freq[1]-b)+c+(freq[3]-d); | |
int p1 = a+b+(freq[2]-c)+(freq[3]-d); | |
int p2 = a+b+c+d; | |
if(n > 0 && p0 != des[0]) continue; | |
if(n > 1 && p1 != des[1]) continue; | |
if(n > 2 && p2 != des[2]) continue; | |
i128 z = ncr[freq[0]][a] * ncr[freq[1]][b] * ncr[freq[2]][c] * ncr[freq[3]][d]; | |
ans += z; | |
} | |
} | |
} | |
return ans; | |
}; | |
vector<int> mask_freq(4, 0); | |
for(int m : mask) mask_freq[m]++; | |
i128 total = get_ways(mask_freq, score); | |
i128 best_score = 0; | |
vector<int> choice(4, 0); | |
for(int m = 0; m < 4; m++){ | |
if(mask_freq[m] == 0) continue; | |
vector<int> new_freq = mask_freq; | |
vector<int> new_score = score; | |
if(!(m & 1)) new_score[0]--; | |
if(!(m & 2)) new_score[1]--; | |
new_score[2]--; | |
new_freq[m]--; | |
i128 res = get_ways(new_freq, new_score); | |
if(res >= total - res){ | |
choice[m] = 0; | |
} else { | |
choice[m] = 1; | |
res = total - res; | |
} | |
best_score += res * i128(mask_freq[m]); | |
} | |
i128 g = gcd(total, best_score); | |
string ans = str(best_score / g) + "/" + str(total / g); | |
cout << "Case #" << t << ": "; | |
string resp; | |
for(int i = 0; i < q; i++){ | |
cout << "FT"[choice[mask[i]] ^ (omask[i] >> 2)]; | |
} | |
cout << " "; | |
cout << ans << '\n'; | |
} | |
int main(){ | |
ios_base::sync_with_stdio(false), cin.tie(nullptr); | |
init(); | |
int T; | |
cin >> T; | |
for(int t = 1; t <= T; t++) solve(t); | |
} |
In this problem we want to maximize our expected score. Let be the probability of question 's answer being T
, and let and be the sets of questions we answer with T
and F
, respectively. By linearity of expectation, the expected score to maximize can be written as
We operate with fractions throughout most of the proposed solutions. As noted in the sample, the needed numbers may exceed 64 bits for Test Set 3, and potentially for Test Set 2 as well, depending on the exact implementation of the algorithm and the fraction operations. It is absolutely possible to solve Test Set 2 with simply 64-bit integers and Test Set 3 with just 128-bit integers. Our most popular languages all support this in some way: C and C++ have __int128
support, Java and C# have BigInteger
, JavaScript has BigInt
, Bash has bc
, and Python, Ruby and Haskell have native long integer support. We usually strive to make most of our problems solvable with just 64-bit integer arithmetic, but in this case, limiting the number of questions so much would allow suboptimal solutions in fast languages to pass Test Set 3.
Notice that we can have information of or other students in the first two test sets, and also in the last test set. We could solve each number of students independently, but there is no need for that. Adding a student with the same answers and score as a student in the input results in a completely equivalent case, so we can always assume that there are a maximum number of students by copying any student the needed number of times.
Test Set 1
In Test Set 1, the number of questions is small enough that we can simply enumerate all possible sequences of answers, and filter out those who are inconsistent with the input (i.e., those for which one of the students would obtain a different score than they actually got). From the consistent ones, we can estimate the s above as the ratio between the number of sequences that answer T
to question , over the total. Then, we can simply choose to answer T
to those questions with and F
to those with . We can answer the questions with either way.
Test Set 2
In Test Set 2 is large, so we cannot enumerate the sequences of answers. We can, on the other hand, figure out the probabilities in a different way, and then proceed as before with choosing the answers by comparing those values to .
An insight-based solution
One way to solve Test Set 2 is by splitting the questions into types. If two questions and received the same answer from each student, then by symmetry . Then, let be equal to the probability of a question's answer being T
given that the first student answered and the second student answered to it. By the first observation, each is equal to one of the values , , or . Moreover, by the symmetry of complementing answers, and . Therefore, we can express every as a linear function of up to two variables and . That means we can express the expected score of both students as linear functions on those two variables too. Given that their expected score should match their actual score, that gives us two equations with two unknowns. We can derive the real values of and from that system of equations. With every calculated, we can simply choose, for each question, an answer that has maximum probability, as in the solution for Test Set 1.
Notice that there are possible cases depending on how our two variables compare with (if one is exactly that means two cases are equivalent and if both are then all cases are equivalent). The cases exactly match with either answering the same as one of the students, or answering the opposite of one of the students. We can use this observation to greatly simplify the implementation as the score of a sequence given by a student is given to us, and the score of the complement of the answers of student is , so we can easily obtain the scores of the options and pick a highest one.
A more competitive-programming-standard solution
In case of having students, we can use dynamic programming to calculate the probability of each question having a particular answer. We compute the recursive function defined as "how many ways are there to answer questions such that student gets exactly of them right and student gets exactly of them right?" We can define that function recursively as
By memoizing that function, we can compute it in time . We can calculate the probability of question 's answer being T
as
If we add only the first observation of the insight-based solution, we can notice that two questions that were answered the same by both students have identical probabilities. Then, we only need to calculate the probability of up to question types (in the notation of the previous solution, we use dynamic programming to calculate all the s). This improves the overall running time to , which fits better within the time limit. An observation about complement could further reduce this to only question types, but that does not change the time complexity and it is not needed to pass this test set.
Test Set 3
The dynamic programming solution for Test Set 2 can be generalized to Test Set 3 by adding an additional score as another parameter to the recursive function. However, the additional dimension and larger limit for can easily make such solutions too slow.
Combining the full insights of the first solution to Test Set 2 with the solution to Test Set 1 works, though: there are probability variables , and pairs of complementary variables have complementary probabilities, so we only care about different ones.
Let us call the subindex of the variables (the part) the "type" of a question. Let us number the types through in any order. If there are questions of type , we can use quadruples with for all to represent sequences of answers that answer T
to exactly questions of type . We know that there are
There are at most quadruples to check. This makes the time complexity of the algorithm , but the constant is pretty significant, and a good implementation runs comfortably in time.
But wait! We can refine this solution even more by using the solution for Test Set 2 that ends with solving the system of equations! We can express the score of each student as a linear function of and . That gives us a system of equations and unknowns. That means that we only need to try all possible values for one of the and then simply solve the system to find unique values for the other three. That refines the solution above to requiring only time.