Code Jam - Qualification Round 2021

Reversort

Code Jam - Google’s Coding Competitions

문제에 Reversort이라는 정렬방법이 주어진다.

배열이 주어지면, Reversort를 이용해 정렬하는데 필요한 비용을 구해야 한다.

 

하라는대로 구현하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int l[101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> l[i];
 
        int ans = 0;
        for (int i = 0; i < n - 1; i++)
        {
            auto it = min_element(l + i, l + n);
            ans += it - l - i + 1;
            reverse(l + i, it + 1);
        }
 
        cout << "Case #" << tc << ": " << ans << '\n';
    }
}
 

---

Moons and Umbrellas

Code Jam - Google’s Coding Competitions

'C', 'J', '?' 3개의 문자로만 이루어진 문자열 \(s\)가 주어진다.

이 문자열에 "CJ"와 같은 부분문자열 하나당 \(x\), "JC"와 같은 부분문자열 하나당 \(y\)의 비용이 든다.

'?'를 'C'와 'J'중 하나로 치환하여, 필요한 비용의 최소값을 구해야 한다.

 

\(O(|s|)\) DP로 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int INF = 1e9;
int x, y;
string s;
int dp[2][1001];
int solve(int cj, int idx)
{
    if (s[idx] != '?' && (s[idx] == 'C') != (cj == 0)) return INF;
    int& ret = dp[cj][idx];
    if (ret != INF) return ret;
    ret = 0;
    if (idx + 1 < s.size())
    {
        int r1 = solve(cj, idx + 1);
        int r2 = solve(1 - cj, idx + 1) + (cj ? y : x);
 
        ret = min(r1, r2);
    }
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++)
    {
        cin >> x >> y;
        cin >> s;
 
        for (int i = 0; i < s.size(); i++)
            dp[0][i] = dp[1][i] = INF;
 
        int res = min(solve(0, 0), solve(1, 0));
 
        cout << "Case #" << tc << ": " << res << '\n';
    }
}
 

---

Reversort Engineering

Code Jam - Google’s Coding Competitions

첫번째 문제의 Reversort의 역문제이다.

배열의 길이 \(n\)과 비용 \(c\)가 주어지면, Reversort했을 때 비용이 \(c\)가 드는 \(n\)길이의 배열을 출력해야 한다.

 

먼저 비용이 \(n-1\)보다 작거나, \(\frac{n(n+1)}{2}-1\)보다 크다면 불가능하다.

그렇지 않다면, \(k\)번째로 Reverse연산을 할 때 최소 1, 최대 \(n+1-i\)의 비용이 드므로 적당히 비용을 분배하자.

정렬된 배열에서 연산 역순으로 배열을 직접 뒤집어 보면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, c;
int ans[101];
int rv[101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    for (int tc = 1; tc <= t; tc++)
    {
        cin >> n >> c;
        if (c < n - 1 || c > n * (n + 1) / 2 - 1)
        {
            cout << "Case #" << tc << ": IMPOSSIBLE\n";
            continue;
        }
 
        c -= n - 1;
        for (int i = 1; i <= n; i++)
        {
            ans[i] = i;
            int res = min(c, n - i);
            c -= res;
            rv[i] = res + 1;
        }
 
        for (int i = n - 1; i >= 1; i--)
        {
            reverse(ans + i, ans + i + rv[i]);
        }
 
        cout << "Case #" << tc << ": ";
        for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}
 

---

Median Sort

Code Jam - Google’s Coding Competitions

\(n\)길이의 서로 다른 수로 이루어진 배열 \(x\)가 있다.

배열의 세 원소 \(x_i, x_j, x_k\)중에 중앙값이 무엇인지 알 수 있는 쿼리를 총 \(Q\)번 사용할 수 있을 때,

배열을 정렬한 결과를 알아내야 한다.

 

먼저 \(x_1, x_2, x_3\)에 대해 쿼리를 날린 다음,

중앙값을 제외하고 하나를 최소값, 하나를 최대값으로 설정한 다음, 정렬된 배열 \(a\)로 만들자.

이 배열에 Insertion Sort로 값을 추가할 수 있다.

 

각 값이 배열의 어디에 존재해야 하는지 삼분탐색을 이용해 알 수 있다.

(여기서의 삼분탐색은, 일반적인 의미의 삼분탐색이 아니라 단순히 구간을 3개로 나누는 것을 말한다)

 

범위 \([l, r)\) 안에 값 \(y\)를 추가하려고 하고, 구간의 삼분점을 각각 \(m1, m2\)라고 하자.

 

\(query(a_{m1}, a_{m2}, y\)의 값을 \(res\)라고 한다면,

1. \(res = y\)일 때 : \(y\)는 \([m1, m2)\)에 있어야 한다.

2. \(res = a_{m1}\)일 때 : \(y\)는 \([l, m1)\)에 있어야 한다.

3. \(res = a_{m2}\)일 때 : \(y\)는 \([m2, r)\)에 있어야 한다.

 

총 \(O(n\log n)\)회의 쿼리를 사용하므로 Test Set 2까지 무난히 통과할 수 있는데,

쿼리 개수에 대해 적절한 상수커팅을 더해주면 Test Set 3까지 통과가 가능하다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int Q = 17000;
 
int n, q;
vector <int> ans;
 
int query_cnt = 0;
 
int query(int a, int b, int c)
{
    if (++query_cnt > Q) exit(0);
 
    cout << a << ' ' << b << ' ' << c << endl;
    int res; cin >> res;
    return res;
}
 
int main()
{
    int t; cin >> t >> n >> q;
    for (int tc = 1; tc <= t; tc++)
    {
        ans.clear();
 
        int res = query(1, 2, 3);
        if (res == 1)
        {
            ans.push_back(2);
            ans.push_back(1);
            ans.push_back(3);
        }
        else if (res == 2)
        {
            ans.push_back(1);
            ans.push_back(2);
            ans.push_back(3);
        }
        else
        {
            ans.push_back(1);
            ans.push_back(3);
            ans.push_back(2);
        }
 
        for (int i = 4; i <= n; i++)
        {
            bool isFirst = false;
            int l = 0, r = ans.size();
            if (l + 1 < r)
            {
                int m = (l + r) / 2;
                int res = query(ans[l], ans[m], i);
                if (res == ans[l]) isFirst = true;
                else if (res == ans[m]) l = m;
                else r = m;
            }
 
            if (isFirst)
            {
                ans.insert(ans.begin(), i);
                continue;
            }
 
            while (l + 2 < r)
            {
                int m1 = (l * 2 + r) / 3;
                int m2 = (l + r * 2) / 3;
 
                int res = query(ans[m1], ans[m2], i);
                if (res == ans[m1]) r = m1;
                else if (res == ans[m2]) l = m2;
                else l = m1, r = m2;
            }
 
            while (l + 1 < r)
            {
                int m = (l + r) / 2;
                res = query(ans[l], ans[m], i);
 
                if (res == i) r = m;
                else l = m;
            }
 
            ans.insert(ans.begin() + l + 1, i);
        }
 
        for (int x : ans) cout << x << ' ';
        cout << endl;
 
        int k; cin >> k;
        if (k != 1) return 0;
    }
}
 

---

Cheating Detection

Code Jam - Google’s Coding Competitions

100명의 사람이 10000개의 문제를 푸려고 한다.

각 사람은 \(S_i\)라는 실력을 가지고 있고, 각 문제는 \(Q_j\)라는 난이도를 가지고 있다.

각 값은 \([-3.00, 3.00]\)의 구간 내에 존재한다.

 

\(i\)번째 사람이 \(j\)번째 문제를 풀 때 문제를 맞출 확률은 \(\frac{1}{1+e^{-x}}\)이다.

 

이 중 한 사람이 치팅을 하고 있다.

치팅을 하는 사람은 1/2의 확률로 문제를 무조건 맞춘다.

 

각 사람이 문제를 맞췄는지 여부가 주어질 때, 치팅을 하는 사람이 누구인지,

최소 86%의 확률로 맞춰야 한다.

 

 

각 사람이 맞춘 문제수를 바탕으로 대략적인 \(S_i\)를 복원할 수 있다.

마찬가지로 각 문제가 풀린 횟수를 바탕으로 \(Q_j\)를 복원할 수 있다.

 

두 문제 \(a,b\)에 대해, \(a\)가 \(b\)보다 더 쉬운 문제라고 하자.

\(a\)는 틀리고, \(b\)는 맞춘 횟수를 모든 \((a,b)\)쌍에 대해 계산할 수 있다.

이 값을 \(rev_i\)라고 하자.

치팅을 하는 사람은 \(rev_i\)값이 다른 사람들에 비해 높을것이라 예상할 수 있다.

 

하지만 한가지 문제가 있다.

어떤 사람의 실력이 3.00이나 -3.00에 가까질수록,

다시 말하면 맞은 문제의 수나 틀린 문제의 수 둘 중 한쪽이 많아질수록 \(rev_i\)값은 작아지게 된다.

 

따라서 일반적으로 \(S_i\)인 실력인 사람이 가지는 평균적인 \(rev_i\)값을 \(avg_i\)라고 할 때,

\(\frac{rev_i}{avg_i}\)의 값을 대신 비교함으로써 문제를 해결할 수 있다.

 

\(avg_i\)의 값은 같은 \(S_i\)의 실력인 사람 10명에 대해 직접 시뮬레이션 해보고,

(\(S_i, Q_j\)를 복원해놨으므로 가능하다.) 그 평균값을 사용했다.

 

#include <bits/stdc++.h>
#include <random>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int p;
string q[101];
 
int h_cnt[101];
int p_cnt[10001];
double h_p[101];
double p_p[10001];
double h_res[101];
double p_res[10001];
 
double solve(double d)
{
    double l = -3.0, r = 3.0;
    for (int i = 0; i < 100; i++)
    {
        double m = (l + r) / 2;
        double cur = (log(exp(m + 3) + 1) - log(exp(m - 3) + 1)) / 6;
        if (d > cur) l = m;
        else r = m;
    }
 
    return l;
}
 
int rev[101];
int avg_rev[101];
double rat_rev[101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    uniform_real_distribution<double> unif(0.0, 1.0);
    default_random_engine re;
 
    //freopen("ts2_input.txt", "r", stdin);
 
    int t; cin >> t >> p;
    for (int tc = 1; tc <= t; tc++)
    {
        memset(h_cnt, 0, sizeof h_cnt);
        memset(p_cnt, 0, sizeof p_cnt);
        memset(rev, 0, sizeof rev);
        memset(avg_rev, 0, sizeof avg_rev);
 
        for (int i = 0; i < 100; i++) cin >> q[i];
 
        for (int i = 0; i < 100; i++) for (int j = 0; j < 10000; j++)
        {
            if (q[i][j] == '1')
            {
                h_cnt[i]++;
                p_cnt[j]++;
            }
        }
 
        for (int i = 0; i < 100; i++)
        {
            h_p[i] = (double)h_cnt[i] / 10000;
            h_res[i] = solve(h_p[i]);
        }
 
        for (int i = 0; i < 10000; i++)
        {
            p_p[i] = (double)p_cnt[i] / 100;
            p_res[i] = -solve(p_p[i]);
        }
 
        int tmp[10001];
        for (int i = 0; i < 10000; i++) tmp[i] = i;
        sort(tmp, tmp + 10000, [](int a, int b) {return p_cnt[a] < p_cnt[b]; });
 
        const int LPCNT = 10;
        for (int i = 0; i < 100; i++)
        {
            int cnt = 0;
            for (int j = 0; j < 10000; j++)
            {
                if (q[i][tmp[j]] == '1') cnt++;
                else rev[i] += cnt;
            }
 
            for (int k = 0; k < LPCNT; k++)
            {
                cnt = 0;
                for (int j = 0; j < 10000; j++)
                {
                    double cp = 1.0 / (1.0 + exp(-(h_res[i] - p_res[tmp[j]])));
                    if (unif(re) < cp) cnt++;
                    else avg_rev[i] += cnt;
                }
            }
 
            rat_rev[i] = (double)rev[i] / ((double)avg_rev[i] / LPCNT);
        }
 
        int ans = max_element(rat_rev, rat_rev + 100) - rat_rev + 1;
        cout << "Case #" << tc << ": " << ans << '\n';
    }
}