PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The model solution for this problem is very simple, and this problem can be solved for larger N. However I have set N ≤ 36 for keeping away from guessing the simple solution from the constraint. Naive bruteforce algorithms with O(N!/K!/(N-K)!) or O**(N*2N/2)** will get TimeLimitExceeded. I would like to say that the tester can solve this problem by an optimized bruteforce solution.
Let’s start the explanation of the model solution. We don’t have to check all combinations. At first, sort Pi, and consider the case where P1 ≤ P2 ≤ … ≤ PN. There is at least one answer that first i problems and last K-i problems are chosen, that is, problem 1, 2, …, i, and problem N-K+i+1, N-K+i+2, …, N are chosen. This method is O(N2 + K3) time implemented naively as the setter’s solution.
A short proof is the following. Let one of the optimal sets be the problem A1, A2, …, AK, and let the set don’t contain problem B and C, where B < AK < C. For the set of K-1 problems A1, A2, …, AK-1, let x be the probability that all problems are solved correctly, and y be the probability that K-2 problems solved correctly. Then, the probability of solving K-1 problems correctly for the set of K problems A1,A2, …, Ak-1,Z is ( 1-PZ/100 ) * x + PZ/100 * y. Because this is the linear function of PZ, the set of problems A1**, A2, …, AK-1, B and A1, A2, …, AK-1, C are also optimal sets.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.