Submission #791174

#	Time	Username	Problem	Language	Result	Execution time	Memory
791174		jophyyjh	Rarest Insects (IOI22_insects)	C++17	98.77 / 100	55 ms	404 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 O(n) (e.g. n/2, 2n/3), so
 * that n is always reduced by some const factor. 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...
 * 
 * P.S. floor(floor(a/b)/c) = floor(a/b/c); the same holds for ceil()'s
 * 
 * Max calls to the 3 operations:   idk
 * Implementation 1                 (condition: 3 < m <= 6)
*/

#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) {
    std::vector<bool> out(N, false);    // out of our consideration
    int insect_types = 0;
    for (int k = 0; k < N; k++) {
        move_inside(k);
        if (press_button() > 1)
            move_outside(k);
        else
            insect_types++, out[k] = true;
    }
    for (int k = 0; k < N; k++) {
        if (out[k])
            move_outside(k);    // clear the machine
    }
    // std::cerr << "[debug] types: " << insect_types << std::endl;

    int base = 1, n = N - insect_types;
    while (n >= insect_types) {
        int bound = find_bound(n, insect_types), count = 0;
        vec over, below;
        for (int k = 0; k < N; k++) {
            if (out[k])
                continue;
            move_inside(k);
            if (press_button() > bound) {
                move_outside(k);
                over.push_back(k);
            } else {
                count++;
                below.push_back(k);
            }
        }
        assert(count <= bound * insect_types);
        if (count == bound * insect_types) {
            base += bound;
            for (int b : below)
                out[b] = true, n--;
        } else {
            for (int o : over)
                out[o] = true, n--;
        }
        for (int b : below)
            move_outside(b);
    }
    return base;
}

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