Submission #713640

#	Time	Username	Problem	Language	Result	Execution time	Memory
713640		jophyyjh	Mechanical Doll (IOI18_doll)	C++14	100 / 100	72 ms	12892 KiB

doll

/**
 * An interesting construction~
 * [Tree] It was quite straight-forward (for me) to come up with a tree solution.
 *      Namely, each trigger's exit should point to a single switch known as the
 *      "root" of our tree. Our switches form shall form a rooted binary tree, with
 *      the exits of the leaves pointing back to the triggers, as specified in the
 *      input order. This idea is best illustrated when N is a power of 2 ([S4]). In
 *      this case, we assign the exits of the N/2 leaves using the reverse bit order
 *      of A[]. As a side note, the number of state changes is bounded by
 *      O(N * log_2(N)), so the limit of P is easily satisfied. (Well, the limit is
 *      there just for the grader~)
 * [Non-perfect tree] Then, I realized that this tree form isn't limited to perfect
 *      binary trees. Note that the tree can be defined in a recursive way. If a
 *      switch has to be responsible for N turns, we can create two new subtrees and
 *      point to them. The X subtree shall be responsible for ceil(N/2) turns, while
 *      the Y subtree shall be responsible for floor(N/2) turns. However, we quickly
 *      realize that this is impossible since each switch should return to state X
 *      when the ball completes a cycle. In the end, it seems that we still have to
 *      add "turns" that point back to the root of our tree, so we still need
 *      two_pow - 1 nodes...
 * [m=1] We have to create a circuit that passes trigger 1 exactly n times. Let
 *      two_pow = 2^(ceil(log_2(n))). It's clear that we can use two_pow-1 nodes to
 *      form a tree, with some leaf's exits pointing to the tree root instead of some
 *      trigger. But notice sth: some switches are unnecessary. If X and Y point to 
 *      two subtrees which are isomorphic, this switch isn't necessary, so this
 *      subtask can be solved with log_2(n) switches~
 * This idea of shrinking subtrees can be extended to the full solution. We first
 * order A[] in a modified version of reverse bit order. We put exits that point back
 * to the root "as left as possible" so that the "shrinking" effect can be maximised.
 * I know I've done a bad job describing this... Sorry~
 * 
 * Switches needed:   n - 1 + #ones_in_binary(two_pow - n),
 *                 two_pow = 2^(ceil(log_2(n))  (bound tight except for const term)
 * Implementation 1                 (Full solution, construction, binary tree)
*/

#include <bits/stdc++.h>
#include "doll.h"

typedef std::vector<int>    vec;

const int INF = 0x3f3f3f3f;

int reverse(int t, int digits) {
    int res = 0;
    for (int d = 0; d < digits; d++)
        res |= (1 << (digits - 1 - d)) * ((t >> d) & 1);
    return res;
}


vec order;      // reverse bit order / exits for the leaves
vec X, Y;

// The index of the root is returned. *helper* is the num of helper exits.
int build_tree(int l, int r, int helper) {
    int m = r - l, mid = (l + r) / 2;
    if (m == 1)
        return order[l];    // Directly return the node. We don't have to create one.
    int x, y;
    if (helper >= m / 2)
        x = -INF, y = build_tree(mid, r, helper - m / 2);   // -INF: placeholder
    else
        x = build_tree(l, mid, helper), y = build_tree(mid, r, 0);
    X.push_back(x);
    Y.push_back(y);
    return -X.size();
}

void create_circuit(int m, vec A) {
    int n = A.size();
    A.push_back(0);

    int pow = 0, two_pow = 1;
    while (two_pow < n)
        pow++, two_pow *= 2;
    int helpers = two_pow - n;
    // reverse bit order, impl inspired by cp-algorithms.com/algebra/fft.html
    order.resize(two_pow);
    for (int i = 0, j = 1; i < two_pow; i++) {
        int rev = reverse(i, pow);
        order[rev] = (rev >= helpers ? A[j++] : -INF);  // -INF: placeholder for root
    }
    int tree_root = build_tree(0, two_pow, helpers);
    std::replace(X.begin(), X.end(), -INF, tree_root);
    std::replace(Y.begin(), Y.end(), -INF, tree_root);
    vec C(m + 1, tree_root);
    C[0] = A[0];
    assert(int(X.size()) == n - 1 + __builtin_popcount(two_pow - n));
    answer(C, X, Y);
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56