Submission #402705

#	Time	Username	Problem	Language	Result	Execution time	Memory
402705		luisgalan	Combo (IOI18_combo)	C++14	5 / 100	1661 ms	988 KiB

combo

#include<bits/stdc++.h>
#include "combo.h"
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl

vector<vector<int>> possible;

char chars[4] = {'A', 'B', 'X', 'Y'};
map<char, int> charsinv;
string guess_sequence(int n) {
    charsinv.insert({'A', 0});
    charsinv.insert({'B', 1});
    charsinv.insert({'X', 2});
    charsinv.insert({'Y', 3});

    vector<int> res;
    int init;

    possible = vector<vector<int>>(n);
    fill(possible.begin(), possible.end(), vector<int> { 1, 1, 1, 1 });

    if (press("AB")) {
        init = press("A") ? 0 : 1;
    } else {
        init = press("X") ? 2 : 3;
    }
    res.push_back(init);

    vector<char> others;
    for (int i = 0; i < 4; i++) {
        if (i == init) continue;
        others.push_back(i);
    }

    for (int i = 0; i < n; i++) {
        possible[i][init] = 0;
    }

    while (true) {
        bool done = true;
        for (int i = 0; i < n-1; i++) {
            if (accumulate(possible[i].begin(), possible[i].end(), 0) > 1) {
                done = false;
                break;
            }
        }
        if (done) break;
        vector<string> queries = { string(1, chars[init]) };
        int i = 0;
        int size = 0;
        // while (2 * queries.size() * (queries[0].size() + 1) <= 4 * n && i + 1 < n) {
        while (i + 1 < n) {
            // debug(queries[0].size());
            vector<string> queries_next;
            int choice_1 = init;
            while (!possible[i][choice_1]) choice_1 = rand() % 4;
            int choice_2 = init;
            while (!possible[i][choice_2]) choice_2 = rand() % 4;
            for (string &query : queries) {
                int num_possible = accumulate(possible[i].begin(), possible[i].end(), 0);
                if (num_possible == 3) {
                    queries_next.push_back(query + chars[choice_1]);
                    queries_next.push_back(query + chars[choice_2]);
                } else {
                    queries_next.push_back(query + chars[choice_1]);
                }
            }
            int size = 0;
            for (auto &q : queries_next) size += q.size();
            if (size > 4 * n) {
                break;
            }
            queries = queries_next;
            i++;
        }
        string query = "";
        vector<vector<int>> possible_q(n);
        fill(possible_q.begin(), possible_q.end(), vector<int> { 0, 0, 0, 0 });
        for (string q : queries) {
            query += q;
            for (int i = 0; i < q.size(); i++) {
                if (q[i] == chars[init]) continue;
                possible_q[i-1][charsinv[q[i]]] = 1;
            }
        }
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < 4; j++) {
        //         cerr << possible_q[i][j];
        //     }
        //     cerr << " ";
        // };
        // cerr << endl;


        // debug(query.size());
        // debug(query);
        int coins = press(query);
        // debug(coins);
        for (int i = 0; i < coins - 2; i++) {
            for (int j = 0; j < 4; j++) {
                possible[i][j] = possible[i][j] && possible_q[i][j];
            }
        }
        for (int j = 0; j < 4; j++) {
            possible[coins-1][j] = possible[coins-1][j] && !possible_q[coins-1][j];
        }
        // cerr << "possible: ";
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < 4; j++) {
        //         cerr << possible[i][j];
        //     }
        //     cerr << " ";
        // };
        // cerr << endl;
    }

    string ans = "";
    ans += chars[init];
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < 4; j++) {
            if (possible[i][j]) ans += chars[j];
        }
    }
    return ans;
}

// we can cross out possible characters in parallel

// check first two chars for i and i + 1
// i has 111 and i+1 has 111
// try 110, 110
// if +2: i <- 110, b <- 110
// if +1: i <- 110, b <- 001
// if +0: i <- 001, b <- 111

// i has 111 and i+1 has 111
// try 100, 100
// if +2: i <- 100, b <- 100
// if +1: i <- 100, b <- 011
// if +0: i <- 011, b <- 111

// i has 110 and i+1 has 110
// try 100, 100
// if +2: i <- 100, b <- 100
// if +1: i <- 100, b <- 010
// if +0: i <- 010

// i has 110 and i+1 has 110 and i+2 has 111
// try 100, 100, 110
// if +3: i <- 100, i+1 <- 100, i+2 <- 110
// if +2: i <- 100, i+1 <- 100, i+2 <- 001
// if +1: i <- 100, i+1 <- 010
// if +0: i <- 010

// we need to cross out 2*n characters in total
// so we just need to always cross out at least two characters with each query
// problem is when we have 110, 110


// maybe we cross out more than two at the start?
// a has 111, b has 111, c has 111
// try 110, 110, 110
// if +3: a <- 110, b <- 110, c <- 110
// if +2: a <- 110, b <- 110, c <- 001
// if +1: a <- 110, b <- 001
// if +0: a <- 001

// P(+3) = 2/3 * 2/3 * 2/3
// P(+2) = 2/3 * 2/3 * 1/3
// P(+1) = 2/3 * 1/3
// P(+0) = 1/3

// C(n) = 2 + n
// P(n) = 1/3 * (2/3)^n
// M(n) = P(0) * C(0) + P(1) * C(1) + ... + P(n-1) * C(n-1) + 3 * P(n) * (C(n) - 2)
// M(n) - 3 * P(n) * (C(n) - 2)

// y = sum a^n
// a * y = sum a^(n+1) = y + a^(n+1) - a^0
// a * y - y = a^(n+1) - a^0
// y * (a - 1) = a^(n+1) - a^0
// y = (a^(n+1) - 1) / (a - 1)

// for 111, 111, 111, ...
// M(n) - 3 * P(n) * (C(n) - 2) > 3n
// M(n) > 3n + 3 * P(n) * (C(n) - 2) = 3n + n * (2/3)^n
// M(n) > 3n

// m * 2^l = 8000
// 2^l = 8000 / m
// l = log2(8000 / m)
// if m = 1 we have l = 12

// afaik we can reduce to only 110s very fast
// with randomized algorithm :)

// for 110, 110, 110, ...
// possible in at most O(n) queries

Compilation message (stderr)

combo.cpp: In function 'std::string guess_sequence(int)':
combo.cpp:81:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             for (int i = 0; i < q.size(); i++) {
      |                             ~~^~~~~~~~~~
combo.cpp:50:13: warning: unused variable 'size' [-Wunused-variable]
   50 |         int size = 0;
      |             ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95