Exam Manipulation ⧉

This is problem seems tricky at first, but the constrained input size (up to 10 questions per test) allows us to simply use brute force to find a solution. We can generate all possible answer keys and find which one renders the optimal score. Keys are generated by counting up from 0 to 2^k, where k is the number of questions on the test. Using the current count as a bit mask, we match its set bits against T's and unset bits against F's.

exam.cpp

exam.py

#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
const int kMaxStudents = 1000;
const int kMaxQuestions = 10;
const int kMaxKeys = 1 << kMaxQuestions;
int withKey[kMaxStudents][kMaxKeys];
int worstScore[kMaxKeys];
int main() {
    int n,k;
    cin >> n >> k;
    const int kPossibleKeys = 1 << k;
    for (int i = 0; i < kPossibleKeys; ++i) {
        worstScore[i] = 11;
    }
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int key = 0; key < kPossibleKeys; ++key) {
            withKey[i][key] = 0; // initialize
            for (int question = 0; question < k; ++question) {
                bool trueOnKey = key & 1 << question;
                if ((s[question] == 'T' && trueOnKey) || (s[question] == 'F' && !trueOnKey)) {
                    withKey[i][key]++;                        
                }
            }
            worstScore[key] = min(worstScore[key], withKey[i][key]);
        } 
    }
    cout << *max_element(begin(worstScore), end(worstScore)) << '\n';
}

If you found this solution helpful, consider leaving a star!