[Solution] Cheating Detection Solution Code Jam 2021

Table of Contents

Problem

100 players are competing in a 10000-question trivia tournament; the players are numbered from 1 to 100. Player ii has a skill level of SiSi and question jj has a difficulty level of QjQj. Each skill level and each question difficulty are chosen uniformly at random from the range [−3.00,3.00][−3.00,3.00], and independently of all other choices. For example, a player can have a skill level of 2.478532.47853 and a question can have a difficulty level of −1.4172−1.4172.

When player ii tries to answer question jj, the probability that they answer it correctly is f(Si−Qj)f(Si−Qj), where ff is the sigmoid function:f(x)=11+e−xf(x)=11+e−x

Notice that 0<f(x)<10<f(x)<1 for all xx, so f(Si−Qj)f(Si−Qj) is always a valid probability. Each of these answer attempts is chosen at random independently of all other choices.

There is one exception: exactly one of the players is a cheater! The cheater is chosen uniformly at random from among all players, and independently of all other choices. The cheater behaves as follows: before answering each question, they flip a fair coin. If it comes up heads, they do not cheat and the rules work as normal. If it comes up tails, they secretly look up the answer on the Internet and answer the question correctly. Formally, they decide whether to cheat at random with 0.50.5 probability for each question, independently of all other choices.

The results of a tournament consist of only the per-question results (correct or incorrect) for each player. Apart from the general description above, you do not know anything about the skill levels of the players or the difficulties of the questions.

You must correctly identify the cheater in at least PP percent of the test cases. That is, you must succeed in at least P⋅T/100P⋅T/100 out of TT cases.

Input

The first line of the input gives the number of test cases, TT. The second line of the input gives the percentage of test cases, PP, that you must answer correctly for your solution to be considered correct. TT test cases follow. Each case consists of 100 lines of 10000 characters each. The j-th character on the i-th line is 1 if the i-th player answered the j-th question correctly, or 0 if they answered it incorrectly.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the number of the cheater (with player numbers starting from 1).

Limits

Time limit: 60 seconds.
Memory limit: 1 GB.
T=50T=50.

Test Set 1 (Visible Verdict)

P=10P=10.

Test Set 2 (Visible Verdict)

P=86P=86.

Sample

Sample Input: given in code jam exam

Sample Output

Case #1: 59

Notice that the sample input uses T=1T=1 and P=0P=0 and therefore does not meet the limits of any test set. The sample output for it is the actual cheater.

Solution:

#include <bits/stdc++.h>

using namespace std;

void solve(int t){
int n = 100;
int q = 10000;
vector a(n);
for(string& s : a) cin >> s;
vector psolved(n), qsolved(q);
for(int i = 0; i < n; i++)

for(int j = 0; j < q; j++)

{ if(a[i][j] == ‘1’){ psolved[i]++; qsolved[j]++; } } vector pord(n);
vector qord(q);
for(int i = 0; i < n; i++)

pord[i] = i;

for(int i = 0; i < q; i++)

qord[i] = i;

sort(pord.begin(), pord.end(), [&](int x, int y)

{ return psolved[x] < psolved[y]; }); sort(qord.begin(), qord.end(), [&](int x, int y){ return qsolved[x] > qsolved[y];
});
vector score(n);
for(int i = 0; i < n; i++)

{ int n0 = 0; int n1 = 0; int inv = 0;

for(int j = 0; j < q; j++)

{ if(a[pord[i]][qord[j]] == ‘1’)

{ n1++; inv += n0; } else { n0++; } }

double f = inv; f /= n0; f /= n1; score[i] = f; }

int best = 0; for(int i = 0; i < n; i++)

{ if(score[i] > score[best]) best = i;
}
cout << “Case #” << t << “: “;
cout << (pord[best] +1) << ‘\n’;
}

int main(){
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int T, P;
cin >> T >> P;
for(int t = 1; t <= T; t++) solve(t);
}