/**
* 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;
}
