USACO 2022 February Contest, Gold Problem 2. Cow Camp

 

USACO 2022 February Contest, Gold Problem 2. Cow Camp

To qualify for cow camp, Bessie needs to earn a good score on the last problem of the USACOW Open contest. This problem has TT distinct test cases (2T1032≤T≤103) 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 KK (1K1091≤K≤109) 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 TT and K.K.

 

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

The answer as a decimal that differs by at most 10610−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 33 submissions or she receives full credit. Bessie will receive full credit with probability 7878 and half credit with probability 1818, so the expected value of Bessie's final score under this strategy is 782+181=158=1.87578⋅2+18⋅1=158=1.875. As we see from this formula, the expected value of Bessie's score can be calculated by taking the sum over xx of p(x)xp(x)⋅x, where p(x)p(x) is the probability of receiving a score of xx.

 

SAMPLE INPUT:

4 2

SAMPLE OUTPUT:

2.8750000000000000000

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

 

SCORING

  • Test cases 3-6 satisfy T25T≤25 and K100.K≤100.
  • Test cases 7-9 satisfy K106.K≤106.
  • 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 TT (at the end, we'll add one back to the answer). Then the probability of Bessie's solution solving exactly ii test cases out of TT is precisely pi=(Ti)2T.pi=(Ti)2T.

Define ExEx to be the expected value given at most xx submissions, where E0=0E0=0. The goal is to compute EKEK. If we have already computed ExEx then Ex+1Ex+1 may be computed as follows:

 

  • Suppose that Bessie's first submission scores ii out of TT test cases.
  • Bessie now has two choices: either she can stop submitting and end up with a final score of ii, or she will end up with expected score ExEx if she submits at least one more time and uses her remaining xx submissions optimally.
  • Therefore, her strategy is as follows: 
    • If i>Exi>Ex, then stop submitting.
    • If iEx,i≤Ex, then continue submitting.

In equations,

 

Ex+1=i=0TpiE[Bessie's strategy given that her first submission scored i]=i=0Tpimax(i,Ex)=Exi=0Expi+i=Ex+1Tipi.Ex+1=∑i=0Tpi⋅E[Bessie's strategy given that her first submission scored i]=∑i=0Tpi⋅max(i,Ex)=Ex⋅∑i=0⌊Ex⌋pi+∑i=⌊Ex⌋+1Tipi.

Subtask 1: The above equations can be simulated in O(TK)O(TK) 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=Exi=0pia=∑i=0⌊Ex⌋pi and b=Ti=Ex+1ipi,b=∑i=⌊Ex⌋+1Tipi, such that Ex+1=aEx+b.Ex+1=aEx+b. Observe that when Ex+1=Ex⌊Ex+1⌋=⌊Ex⌋, we do not need to recalculate aa and bb.

The runtime of the solution below is O(T2+K)O(T2+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)O(K), we need to be able to advance xx multiple submissions forward at once.

Under this assumption, we can write

 

Ex+q=aqEx+bi=0q1ai=aqEx+b1aq1aEx+q=aqEx+b⋅∑i=0q−1ai=aqEx+b⋅1−aq1−a

by the geometric series formula. It remains to either determine that EK=Ex⌊EK⌋=⌊Ex⌋, or find the smallest qKxq≤K−x such that Ex+q>Ex.⌊Ex+q⌋>⌊Ex⌋.

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

Method 1: Binary search on qq.

My code follows. The total number of calls to powpow is O(TlogK)O(Tlog⁡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 Ex+q>Ex⌊Ex+q⌋>⌊Ex⌋ as follows:

 

aqEx+b1a(1aq)Ex+1aq(b1aEx)b1a(Ex+1)aqb1a(Ex+1)b1aEx.aq⋅Ex+b1−a⋅(1−aq)≥⌊Ex⌋+1⟹aq(b1−a−Ex)≤b1−a−(⌊Ex⌋+1)⟹aq≤b1−a−(⌊Ex⌋+1)b1−a−Ex.

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

 

qlog(b1a(Ex+1)b1aEx)loga.q≥log⁡(b1−a−(⌊Ex⌋+1)b1−a−Ex)log⁡a.

The runtime of the solution below is O(T2)O(T2)aa corresponds to probabilityLowerprobabilityLower and b1ab1−a corresponds to expectedHigherexpectedHigher.

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]

翰林国际教育资讯二维码