Home » 国际竞赛 » Details

USACO 2022 February Contest, Gold Problem 2. Cow Camp

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午4:34

To qualify for cow camp, Bessie needs to earn a good score on the last problem of the USACOW Open contest. This problem has $T$ distinct test cases ( $2 \leq T \leq 10^{3}$ ) weighted equally, with the first test case being the sample case. Her final score will equal the number of test cases that her last submission passes.

Unfortunately, Bessie is way too tired to think about the problem, but since the answer to each test case is either "yes" or "no," she has a plan! Precisely, she decides to repeatedly submit the following nondeterministic solution:

if input == sample_input:
  print sample_output
else:
  print "yes" or "no" each with probability 1/2, independently for each test case

Note that for all test cases besides the sample, this program may produce a different output when resubmitted, so the number of test cases that it passes will vary.

Bessie knows that she cannot submit more than $K$ ( $1 \leq K \leq 10^{9}$ ) times in total because then she will certainly be disqualified. What is the maximum possible expected value of Bessie's final score, assuming that she follows the optimal strategy?

INPUT FORMAT (input arrives from the terminal / stdin):

The only line of input contains two space-separated integers $T$ and $K .$

OUTPUT FORMAT (print output to the terminal / stdout):

The answer as a decimal that differs by at most $10^{- 6}$ absolute or relative error from the actual answer.

SAMPLE INPUT:

2 3

SAMPLE OUTPUT:

1.875

In this example, Bessie should keep resubmitting until she has reached $3$ submissions or she receives full credit. Bessie will receive full credit with probability $\frac{7}{8}$ and half credit with probability $\frac{1}{8}$ , so the expected value of Bessie's final score under this strategy is $\frac{7}{8} \cdot 2 + \frac{1}{8} \cdot 1 = \frac{15}{8} = 1.875$ . As we see from this formula, the expected value of Bessie's score can be calculated by taking the sum over $x$ of $p (x) \cdot x$ , where $p (x)$ is the probability of receiving a score of $x$ .

SAMPLE INPUT:

4 2

SAMPLE OUTPUT:

2.8750000000000000000

Here, Bessie should only submit twice if she passes fewer than $3$ test cases on her first try.

SCORING

Test cases 3-6 satisfy $T \leq 25$ and $K \leq 100.$
Test cases 7-9 satisfy $K \leq 10^{6} .$
Test cases 10-17 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2022 February Contest, Gold Problem 2. Cow Camp 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Let's ignore the sample case by subtracting one from $T$ (at the end, we'll add one back to the answer). Then the probability of Bessie's solution solving exactly $i$ test cases out of $T$ is precisely $p_{i} = \frac{(\binom{T}{i})}{2^{T}} .$

Define $E_{x}$ to be the expected value given at most $x$ submissions, where $E_{0} = 0$ . The goal is to compute $E_{K}$ . If we have already computed $E_{x}$ then $E_{x + 1}$ may be computed as follows:

Suppose that Bessie's first submission scores $i$ out of $T$ test cases.
Bessie now has two choices: either she can stop submitting and end up with a final score of $i$ , or she will end up with expected score $E_{x}$ if she submits at least one more time and uses her remaining $x$ submissions optimally.
Therefore, her strategy is as follows:
- If $i > E_{x}$ , then stop submitting.
- If $i \leq E_{x},$ then continue submitting.

In equations,

E x + 1 = \sum i = 0 T p i \cdot E [Bessie's strategy given that her first submission scored i] = \sum i = 0 T p i \cdot max (i, E x) = E x \cdot \sum i = 0 ⌊ E x ⌋ p i + \sum i = ⌊ E x ⌋ + 1 T i p i .

Subtask 1: The above equations can be simulated in $O (T K)$ time.

The solution below uses Python's decimal module for increased precision (though it was not necessary to do so).

from decimal import *
getcontext().prec = 100
 
T, K = map(int, input().split())
T -= 1
 
prob = [Decimal(1)]
for _ in range(T):
	prob = [(x+y)/2 for x, y in zip([Decimal(0)]+prob, prob+[Decimal(0)])]
 
E = Decimal(T)/2
K -= 1
 
while K > 0:
	K -= 1
	next_E = 0
	for i in range(T+1):
		next_E += prob[i]*max(i,E)
	E = next_E

getcontext().prec = 20
print(E+1)

Subtask 2: Let $a = \sum_{i = 0}^{⌊ E_{x} ⌋} p_{i}$ and $b = \sum_{i = ⌊ E_{x} ⌋ + 1}^{T} i p_{i},$ such that $E_{x + 1} = a E_{x} + b .$ Observe that when $⌊ E_{x + 1} ⌋ = ⌊ E_{x} ⌋$ , we do not need to recalculate $a$ and $b$ .

The runtime of the solution below is $O (T^{2} + K)$ .

T, K = map(int, input().split())
T -= 1
 
prob = [1]
for _ in range(T):
	prob = [(x+y)/2 for x, y in zip([0]+prob, prob+[0])]
 
E = T/2
K -= 1

for f in range(T):
	a, b = 0, 0
	for i in range(T+1):
		if i <= f:
			a += prob[i]
		else:
			b += prob[i]*i
	while K > 0 and E < f+1:
		E = a*E+b
		K -= 1

print(E+1)

Full Credit: For a solution without a factor of $O (K)$ , we need to be able to advance $x$ multiple submissions forward at once.

Under this assumption, we can write

E x + q = a q E x + b \cdot \sum i = 0 q - 1 a i = a q E x + b \cdot 1 - a q 1 - a

by the geometric series formula. It remains to either determine that $⌊ E_{K} ⌋ = ⌊ E_{x} ⌋$ , or find the smallest $q \leq K - x$ such that $⌊ E_{x + q} ⌋ > ⌊ E_{x} ⌋ .$

After finding $q$ via one of the two methods below, we may simulate $min (q, K - x)$ submissions at once and then update $x + = min (q, K - x)$ . If we now have $x = K$ , then we're done. Otherwise, we know that $⌊ E_{x} ⌋$ has increased by one. $⌊ E_{x} ⌋$ can increase a total of at most $T$ times, which is a lot smaller than $K$ .

Method 1: Binary search on $q$ .

My code follows. The total number of calls to $pow$ is $O (T \log K)$ .

from decimal import *
getcontext().prec = 100
 
T, K = map(int, input().split())
T -= 1
 
prob = [Decimal(1)]
for _ in range(T):
	prob = [(x+y)/2 for x, y in zip([Decimal(0)]+prob, prob+[Decimal(0)])]
 
E = Decimal(T)/2
K -= 1

for f in range(T):
	if K == 0:
		break
	if E // 1 > f:
		continue
	a, b = Decimal(0), Decimal(0)
	for i in range(T+1):
		if i <= f:
			a += prob[i]
		else:
			b += prob[i]*i

	def next_E(q): # value of E after q timesteps
		return pow(a,q)*E+(1-pow(a,q))/(1-a)*b

	# binary search on q
	q_lo = 1
	while 2*q_lo <= K and next_E(q_lo*2) < f+1:
		q_lo *= 2
	q_hi = 2*q_lo
	while q_lo < q_hi:
		q_mid = (q_lo+q_hi)//2
		if next_E(q_mid) < f+1:
			q_lo = q_mid+1
		else:
			q_hi = q_mid

	# advance q submissions
	q_lo = min(q_lo, K)
	K -= q_lo
	E = next_E(q_lo)
 
getcontext().prec = 20
print(E+1)

Method 2: We can rewrite $⌊ E_{x + q} ⌋ > ⌊ E_{x} ⌋$ as follows:

⟹ ⟹ a q \cdot E x + b 1 - a \cdot (1 - a q) \geq ⌊ E x ⌋ + 1 a q (b 1 - a - E x) \leq b 1 - a - (⌊ E x ⌋ + 1) a q \leq b 1 - a - ( ⌊ E x ⌋ + 1 ) b 1 - a - E x .

Then we can take the natural logarithm of both sides to get

q \geq log ( b 1 - a - ( ⌊ E x ⌋ + 1 ) b 1 - a - E x ) log a .

The runtime of the solution below is $O (T^{2})$ . $a$ corresponds to $probabilityLower$ and $\frac{b}{1 - a}$ corresponds to $expectedHigher$ .

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class CowCamp {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int t = Integer.parseInt(tokenizer.nextToken()) - 1;
        int k = Integer.parseInt(tokenizer.nextToken());
        double[][] probability = new double[t + 1][t + 1];
        probability[0][0] = 1.0;
        for (int a = 1; a <= t; a++) {
            probability[a][0] = probability[a - 1][0] / 2.0;
            for (int b = 1; b <= t; b++) {
                probability[a][b] = (probability[a - 1][b - 1] + probability[a - 1][b]) / 2.0;
            }
        }
        double expected = .0;
        int attempts = 0;
        for (int score = 1; score <= t; score++) {
            double probabilityLower = .0;
            for (int lower = 0; lower < score; lower++) {
                probabilityLower += probability[t][lower];
            }
            double expectedHigher = .0;
            for (int higher = score; higher <= t; higher++) {
                expectedHigher += probability[t][higher] * ((double) higher);
            }
            expectedHigher /= 1.0 - probabilityLower;
            double difference = expectedHigher - expected;
            double differenceToAchieve = expectedHigher - ((double) score);
            double attemptsNeeded = Math.log(differenceToAchieve / difference) / Math.log(probabilityLower);
            boolean doneHere = attemptsNeeded > k - attempts;
            int attemptsToUse = doneHere ? (k - attempts) : (int) Math.round(Math.ceil(attemptsNeeded));
            difference *= Math.pow(probabilityLower, attemptsToUse);
            expected = expectedHigher - difference;
            attempts += attemptsToUse;
            if (attempts == k) {
                break;
            }
        }
        System.out.println(1.0 + expected);
    }
}

[/hide]