Submission #792179

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
792179	2023-07-24 17:04:47	jophyyjh	Rarest Insects (IOI22_insects)	C++17	100 / 100	49 ms	420 KiB

insects

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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