oj.uz

Submission #792179

# Submission time Handle Problem Language Result Execution time Memory
792179 2023-07-24T17:04:47 Z jophyyjh Rarest Insects (IOI22_insects) C++17
100 / 100
 49 ms 420 KB 
/**
 * 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 220 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 4 ms 208 KB Output is correct
9 Correct 5 ms 208 KB Output is correct
10 Correct 3 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 5 ms 208 KB Output is correct
13 Correct 5 ms 208 KB Output is correct
14 Correct 4 ms 208 KB Output is correct
15 Correct 3 ms 208 KB Output is correct
16 Correct 4 ms 208 KB Output is correct
17 Correct 5 ms 256 KB Output is correct
18 Correct 5 ms 296 KB Output is correct
19 Correct 5 ms 208 KB Output is correct
20 Correct 4 ms 304 KB Output is correct
21 Correct 4 ms 208 KB Output is correct
22 Correct 2 ms 208 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 220 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 4 ms 208 KB Output is correct
9 Correct 5 ms 208 KB Output is correct
10 Correct 3 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 5 ms 208 KB Output is correct
13 Correct 5 ms 208 KB Output is correct
14 Correct 4 ms 208 KB Output is correct
15 Correct 3 ms 208 KB Output is correct
16 Correct 4 ms 208 KB Output is correct
17 Correct 5 ms 256 KB Output is correct
18 Correct 5 ms 296 KB Output is correct
19 Correct 5 ms 208 KB Output is correct
20 Correct 4 ms 304 KB Output is correct
21 Correct 4 ms 208 KB Output is correct
22 Correct 2 ms 208 KB Output is correct
23 Correct 7 ms 208 KB Output is correct
24 Correct 9 ms 208 KB Output is correct
25 Correct 12 ms 284 KB Output is correct
26 Correct 33 ms 300 KB Output is correct
27 Correct 15 ms 208 KB Output is correct
28 Correct 6 ms 208 KB Output is correct
29 Correct 19 ms 312 KB Output is correct
30 Correct 25 ms 300 KB Output is correct
31 Correct 14 ms 300 KB Output is correct
32 Correct 13 ms 308 KB Output is correct
33 Correct 17 ms 304 KB Output is correct
34 Correct 16 ms 208 KB Output is correct
35 Correct 21 ms 308 KB Output is correct
36 Correct 21 ms 208 KB Output is correct
37 Correct 25 ms 208 KB Output is correct
38 Correct 13 ms 208 KB Output is correct
39 Correct 13 ms 300 KB Output is correct
40 Correct 13 ms 208 KB Output is correct
41 Correct 7 ms 208 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 31 ms 300 KB Output is correct
8 Correct 12 ms 208 KB Output is correct
9 Correct 19 ms 304 KB Output is correct
10 Correct 36 ms 300 KB Output is correct
11 Correct 43 ms 308 KB Output is correct
12 Correct 26 ms 300 KB Output is correct
13 Correct 48 ms 300 KB Output is correct
14 Correct 48 ms 300 KB Output is correct
15 Correct 36 ms 296 KB Output is correct
16 Correct 31 ms 300 KB Output is correct
17 Correct 36 ms 308 KB Output is correct
18 Correct 31 ms 304 KB Output is correct
19 Correct 45 ms 304 KB Output is correct
20 Correct 40 ms 300 KB Output is correct
21 Correct 46 ms 300 KB Output is correct
22 Correct 46 ms 300 KB Output is correct
23 Correct 45 ms 304 KB Output is correct
24 Correct 32 ms 296 KB Output is correct
25 Correct 29 ms 288 KB Output is correct
26 Correct 8 ms 296 KB Output is correct
27 Correct 40 ms 304 KB Output is correct
28 Correct 37 ms 300 KB Output is correct
29 Correct 43 ms 304 KB Output is correct
30 Correct 33 ms 304 KB Output is correct
31 Correct 34 ms 420 KB Output is correct
32 Correct 36 ms 208 KB Output is correct
33 Correct 43 ms 300 KB Output is correct
34 Correct 49 ms 300 KB Output is correct
35 Correct 35 ms 300 KB Output is correct
36 Correct 34 ms 304 KB Output is correct
37 Correct 34 ms 304 KB Output is correct
38 Correct 38 ms 308 KB Output is correct
39 Correct 43 ms 308 KB Output is correct
40 Correct 21 ms 308 KB Output is correct
41 Correct 21 ms 320 KB Output is correct
42 Correct 36 ms 312 KB Output is correct
43 Correct 12 ms 316 KB Output is correct
44 Correct 16 ms 320 KB Output is correct
45 Correct 15 ms 312 KB Output is correct
46 Correct 11 ms 320 KB Output is correct
47 Correct 32 ms 308 KB Output is correct
48 Correct 16 ms 292 KB Output is correct