Problem Info
http://usaco.org/index.php?page=viewproblem2&cpid=1210
My Work
from decimal import *
getcontext().prec = 30 # let's hope this works
test_num, sub_num = [int(i) for i in input().split()]
test_num -= 1 # we don't care about the sample
comb_vals = []
curr = 1
at = test_num
for k in range(test_num + 1):
comb_vals.append(curr)
curr = curr * at // len(comb_vals)
at -= 1
pow_ = 2 ** test_num
prob = [Decimal(v) / pow_ for v in comb_vals]
# this[i] = the change of getting at least i test cases
prob_meet = [prob[-1]]
for i in range(len(prob) - 2, -1, -1):
prob_meet.append(prob_meet[-1] + prob[i])
prob_meet.reverse()
# this[i] GIVEN THAT we've hit at least i test cases, what's the expected value?
meet_exp_val = [test_num]
outcome_num = 1
total_vals = test_num
for tcn in range(test_num - 1, -1, -1):
outcome_num += comb_vals[tcn]
total_vals += comb_vals[tcn] * tcn
meet_exp_val.append(Decimal(total_vals) / outcome_num)
meet_exp_val.reverse()
# this[i] = same thing as above but given that we've hit STRICTLY UNDER i test cases
under_exp_val = [0, 0]
outcome_num = 1
total_vals = 0
for tcn in range(1, test_num + 1):
outcome_num += comb_vals[tcn]
total_vals += comb_vals[tcn] * tcn
under_exp_val.append(Decimal(total_vals) / outcome_num)
best_val = 0
for strat in range(test_num + 1):
p_meet = prob_meet[strat]
meet_exp = meet_exp_val[strat]
p_under = 1 - p_meet
under_exp = under_exp_val[strat]
hit_target = p_meet * (p_under ** sub_num - 1) / (p_under - 1)
dont = p_under ** sub_num
print(meet_exp * hit_target + under_exp * dont)
best_val = max(
best_val,
meet_exp * hit_target + under_exp * dont
)
print(best_val + 1) # +1 for the sample
# 25 97 should output 17.908380127142752664
I defined a “strategy” as a point where Bessie goes “Good enough for me”.
All the arrays are defined in the code with comments.
The main for loop at the bottom of the code calculates for each strat the expected value.
hit_target is the chance that Bessie hits her expectation, and dont is the chance she doesn’t hit her expectation.
This program fails on all cases except the sample ones. I’ve tried downloading the data, but all of them are too large to solve by hand.