Move Fast

문제

• 문제 링크
• 문제 설명: 지원자가 지원서에 입력한 4가지의 정보(개발언어, 직군, 경력, 소울푸드)와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 반환하는 함수 작성
• 입력
  • info 배열의 크기는 1 이상 50,000 이하
  • 개발언어는 cpp, java, python 중 하나
  • 직군은 backend, frontend 중 하나
  • 소울푸드는 chicken, pizza 중 하나
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수
  • query 배열의 크기는 1 이상 100,000 이하
  • query의 각 문자열은 "[조건] X" 형식
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미
• 출력: 매 query마다 조건을 만족하는 사람 수를 배열에 담아 반환

풀이

• query 배열의 크기가 최대 10만이기 때문에 매 쿼리에 info 배열을 순회하는 것은 시간초과가 발생한다. 따라서 O(logN) 으로 조건을 만족하는 사람을 찾도록 info 배열을 전처리 해주어야 한다.
• logN 의 시간으로 탐색하는 방법은 이진 탐색이 있다. 이진 탐색은 탐색 대상이 오름차순으로 정렬되었음을 가정한다.
• 4가지 지원자의 정보로 조합 가능한 조건들은 최대 (3+1) * (2+1) * (2+1) * (2+1) = 4 * 3 * 3 * 3 = 108가지이다. 1을 더한 것은 '-'을 포함한 것이다.
• map<string, vector<int>> 자료형을 이용해서 108가지의 조건 각각을 키로 가지고 조건에 해당되는 지원자의 점수를 값으로 가지게 하면 정렬 후 이진 탐색으로 원소의 위치를 알아내서 컨테이너 끝하고 오프셋으로 사람 수를 계산할 수 있게 된다.
  • 시간 절약을 위해 unordered_map 을 활용하기로 했다.

#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 각 조건과 해당되는 점수 목록을 저장할 자료구조
unordered_map<string, vector<int>> m;

// 지원자 정보로 가능한 조건을 조합
void dfs(int pos, vector<string>& key, int& score, string s) {
    if (pos == key.size()) {
        m[s].push_back(score); // 생성된 조건마다 지원자의 점수 저장
        return;
    }
    dfs(pos + 1, key, score, s + key[pos]);
    dfs(pos + 1, key, score, s + "-");
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<string> key(4);
    int score;
    for (auto& i : info) {
        istringstream iss(i);
        iss >> key[0] >> key[1] >> key[2] >> key[3] >> score;
        dfs(0, key, score, ""); // 가지고 있는 조건들로 가능한 조건 조합을 생성
    }
    
    for (auto it = m.begin(); it != m.end(); it++)
        sort(it->second.begin(), it->second.end()); // 각 조건마다 지원자의 점수들을 오름차순 정렬
    
    for (auto& q : query) {
        istringstream iss(q);
        string tmp; // and
        iss >> key[0] >> tmp >> key[1] >> tmp >> key[2] >> tmp >> key[3] >> score;
        auto it = m.find(key[0] + key[1] + key[2] + key[3]);
        if (it == m.end()) answer.push_back(0); // 없는 조건이면 0명
        else { // 있는 조건이면 이진 탐색으로 오프셋 계산
            // lower_bound는 score보다 이상인 값들 중 가장 작은 값(하한)의 위치를 반환
            auto vit = lower_bound(it->second.begin(), it->second.end(), score);
            int num_applicants = it->second.end() - vit;
            answer.push_back(num_applicants);
        }
    }
    return answer;
}

문제

• 문제 링크
• 문제 설명: 각 손님이 이전에 주문한 메뉴 조합들(orders)과 앞으로 만들 메뉴 조합들 각각의 단품 메뉴 개수 목록(course)이 주어질 때, 이전에 2번 이상 주문된 단품 메뉴들 중 원하는 개수만큼 메뉴를 조합할 때 각 코스별 가장 많이 주문된 것들을 반환하는 함수를 작성하기
• 입력
  • orders 배열의 크기는 2 이상 20 이하
  • orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열
  • 각 문자열은 알파벳 대문자로만 구성
  • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않음
  • course 배열의 크기는 1 이상 10 이하
  • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬
  • course 배열에는 같은 값이 중복해서 들어있지 않음
• 출력
  • 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 반환
  • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 함
  • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담을 것

풀이

• 먼저 단품 메뉴마다 몇 명이 주문했는지 알기 위해 단품 메뉴별 주문한 사람 수(freq)를 구함
• course 목록에 있는 개수대로 메뉴를 조합. (조합을 구현할 때는 항상 DFS)
  • dfs(pos, comb, ...) 에서 pos가 필요한 이유: 메뉴 A -> 메뉴 B 와 메뉴 B -> 메뉴 A 는 동일하며 중복을 없애기 위해 다음 호출 시 pos 를 1씩 증가시켜준다. 게다가 오름차순 정렬도 자연스레 된다.
• 메뉴를 조합한 후 결과가 여러 개일 때 가장 많이 주문한 것들을 구해야 함.
  • orders의 원소는 알파벳 대문자만 포함하기 때문에 단품 메뉴는 최대 26개
  • orders 배열의 크기는 최대 20이므로 각 메뉴를 주문한 최대 사람 수도 20이 된다.
  • 32보다 작은 숫자이므로 32비트 정수형 변수에 비트로 저장하면 AND 연산으로 메뉴 A와 메뉴 B를 주문한 사람을 쉽게 알아낼 수 있게 된다.
    • freq[i] 는 i번 메뉴 (=메뉴 i + 'A')를 주문한 사람의 인덱스번째 비트를 1로 가짐
    • orders를 순회할 때마다 OR 연산으로 해당 단품 메뉴를 주문한 사람 목록을 쉽게 구할 수 있다.
    • __builtin_popcount() 를 활용하여 1-bit의 개수를 얻으면 주문한 사람 수도 쉽게 얻을 수 있다.
  • course 배열마다 dfs를 호출할 필요 없이 dfs를 1번 호출해서 단품 메뉴의 조합 개수를 늘릴 때마다 course에 있는 개수인지 검사해서 있으면 해당 메뉴 조합을 주문한 사람 수를 저장
    • 메뉴 A와 메뉴 B를 주문한 사람의 목록은 freq[0] & freq[1] 을 해서 구하면 된다. dfs 를 재귀호출할 때마다 인자로 넘기기
  • 메뉴 조합의 개수별로 dfs로 구한 전체 메뉴 조합을 나눈다. set 을 쓰면 삽입하면서 주문한 사람수 오름차순으로 자동 정렬할 수 있다.
  •  각 조합 개수마다 가장 많이 주문한 것들을 answer 배열에 저장한다.
• 정답 코드

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

void dfs(int pos, string comb, int found, vector<int>& freq,
         vector<int>& course, vector<pair<int, string>>& ret)
{
    // course 에 있는 메뉴 조합의 개수이면
    if (binary_search(course.begin(), course.end(), (int)comb.size())) {
        // 해당 조합에 포함된 단품메뉴를 주문한 사람 수 계산
        int num_found = __builtin_popcount(found);
        // set에 오름차순을 위해 -1을 곱함
        if (num_found > 1) ret.emplace_back(-num_found, comb);
    }
    
    for (int i = pos; i < 26; i++)
        if (__builtin_popcount(freq[i]) > 1) // 단품 메뉴 주문 수 > 1 일 때만 포함
            dfs(i+1, comb + char(i+'A'), found & freq[i], freq, course, ret);
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    
    // 주문한 사람 목록 구하기
    vector<int> freq(26, 0);
    for (int i = 0; i < orders.size(); i++)
        for (int j = 0; j < orders[i].size(); j++)
            freq[orders[i][j]-'A'] |= (1 << i);
    
    // 모든 가능한 메뉴 조합 구하기
    vector<pair<int, string>> ret;
    dfs(0, "", (1<<21)-1, freq, course, ret);
    
    // 조합 메뉴 개수별로 조합 목록 나누기
    set<pair<int,string>> combinations[11];
    for (int i = 0; i < ret.size(); i++)
        combinations[ret[i].second.length()].insert(ret[i]);
    
    // 개수마다 최대 주문량을 가진 메뉴 조합 저장
    for (int i = 2; i < 11; i++) {
        if (combinations[i].size() == 0) continue;
        auto it = combinations[i].begin();
        int max_orders = it->first;
        while (it != combinations[i].end() and it->first == max_orders) {
            answer.push_back(it->second);
            it++;
        }
    }
    
    // 정렬해서 반환
    sort(answer.begin(), answer.end());
    return answer;
}

문제

• 문제 링크
• 문제 설명: 문자열을 w개 단위로 잘라서 압축할 때 가장 짧은 길이를 반환 (문자열 길이는 1000 이하, 알파벳 소문자만 포함)
  • 예를 들어, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 된다.
• 참고: 문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다.

풀이

• 단순하게 생각하기: 문자 1개 단위로 압축했을 때 다음과 같은 코드를 실행하면 된다.

int compress(const string& s, int& n) {
    int len = 0;
    for (int i = 0, num_units = 1; i < n; i++) {
        if (s[i] == s[i+1]) num_units++; // 문자가 같으면 압축된 문자 단위 개수 증가
        else if (cnt > 1) { // 이전에 압축된 개수가 2개 이상이면
            len += to_string(num_units).size() + 1; // 압축된 길이를 계산 
            num_units = 1; // 문자 단위 개수 갱신
        } else len++; // 이전에 압축된 개수가 1인데 더 압축할 게 없으면 길이만 늘림
    }
    return len;
}

• 더 나아가기: 문자 w개 단위로 압축할 경우 w개의 문자들이 연속되는지 검사하고 n 이 w로 나누어 떨어지지 않는 부분을 예외처리하면서 연속되지 않으면 w만큼 길이를 늘려주면 위와 동일하게 동작하는 코드를 작성할 수 있다.

int compress(const string& s, int& n, int& w) {
    int len = 0;
    for (int i = 0, j = w, num_units = 1; i < n; i+=w, j+=w) {
        if (s.substr(i, w) == s.substr(j, w)) num_units++; // 부분 문자열이 연속되면 개수 증가
        else if (num_units > 1) { // 개수가 1보다 크면 압축된 길이 추가
            len += to_string(num_units).size() + w;
            num_units = 1;
        } else len += i + w > n ? n % w : w; // 연속 개수가 1인데 압축할 게 없으면 남은 길이 추가
    }
    return len;
}

• 길이가 1000 이하이기 때문에 compress의 시간복잡도가 O(N) 인 걸 감안하면, 브루트-포싱으로 매 w개 만큼 압축을 시도해서 최소 길이를 탐색해도 시간 초과가 발생하지 않는다. 참고로 w의 최대 길이는 주어진 문자열의 길이의 절반이다.
• 정답 코드

#include <string>
#include <vector>
using namespace std;

int compress(const string& s, int& n, int& w) {
    int len = 0;
    for (int i = 0, j = w, num_units = 1; i < n; i+=w, j+=w) {
        if (s.substr(i, w) == s.substr(j, w)) num_units++;
        else if (num_units > 1) {
            len += to_string(num_units).size() + w;
            num_units = 1;
        } else len += i + w > n ? n % w : w;
    }
    return len;
}

int solution(string s) {
    int n = s.size();
    s += string(n >> 1, '.'); // 맨 끝에서 연속되는지 검사할 때 OOB 방지를 위해 패딩을 추가
    int answer = n;
    for (int w = 1; w <= n >> 1; w++) {
        answer = min(answer, compress(s, n, w));
    }
    return answer;
}

Reversort

• 문제 설명: 아래와 같은 알고리즘으로 주어진 배열을 정렬하면 된다. 여기서 1번 뒤집을 때 원소의 개수가 비용이 되며, 오름차순 정렬이 끝날 때까지 모든 비용의 합을 출력하면 된다.

Reversort(L):
  for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

• 접근법: N <= 100 이므로, 슈도코드를 있는 그대로 작성했다.
• 시간 복잡도: O(N^2)

int solve() {
    int N;
    cin >> N;
    vector<int> v(N);
    for (int i = 0 ; i < N; i++)
        cin >> v[i];
    int ans = 0;
    for (int i = 0; i < N-1; i++) {
        int minIdx = i, minVal = v[i];
        for (int j = i; j < N; j++) {
            if (minVal > v[j]) {
                minVal = v[j];
                minIdx = j;
            }
        }
        reverse(v.begin() + i, v.begin() + minIdx + 1);
        ans += minIdx - i + 1;
    }
    return ans;
}

Moons and Umbrellas

• 문제 설명: C, J, ? 로 이루어진 문자열이 주어질 때, ?를 C또는 J로 대체해서 비용을 계산했을 때 가장 작은 비용이 나오게 하는 문자열을 출력하면 된다. X는 "CJ"가 나타날 때의 비용, Y는 "JC"가 나타날 때의 비용이다.
• 접근법: ?를 한 글자씩 처리하지 않고 ?...?로 이루어진 덩어리 단위로 처리했다. Test Set 2까지는 1 <= X, Y <= 100 이므로, 비용이 나오지 않도록 문자를 대체해야 한다. "C...C"또는 "J...J"를 많이 만들면 비용이 들지 않기 때문에 ?...? 덩어리 양 옆에 배치한 문자가 다른 경우에만 비용을 계산하고, 나머지는 건너뛰었다. ?...? 덩어리가 문자열의 앞뒤로 위치할 때도 마찬가지로 건너뛴다.
• 시간 복잡도: O(N)

int solve() {
    int X, Y;
    string S;
    cin >> X >> Y >> S;
    int cost = 0;
    int s = 0, e = S.size() - 1;
    // 문자열 양 끝에 ?...? 덩어리는 스킵한다.
    while (s < S.size() and S[s] == '?') s++;
    while (e >= 0 and S[e] == '?') e--;
    // S[s] != '?' and S[e] != '?'
    for (int i = s; i < e; i++) {
        if (S[i] != '?' and S[i+1] != '?' and S[i] != S[i+1]) {
            // "CJ", "JC"가 나오는 경우 비용 계산
            if (S[i] == 'C' and S[i+1] == 'J') cost += X;
            if (S[i] == 'J' and S[i+1] == 'C') cost += Y;
        } else if (S[i] == '?') {
            int j = i+1;
            // ?...? 덩어리 탐색
            while (j < e and S[j] == '?') j++;
            assert(S[i-1] == 'C' or S[i-1] == 'J');
            assert(S[j] == 'C' or S[j] == 'J');
            // ?...? 덩어리 양 끝에 문자가 다르면 비용을 계산한다.
            if (S[i-1] != S[j]) {
                if (S[i-1] == 'C') cost += X;
                else cost += Y;
            }
            // ?...? 덩어리 바로 다음 부터 탐색시작.
            i = j-1;
        }
    }
    return cost;
}

• Test Set 3부터는 해결하지 못한 상태로 대회가 끝났다. (코드잼 예선은 30점 이상만 되면 통과가 되서, 그냥 다른거 하러 갔다ㅜㅜ)
  • Test Set 3에서는 -100 <= X, Y <= 100 의 범위를 가진다. X+Y < 0인 경우 "CJC" 또는 "JCJ"를 많이 만들면 되며, X+Y > 0 인데 둘 중 하나가 음수이면 음수가 되는 문자열을 많이 만들면 된다. 그러나, 경우의 수가 너무 많고 (길이도 봐야하고 문자도 봐야하고..) 시간이 오래 걸려서 결국 풀이를 봤다.
  • 풀이에 따르면 이 문제는 "동적 계획법"으로 풀어야 된다고 한다. dp[1000][2]에 캐싱할 때 dp[i][0]은 i번째 문자까지 봤을 때 현재 문자가 C일 때의 최소 비용이고 dp[i][1]은 i번째 문자까지 봤을 때 현재 문자가 J일 때의 최소비용이다. 당연히 i번째 문자가 C일 때 dp[i][1] 은 올 수 없는 경우이기 때문에 INF 로 예외 처리를 해주어야 한다. 반대 경우도 마찬가지.
  • 시간 복잡도: O(N)

int solve() {
    int X, Y;
    string S;
    cin >> X >> Y >> S;
    const int INF = 1e9;
    /*
     dp[i][0] :=
        S[i] == '?' 이면 C일 때 최소 비용
        S[i] == 'C' 이면 min(dp[i-1][0], dp[i-1][1] + Y)
        S[i] == 'J' 이면 INF
     dp[i][1] :=
        S[i] == '?' 이면 J일 때 최소 비용
        S[i] == 'C' 이면 INF
        S[i] == 'J' 이면 min(dp[i-1][0] + X, dp[i-1][1])
     */
    int dp[1000][2];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = dp[0][1] = INF;
    if (S[0] == 'C') dp[0][0] = 0;
    else if (S[0] == 'J') dp[0][1] = 0;
    else dp[0][0] = dp[0][1] = 0;
    for (int i = 1; i < S.size(); i++) {
        dp[i][0] = dp[i][1] = INF;
        for (int j = 0; j < 2; j++) { // 이전 글자가 C인지, J인지
            for (int k = 0; k < 2; k++) { // 현재 글자가 C일 때와 J일 때의 최소비용 계산
                // dp[i][1]를 계산하는데 S[i] == 'C' 이면 INF
                if (S[i] == 'C' and k == 1) continue;
                // dp[i][0]를 계산하는데 S[i] == 'J' 이면 INF
                if (S[i] == 'J' and k == 0) continue;
                int add = 0; // 글자가 같으면 0
                if (j != k) { // 이전 글자와 현재 글자가 다르면 비용 추가
                    add = k == 1 ? X : Y;
                }
                // 이전 글자가 무엇인지에 따라 비용 갱신 (총 4번)
                dp[i][k] = min(dp[i][k], dp[i-1][j] + add);
            }
        }
    }
    return min(dp[S.size()-1][0], dp[S.size()-1][1]);
}

Reversort Engineering

• 문제 설명: 수열의 크기 N과 비용 C가 주어졌을 때 Reversort를 해서 정확히 C의 비용으로 오름차순 정렬이 되는 원래 수열을 구해야 한다. 답이 여러 개이면 아무거나 출력하면 된다.
• 접근법: Reversort는 첫번째 숫자부터 마지막 숫자까지 다 뒤집기를 시도한다. 현재 숫자가 가장 작은 숫자이면 뒤집기는 자기자신과 하므로 1만큼의 비용이 든다. 기존 알고리즘과 반대로 동작하는 알고리즘을 짜야될 것 같은데 수학적으로 풀기에는 머리가 안 돌아가서 그냥 naive하게 BFS로 모든 경우의 수를 탐색하는 방식으로 해결했다. 오름차순 정렬 상태인 수열에서 시작하며, 마지막 숫자부터 첫번째 숫자 순으로 뒤집기를 해서 다 뒤집고 난 뒤 총 비용이 C이면 그 때 배열의 상태를 반환하도록 했다. BFS를 수행할 노드는 비용과 배열의 상태, 뒤집기를 시작할 숫자 인덱스를 포함한다.
  • 여기서 뒤집기 할 시작 위치가 끝 인덱스 -> 시작 인덱스 순이고, 뒤집기는 reversort 와 동일하게 동작한다.
• 시간 복잡도: O(N^2 * N!)
  • 노드는 트리 구조가 되며, depth 가 올라갈 때마다 (N - depth) 개씩 노드가 늘어난다. 배열을 찾지 못하는 최악의 경우 N!개의 노드를 탐색해야 한다.
  • 매 노드마다 뒤집기 구간을 늘려서 뒤집기 연산(=Reversort)을 해주어야 하므로 N^2 만큼의 비용이 든다.
  • Test Set 2는 N이 최대 100이기 때문에 메모리/시간 초과로 풀지 못했다.

struct State {
    int start; // start index to reverse
    int cost;
    vector<int> A;
    State(int s, int c, vector<int>& a): start(s), cost(c), A(a) {}
};

int N, C;

vector<int> bfs(vector<int>& A) {
    if (C < N-1) return vector<int> ();
    queue<State*> q;
    // 마지막 숫자는 뒤집기하지 않으므로 비용 0에서 시작
    q.push(new State(N-1, 0, A));
    while (!q.empty()) {
        State* state = q.front();
        q.pop();
        // 시작 위치까지 왔으면 비용을 계산해보고 같으면 현재 배열 반환
        if (state->start == 0) {
            if (state->cost == C) return state->A;
            continue;
        }
        // 다음 노드는 현재 시작 위치 - 1 에서 뒤집기를 시작
        int start = state->start - 1;
        // 자기 자신도 뒤집기
        q.push(new State(start, state->cost+1, state->A));
        // 뒤집을 구간을 1씩 늘리면서 비용이 C보다 작은 것들만 큐에 삽입
        for (int end = start+1; end < N; end++) {
            vector<int> a = state->A;
            int cost = state->cost + (end - start + 1);
            if (cost > C) continue;
            reverse(a.begin() + start, a.begin() + end + 1);
            q.push(new State(start, cost, a));
        }
    }
    // 비용 C를 정확히 만들 수 없으면 빈 배열 반환
    return vector<int> ();
}

void solve() {
    cin >> N >> C;
    vector<int> A(N);
    for (int i = 0 ; i < N; i++) A[i] = i+1;
    vector<int> ans = bfs(A);
    if (ans.size() == 0) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        for (auto& x : ans) cout << x << " ";
        cout << endl;
    }
}

• Test Set 2 에서는 수학적인 접근이 필요하다.
  • Reversort는 i=0부터 i=n-2까지 [i:n-1] 구간 중 최솟값이 있으면 그 최솟값의 위치 min_idx까지의 구간 [i:min_idx]를 뒤집는다.
  • 비용 c로 어떤 구간 [a:b]을 뒤집는 연산을 할 수 있는지 알려면 "비용 검사"를 해야하는데, 구간의 크기 N에 대해 각 원소를 1번씩만 뒤집게 되면 최소 비용 (N-1)이 나온다. 반대로, 항상 [i:n-1] 구간을 뒤집게 되면 비용은 n + (n-1) + (n-2) + ... + 2 가 된다. (마지막 원소는 뒤집지 않으므로 +1 하지 않음)
  • 결국 크기가 N인 구간을 뒤집는 비용 c는 N-1 <= c <= (N*(N+1)/2 - 1) 의 범위를 항상 가져야 한다.
    • 비용 구간에 맞는 c가 주어지면 오름차순 정렬된 N개의 원소에서 반드시 뒤집기 연산을 비용 c만큼 할 수 있음을 의미한다. 당연히 정답이 여러 개일 수 있는데, 아무 순서나 반환해도 되니 순서는 고려할 필요가 없다.
  • 주어진 N과 C에서 비용 검사를 해서 반드시 가능한 경우에 대해서만 답을 찾을 수 있다.
  • 그러나, 가능한 경우의 수열을 찾으려면 끝에서부터 한 번씩 뒤집어봐야 한다는 사실은 변하지 않는다. 이전 방법에서는 모든 경우의 수를 찾았으나, 비용 검사를 활용하면 뒤집을 때마다 뒤집고 남은 비용으로 남은 구간들을 뒤집을 수 있는지 검사함으로써 정답을 찾을 수 있게 된다.
  • 주의할 점은 최초로 N과 C를 검사할 때와는 다른 수식을 사용해야 된다는 점이다. 그 이유는 뒤집고나서도 뒤집기 시작 위치 i 이전 인덱스들은 n-1 번째 원소까지 뒤집을 수 있기 때문이다.
    • 어떤 수식을 사용해야 하는가? 뒤집기 연산의 최소 비용과 최대 비용을 구할 때의 원리를 잘 되짚어 보자.
    • 뒤집기 연산의 최소 비용은 매 인덱스에서 자기자신만 뒤집을 때 비용 1이 더해진 것이다.
    • 뒤집기 연산의 최대 비용은 매 인덱스에서 항상 자기 자신부터 마지막 원소까지 뒤집을 때의 비용이 더해진 것이다.
  • 다음과 같이 귀납법으로 비용 검사를 하는 수식을 얻을 수 있다.
    • 아무것도 뒤집지 않은 상태에서의 비용
      • 최댓값: n + (n-1) + (n-2) + ... + 2 = n * (n+1) / 2 - 1
      • 최솟값: n - 1 (마지막 원소 제외)
    • [n-2:n-1] 사이의 구간을 뒤집으면 남는 비용
      • 최댓값: n + (n-1) + (n-2) + ... + 2 - 2 = n * (n+1) / 2 - 1 - 2 -> 구간의 최대 크기 2만큼 뒤집는 경우를 빼줌
      • 최솟값: n-2 -> 자기 자신을 뒤집는 경우, 1을 빼줌
    • [n-3:n-1] 사이의 구간을 뒤집으면 남는 비용
      • 최댓값: n + (n-1) + (n-2) + ... + 2 - 2 - 3 = n * (n+1) / 2 - 1 - 2 - 3 -> 구간의 최대 크기 3만큼 뒤집는 경우를 누적해서 빼줌
      • 최솟값: n - 3 -> 자기 자신을 뒤집는 경우, 1을 누적해서 빼줌
    • [i:n-1] 사이의 구간을 뒤집으면 남는 비용
      • 최댓값: n + (n-1) + (n-2) + ... + 2 - (2 + 3 + ... + (n-i)) = n + (n-1) + ... + (n-i+1) -> 구간의 최대 크기 (n-i)만큼 뒤집는 경우를 누적해서 빼줌
      • 최솟값: i
  • n-2 인덱스부터 0까지 계산할 때 비용의 최댓값이 누적해서 빠져야 된다는 사실을 주의해야 한다. 마지막 귀납법으로 다음과 같이 최댓값 공식을 얻을 수 있다.

                                                n * (n+1) / 2 - (n-i)*(n-i+1) / 2 = (n*(n+1) - (n-i)*(n-i+1)) / 2

                                                = (n*n + n - (n*n-n*i+n-n*i+i*i-i))/2 = (2*n*i-i*i+i))/2 = i*(2*n-i+1)/2

• 위에서 얻은 수식에서 작은 예제로 정당성을 증명할 수 있다.
  • (예제) n = 4, c = 6
  • 이미 정렬된 배열에서 시작하므로 인덱스와 원소는 다음과 같다
    • i : 0 1 2 3 -> A[i]: 1 2 3 4 
  • i=2, L=1, C=6-1=5 -> [2:3] 사이의 구간을 뒤집으면 비용 5로 나머지를 뒤집을 수 있는가? 5 > 2 && 5 < 7 (O)
    • 가능하니, 구간 [i:i+L-1] = [2:2] 을 뒤집는다. -> 1 2 3 4
  • i=1, L=1, C=5-1=4 -> 구간 [1:1]을 뒤집으면 이전 위치에서 비용 4로 반드시 뒤집을 수 있는가? 4 > 1 && 4 <= 4 (O)
    • 가능하니, 구간 [i:i+L-1] = [1:1] 을 뒤집는다. -> 1 2 3 4
  • i=0, L=1, C=4-1=3 -> 구간 [0:0]을 뒤집으면 이전 위치에서 비용 3로 반드시 뒤집을 수 있는가? 3 > 0 && 3 > 0 (X)
  • i=0, L=2, C=4-2=2 -> 구간 [0:1]을 뒤집으면 이전 위치에서 비용 2로 반드시 뒤집을 수 있는가? 2 > 0 && 2 > 0 (X)
  • i=0, L=3, C=4-3=1 -> 구간 [0:2]을 뒤집으면 이전 위치에서 비용 1로 반드시 뒤집을 수 있는가? 1 > 0 && 1 < 0 (X)
  • i=0, L=4, C=4-4=0 -> 구간 [0:3]을 뒤집으면 이전 위치에서 비용 0로 반드시 뒤집을 수 있는가? 0 >= 0 && 0 <= 0 (O)
    • 가능하니, 구간 [i:i+L-1] = [0:3] 을 뒤집는다. -> 4 3 2 1
  • Reversort PoC) 4 3 2 1
    • i=0, min_idx=2, [0:2] reverse -> 1 2 3 4, cost = 4
    • i=1, min_idx=1, [1:1] reverse -> 1 2 3 4, cost = 1
    • i=2, min_idx=2, [2:2] reverse -> 1 2 3 4, cost = 1
    • total cost = 6
• 시간 복잡도: O(N^2)

bool canReverse(int i, int n, int c) {
    return c >= i and c <= i*(2*n-i+1)/2;
}

void solve() {
    int n, c;
    cin >> n >> c;
    if (c < n-1 or c > n*(n+1)/2-1) {
        cout << "IMPOSSIBLE" << endl;
        return;
    }
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = i+1;
    for (int i = n-2; i >= 0; i--) {
        for (int len = 1; len <= n-i; len++) {
            if (canReverse(i, n, c-len)) {
                reverse(ans.begin() + i, ans.begin() + i + len);
                c -= len;
                break;
            }
        }
    }
    
    for (auto& x : ans) cout << x << " ";
    cout << endl;
}

Median Sort

• 문제 설명: T, N, Q 주어지면, 최대 Q번의 쿼리를 통해 1~N 사이의 숫자가 나열된 수열을 맞춰야 한다. 매 쿼리는 1~N 사이에 서로 다른 3개의 숫자를 질의하고 3개의 숫자 중 중앙값(median)을 알려주는 방식이다.
  • 이 문제는 interactive problem 이라고 코드잼에서 입출력 방식이 기존 문제와는 다르게 진행된다.
  • testing_tool.py 및 interative_runner.py 를 다운받아 알고리즘을 테스트해볼 수 있다.
  • 쿼리는 표준출력으로 질의하면 표준입력으로 응답을 받는다.
• 첫번째 접근법: 5개의 숫자가 있는 수열 {x1, x2, x3, x4, x5}에 대해 질의한 결과가 다음과 같다면,
  • Q1 = {x1, x2, x3} -> median = x1
  • Q2 = {x2, x3, x4} -> median = x2
  • Q3 = {x3, x4, x5} -> median =x3
  • 정답은 2개가 나온다. 하나는 {x4, x2, x1, x3, x5}이고, 다른 하나는 {x5, x3, x1, x2, x4} 이다. 2개 모두 반대순서인거 빼면 동일하다.
  • 여기서 알 수 있는 사실은 수열의 양 끝 숫자는 절대 median 으로 나올 수 없다는 것이다.
  • 모든 3개의 숫자쌍에 대해 질의해서 양 끝 숫자를 알아낸다면, 그 숫자를 제외한 숫자들에 대해 3-숫자쌍을 다시 질의해서 양 끝 숫자를 알아낼 수 있다.
  • N개의 숫자 중에 3개의 숫자를 선택하는 조합의 수만큼 쿼리 비용이 드는데, Test Set 1 은 N이 10 이하이기 때문에 Q의 최댓값이 충분히 커서 가능하다.

int T, N, Q;

int query(int a, int b, int c) {
    cout << a << " " << b << " " << c << endl;
    int median;
    cin >> median;
    return median;
}

void solve() {
    int l = 1, r = N;
    vector<int> ans(N+1); // 정답 수열
    vector<bool> found(N+1, false); // 숫자의 발견 유무
    vector<int> nums; // 남은 수열
    for (int i = 1; i <= N; i++) nums.push_back(i); // 초기에는 모든 숫자를 포함
    while (l < r) {
        vector<bool> chk(N+1, false); // 남은 수열에서 숫자의 발견 유무
        // 남은 수열 중 모든 3개의 숫자쌍의 조합을 질의
        for (int j = 0; j < nums.size(); j++) {
            int a = nums[j];
            for (int k = j+1; k < nums.size(); k++) {
                int b = nums[k];
                for (int v = k+1; v < nums.size(); v++) {
                    int c = nums[v];
                    int median = query(a, b, c);
                    chk[median] = true; // 나온 숫자를 체크
                }
            }
        }
        
        // 남은 수열의 양 끝 숫자 탐색
        int bound[2]; // start, end
        for (int j = 0, k = 0; j < nums.size(); j++) {
            if (!chk[nums[j]]) { // 아직 안나온 숫자이면
                bound[k++] = nums[j];
                found[nums[j]] = true;
            }
        }
        
        if (l == 1) { // 처음에는 정답 수열의 양 끝에 바로 삽입
            ans[l] = bound[0];
            ans[r] = bound[1];
        } else { // 이전 단계에서 양 끝 숫자가 정해지면 질의해서 현재 숫자도 순서에 맞게 삽입
            int median = query(ans[l-1], bound[0], bound[1]);
            if (median == bound[0]) { // l-1, bound[0], ..., bound[1], r+1
                ans[l] = bound[0];
                ans[r] = bound[1];
            } else {                  // l-1, bound[1], ..., bound[0], r+1
                ans[l] = bound[1];
                ans[r] = bound[0];
            }
        }
        l++; r--;

        // 발견한 양 끝 숫자를 제외한 남은 수열 탐색
        nums.clear();
        for (int i = 1; i <= N; i++) {
            if (!found[i])
                nums.push_back(i);
        }
    }

    // 홀수 개이면 1개 남게 되므로 중간에 삽입
    if (l == r) ans[l] = nums[0];
    for (int i = 1; i <= N; i++) cout << ans[i] << " ";
    cout << endl;
    int correct;
    cin >> correct;
    assert(correct == 1);
}

int main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
    cin >> T >> N >> Q;
    while (T--)
        solve();
    return 0;
}

• 두번째 접근법: 이전 방식은 굉장히 naive하기 때문에 Test Set 2 부터는 N <= 50 이므로 최적화를 해주어야 한다. 코드잼 풀이 아이디어는 매 숫자마다 이전에 정해진 수열에 삽입 할 때 이분 탐색을 활용하는 것이다. 남은 수열(=이미 찾은 순서)의 순서는 항상 정답 수열의 순서와 동일하기 때문에 남은 수열의 중앙값, 끝값, 삽입할 숫자에 대해 질의하면 결과를 통해 [0:m]과 [m+1:N] 사이에 어디에 삽입할 숫자가 위치해야 하는지 알 수 있다. (끝값이 아니라 시작값도 상관없다.)
  • 예를 들어, [5,4,2,1,3] 이라는 정답 수열이 있을 때, 처음에는 1,2,3에 대해 질의를 해서 [2,1,3]이라는 수열을 얻게 된다.
  • 다음 숫자 4를 삽입할 때, [2,1,3]의 중앙값인 1과 끝값인 3과 함께 질의하면 그 결과는 query(1,3,4) = 1 이 나오게 된다.
  • 다음 숫자 4는 왼쪽 구간 [2,1]에 존재해야 하는 것을 의미하므로 왼쪽 구간에서 중앙값을 찾아 다시 질의한다.
  • 다음 숫자 5도 마찬가지로 반복한다.
  • 이 방법에서 주의할 점은 base case이다. 1개의 숫자가 남을 때까지 질의하는게 아니라 2개의 숫자가 남을 때 질의해야 코드의 반복을 줄일 수 있다. 위의 예시에서 숫자 4가 들어갈 구간이 [2,1] 로 크기가 2이면 query(2,1,4) 를 1번만 하면 바로 4의 위치를 알 수 있다.
• 시간 복잡도: O(N*log(N))
  • 쿼리 횟수는 N*log2(N) 보다 적다. 계산해보면 매 삽입 시 이진 탐색을 수행하므로 log2(3) + log2(4) + log2(5) + ... + log2(50) = 213.208 이 쿼리 횟수가 되고 Q는 300이하 이므로 충분히 해결할 수 있다.

int query(int a, int b, int c);

void binary_search(int x, vector<int>& ans) {
    int lo = 0, hi = ans.size() - 1;
    // [lo,hi] 만 남았을 때 끝나도록 이분 탐색을 수행
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        int median = query(ans[mid], ans[hi], x);
        if (median == ans[hi]) { // base case: 현재 구간의 끝을 벗어나면
            ans.insert(ans.begin() + hi + 1, x); // hi + 1 위치에 항상 삽입
            return;
        } else if (median == ans[mid]) hi = mid; // 왼쪽 구간에 있는 경우 [lo:mid]
        else lo = mid; // 오른쪽 구간에 있는 경우 [mid:hi]
    }
    // lo + 1 == hi 이므로 3개의 숫자를 질의해서 삽입
    int median = query(ans[lo], ans[hi], x);
    if (median == ans[lo]) ans.insert(ans.begin() + lo, x);
    else if (median == ans[hi]) ans.insert(ans.begin() + hi + 1, x);
    else ans.insert(ans.begin() + hi, x);
}

void solve() {
    vector<int> ans(3);
    int median = query(1, 2, 3);
    if (median == 1) {
        ans[0] = 2; ans[1] = 1; ans[2] = 3;
    } else if (median == 2) {
        ans[0] = 1; ans[1] = 2; ans[2] = 3;
    } else {
        ans[0] = 1; ans[1] = 3; ans[2] = 2;
    }
    for (int x = 4; x <= N; x++)
        binary_search(x, ans);
    for (auto& x : ans) cout << x << " ";
    cout << endl;
    int correct; cin >> correct;
    assert(correct == 1);
}

• 세번째 접근법: 이분 탐색으로는 Test Set 3를 풀 경우 쿼리 비용이 많이 들어 해결 할 수 없다. Test Set 3에서는 1번의 테스트당 최대 Q는 170인데, 213 > 170 이기 때문에 다른 방법으로 최적화를 해주어야 한다. 풀이 아이디어에 따르면 삼분 탐색(Ternary Search)으로 삽입 위치를 결정할 경우 시간 복잡도는 대략 O(N*log3(N)) 정도이고 쿼리 횟수는 log3(3) + log3(4) + ... + log3(50) = 134.519 로 170보다 작기 때문에 충분히 해결할 수 있다.
  • 코드는 GeeksforGeeks를 참고했다.
  • 마찬가지로 base case에 주의해야 한다. 이분 탐색 풀이와 마찬가지로 크기가 2인 구간을 base case로 했다.
  • 삼분 탐색을 할경우 3개의 원소만 남게 되면 m1, m2가 시작값과 끝값과 동일하게 되므로 무한루프를 돌게 된다. 이런 상황을 배제하기 위해 구간을 나눌 때 m1, m2가 서로 겹치지 않게 나누어야 된다. 이 말은 lo ___ m1 ___ m2 ___ hi 라는 구간에 대해 3개의 구간으로 나눌 경우 겹치는 숫자가 있으면 안된다는 의미이다. [lo:m1) 그리고 [m1:m2) 그리고 [m2:hi).
  • 또한, 구간에 숫자가 겹치게 되면 삽입할 숫자 x가 들어갈 위치가 구간과 구간 사이에 놓일 때 원하는 순서로 삽입되지 않게 된다. 이거 때문에 직접 손으로 base case를 그려보면서 풀었다.
• 시간 복잡도: O(N*log3(N))

int query(int a, int b, int c);

void ternary_search(int x, vector<int>& ans) {
    int lo = 0, hi = ans.size() - 1;
    while (lo < hi) {
        if (lo + 1 == hi) { // base case
            int median = query(ans[lo], ans[hi], x);
            if (median == x) hi = lo;
            else if (median == ans[lo]) hi = lo - 1;
            break;
        }
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        // lo __ m1 __ m2 __ hi
        int median = query(ans[m1], ans[m2], x);
        if (median == ans[m1]) { // [lo, m1)
            hi = m1 - 1;
            if (lo == 0 and lo == hi) hi++;
            // ㄴ 첫번째 원소만 남게 되면 해당 원소의 앞에 위치할 수 있으므로
            // 첫 2개의 원소에 대해 질의할 수 있도록 hi++로 구간 크기를 2로 만들어준다.
        } else if (median == ans[m2]) { // [m2, hi)
            lo = m2;
        } else { // [m1, m2)
            lo = m1;
            hi = m2 - 1;
        }
    }
    ans.insert(ans.begin() + hi + 1, x);
}

void solve() {
    vector<int> ans(3);
    int median = query(1, 2, 3);
    ans[1] = median;
    ans[2] = ans[1] % 3 + 1;
    ans[0] = ans[2] % 3 + 1;
    for (int x = 4; x <= N; x++)
        ternary_search(x, ans);
    assert (ans.size() == N);
    for (auto& x : ans) cout << x << " ";
    cout << endl;
    int correct; cin >> correct;
    assert(correct == 1);
}

Cheating Detection

• 문제 설명: 100명의 선수들 중 랜덤으로 cheater가 1명 선정되어 경기를 하는데, cheater는 0.5의 확률로 치팅을 하거나 하지 않는다. 경기는 10000개의 질문에 대답하는 것이다. 선수가 질문에 옳게 답했다면 1, 아니면 0을 경기 결과로 가지게 된다. 테스트 케이스 이전에 입력으로 P가 주어지는데 이는 전체 테스트 케이스 중에서 적어도 P 개의 케이스에서 cheater 를 정확하게 선별해야 함을 의미한다. 매 테스트 케이스마다 100줄에 각 선수의 경기 결과가 10000글자로 입력되어진다.
  • 각 선수의 스킬 레벨 S와 각 질문의 난이도 Q는 [-3.00, 3.00] 범위에서 랜덤으로 균등하게 선택된다.
  • i번째 선수가 j번째 질문에 올바르게 답할 확률은 시그모이드 함수로 계산되며, sigmoid(Si - Qj) = 1 / (1 + exp(-Si + Qj)) 이다.
  • 출력은 cheater의 번호이며 선수의 번호는 1번부터 시작한다.
• 첫번째 접근법: 전체 테스트 케이스는 50개이며, P는 10이다. 전체 중 10퍼센트이므로 5번만 cheater를 찾아내면 된다. 정말 간단하게 생각해보면 cheater는 10000개의 질문 중 5000개는 반드시 올바르게 답하고, 5000개는 맞거나, 틀리거나 둘 중 하나이다. 만약 5000개의 질문 중 난이도가 높은 질문에 답을 잘하던 선수가 다른 5000개의 질문 중 난이도가 낮은 질문에 틀린 답을 많이 하게 된다면 cheater일 확률이 높다. 즉, 각 선수에게 cheater일 확률을 계산하기 위해 점수를 준다면 질문 난이도를 이용해야 한다.
  • 난이도가 낮은 질문을 틀렸을 때와 난이도가 높은 질문을 맞췄을 때 점수를 높게 준다.
  • 난이도가 낮은 질문을 맞췄을 때와 난이도가 높은 질문을 틀렸을 때 점수를 낮게 준다.
  • 질문 난이도는 쉽게 계산한다면 "100 - 제대로 답한 선수의 수" 가 될 것이다. 난이도가 낮을 수록 답한 선수가 많을 것.
  • 질문을 맞추는 경우 난이도에 비례(score += question_level)해서 점수를 주어야 하고, 질문이 틀린 경우 난이도에 반비례(score += 1 / question_level)해서 점수를 주어야 한다.

#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const static int _ = []() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
    return 0;
}();

const int MAX_P = 100;
const int MAX_Q = 10000;
const char CORRECT = '1';

void solve() {
    string in[MAX_P];
    double q_lv[MAX_Q];
    for (int i = 0; i < MAX_P; i++) cin >> in[i];

    int num_solved_questions[MAX_P], num_solved_players[MAX_Q];
    memset(num_solved_questions, 0, sizeof(num_solved_questions));
    memset(num_solved_players, 0, sizeof(num_solved_players));
    for (int i = 0; i < MAX_P; i++) {
        for (int j = 0; j < MAX_Q; j++) {
            if (in[i][j] == CORRECT) {
                num_solved_questions[i]++;
                num_solved_players[j]++;
            }
        }
    }

    int ans = -1;
    double max_score = 1e5;
    for (int i = 0; i < MAX_P; i++) {
        double score = 0;
        for (int j = 0; j < MAX_Q; j++) {
            int question_level = 100 - num_solved_players[j];
            if (in[i][j] == CORRECT) score += question_level;
            else score += 1.0 / question_level;
        }
        if (score > max_score) {
            max_score = score;
            ans = i+1;
        }
    }
    cout << ans << endl;
}

int main() {
    int T, P;
    cin >> T >> P;
    for (int tc = 1; tc <= T; tc++) {
        cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

• 두번째 접근법: Test Set 2은 P = 86으로 정확도를 90%가까이 향상시켜야 한다. 코드잼 풀이 아이디어에 따르면, 역수만 이용해서 계산할 경우 참가자의 스킬 레벨에 영향을 받지 않아 correct나 incorrect의 비율이 현저히 적은 선수에게는 역수를 계산할 기회가 적어 cheater를 찾기 어렵다고 한다. 따라서 스킬 레벨을 고려해야 한다. 그러나, 스킬 레벨을 단순히 "올바르게 답한 질문의 수"로만 지정하기에는 질문 난이도에 영향을 받는 등 별도로 계산하기 까다롭다. 풀이에서는 스킬 레벨을 추정(estimate)해서 모든 질문에 대해 답할 확률이 가장 낮게 나온 선수를 cheater로 봐야 한다고 한다. 다른 참가자의 코드를 살펴보니 이진 탐색으로 correct 확률과 incorrect 확률이 거의 동일하게 나오는 스킬 레벨을 추정값으로 썼다.
  • correct 확률은 앞서 설명한 시그모이드 함수로 계산할 수 있다.
  • incorrect 확률은 시그모이드 함수의 역수로 계산할 수 있다.
  • 이진 탐색으로 두 확률이 변화가 없을 때까지 추정하는데 10회 정도면 추정값을 찾을 수 있다. (이유는 모르겠다..)
  • 그리고 추정값을 실제 선수의 스킬 레벨이라고 가정하고, 모든 질문에 대해 답할 확률(맞거나 틀린 것 모두)의 기댓값이 가장 낮다면 실제 경기 결과에 치팅을 많이 했다는 의미이므로 해당 선수의 인덱스를 출력한다.

#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <limits>
using namespace std;

const static int _ = []() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
    return 0;
}();

const int MAX_P = 100;
const int MAX_Q = 10000;
const double MIN_QUESTION_LEVEL = -3.0;
const double MAX_QUESTION_LEVEL = 3.0;
const char CORRECT = '1';

void solve() {
    string in[MAX_P];
    double q_lv[MAX_Q];
    for (int i = 0; i < MAX_P; i++) cin >> in[i];

    // Calculate the difficulty of each question.
    for (int i = 0; i < MAX_Q; i++) {
        int num_solved_players = 0;
        for (int j = 0; j < MAX_P; j++)
            if (in[j][i] == CORRECT) num_solved_players++;
        if (num_solved_players == MAX_P) q_lv[i] = MIN_QUESTION_LEVEL;
        else if (num_solved_players == 0) q_lv[i] = MAX_QUESTION_LEVEL;
        else {
            q_lv[i] = log((double)MAX_P/num_solved_players - 1);
            if (q_lv[i] < MIN_QUESTION_LEVEL) q_lv[i] = MIN_QUESTION_LEVEL;
            if (q_lv[i] > MAX_QUESTION_LEVEL) q_lv[i] = MAX_QUESTION_LEVEL;
        }
    }

    // Find a cheater.
    pair<int, double> ans = {-1, numeric_limits<double>::max()};
    for (int i = 0; i < MAX_P; i++) {
        // Estimate each player's skill level using binary search.
        double lo = MIN_QUESTION_LEVEL, hi = MAX_QUESTION_LEVEL;
        for (int j = 0; j < 10; j++) {
            double mid = (lo + hi) * 0.5;
            double correct_pb = 0, incorrect_pb = 0;
            int num_correct = 0, num_incorrect = 0;
            for (int k = 0; k < MAX_Q; k++) {
                double expo = exp(-mid + q_lv[k]);
                if (in[i][k] == CORRECT) {
                    num_correct++;
                    correct_pb += log(1 / (1 + expo));
                } else {
                    num_incorrect++;
                    incorrect_pb += log(expo / (1 + expo));
                }
            }
            correct_pb /= num_correct;
            incorrect_pb /= num_incorrect;
            if (correct_pb > incorrect_pb) hi = mid;
            else lo = mid;
        }
        // Calculate the expected value that a player will answer for questions.
        double skill_level = (lo + hi) * 0.5;
        double sum = 0;
        for (int j = 0; j < MAX_Q; j++) {
            double expo = exp(-skill_level + q_lv[j]);
            if (in[i][j] == CORRECT) sum += log(1 / (1 + expo));
            else sum += log(expo / (1 + expo));
        }

        // Trace a cheater who has the greater difference
        // between actual probability and expected probability.
        // where the probability is that a player will answer for each question.
        if (ans.second > sum) {
            ans.second = sum;
            ans.first = i+1;
        }
    }
    cout << ans.first << endl;
}

int main() {
    int T, P;
    cin >> T >> P;
    for (int tc = 1; tc <= T; tc++) {
        cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}