Submission #792179

#	Time	Username	Problem	Language	Result	Execution time	Memory
792179		jophyyjh	Rarest Insects (IOI22_insects)	C++17	100 / 100	49 ms	420 KiB

insects

/**
 * I essentially screwed up this problem during contest, making me only capable of a
 * bronze. Anyway, my first solution was to add at most 1 insect of each insect type to the
 * machine, so we can find the total num of types & a representative of each type. Then, we
 * can iterate through each repr, each time clearing the machine, then adding all insects
 * of the same type to the machine. As a result, we find the cardinality of each type in
 * n^2 calls. (I should've done better...)
 * 
 * After the contest, I realized we can turn this into a decision problem. We wanna know
 * about the following predicate P(bound):
 *                  Does every insect type has cardinality >= bound?
 * Therefore, the final answer equals the max bound s.t. P(bound) is true. This can be done
 * with binary search. Most importantly, P(bound) can be found (quite easily) as follows:
 *      Iterate through all insects. First, add them to the machine. We can then
 *      check whether max_cardinality_in_machine <= bound (if not, just pop it).
 *      Consequently, every insect type has cardinality_in_machine <= bound after we
 *      consider every insect, so we just have to check if the num of insects in the
 *      machine is exactly #insect_types * bound.
 * This means m is at most ~11 (log_2(n)).
 * 
 * We now optimize the above approach. If P(bound) is true, the bound * #insect_type
 * insects currently in the machine can be discarded for later consideration, because we
 * know min_cardinality >= bound. Similarly, when P(bound) is false, we know
 * min_cardinality < bound, so we can forget the bound-th, (bound+1)-th, (bound+2)-th, ...
 * insects of any insect types can be discarded. Therefore, each time we reduce n by a
 * certain amount, which means our method of choosing bound each time is critical.
 * 
 * I was stuck for a while. Then, I noticed that when #insect_types is small, e.g. 1,
 * bound shall be O(n). (Like our original binary search, and n + n/2 + n/4 + ... ~= 2n.)
 * Though when #insect_types is O(n), e.g. n/2 or n, starting with n/2 may not reduce n at
 * all! To sum up, when the insects are distributed evenly, bound should start small; when
 * the insects are more concentrated in some types, bound should be rather "bigger". The
 * sol I found was to choose bound s.t. bound * #insect_types is n/2, so that n is always
 * reduced by 2 no matter P(bound) is true or false. As 2n = n + n/2 + n/4 + ..., our
 * solution should be ~3n. However, I don't have a good analysis on m, but I guessed it's
 * at most ~4, because every a less than 2b/3 has a multiple in [b/3,2b/3], though integer
 * rounding may spoil everything. Hmmm...
 * 
 * It turns out that I got 98.77 (pretty well actually). I then viewed the editorial. Turns
 * out that it doesn't have a good analysis too! They say that due to integer rounding, 
 * our solution should have m being slightly greater than 3. To improve the const, we can
 * just stop adding insects when P(bound) is known to be satisfied (before all insects
 * are added). But why does this guarantee 3n? (I don't even know whether it can!) I added
 * some randomization to satisfy P(bound) earlier.
 * 
 * PS1  floor(floor(a/b)/c) = floor(a/b/c); the same holds for ceil()'s
 * PS2  I've read many comments on codeforces. Looks like nobody have a good analysis~
 * PS3  Many solutions don't pop insects if
 *      bound * #insect_types = #cardinality_in_machine, but this only reduces the num of
 *      move_outside() calls. The ans is unaffected.
 * 
 * Max calls to the 3 operations:   3n      (claimed by the editorial, not proven at all)
 * Implementation 1.5               (condition: m=3)
*/

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

typedef std::vector<int>    vec;

inline int div_ceil(int a, int b)   { return (a + b - 1) / b; }


int find_bound(int n, int insect_types) {
    int b1 = n / 2 / insect_types, b2 = div_ceil(div_ceil(n, 2), insect_types);
    return (rand() & 1 ? b1 : b2);      // Add some randomization
}

int min_cardinality(int N) {
    vec consider;       // the set of insects we're currently considering
    std::vector<bool> first(N, false);
    int insect_types = 0;
    for (int k = 0; k < N; k++) {
        move_inside(k);
        if (press_button() > 1) {
            move_outside(k);
            consider.push_back(k);
        } else {
            insect_types++, first[k] = true;
        }
    }
    for (int k = 0; k < N; k++) {
        if (first[k])
            move_outside(k);    // clear the machine
    }
    // std::cerr << "[debug] types: " << insect_types << std::endl;

    std::default_random_engine rng(time(NULL));
    int base = 1, n = N - insect_types;
    while (n >= insect_types) {
        assert(int(consider.size()) == n);
        std::shuffle(consider.begin(), consider.end(), rng);
        int bound = find_bound(n, insect_types), count = 0;
        vec over, below;
        for (int k : consider) {
            // The last "constant" optimization
            if (count < bound * insect_types) {
                move_inside(k);
                if (press_button() > bound) {
                    move_outside(k);
                    over.push_back(k);
                } else {
                    count++;
                    below.push_back(k);
                }
            } else {
                over.push_back(k);
            }
            assert(count <= bound * insect_types);
        }
        for (int b : below)
            move_outside(b);
        if (count == bound * insect_types) {
            base += bound, n -= count;
            std::swap(consider, over);
        } else {
            n -= int(over.size());
            std::swap(consider, below);
        }
    }
    return base;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75