PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] Google Code Jam 2009, Final - A

看板Prob_Solve (計算數學 Problem Solving)作者RockLee (Now of all times)時間12年前 (2012/04/12 20:32)推噓1(1推 0噓 7→)

留言8則, 2人參與討論串1/1

題目敘述網址: http://code.google.com/codejam/contest/311101/dashboard#s=p0&a=0 官方解答說明: http://code.google.com/codejam/contest/311101/dashboard#s=a&a=0 (以下摘錄自官方解答) Define the random variable X to be the number of contests on the i-th day. Define Yj to be the indicator of whether the j-th tournament will have a contest on the i-th day. Clearly, X = Σ1<=j<=T Yj. So, (*) Ε(X^2) = Ε((Σ1<=j<=T Yj)^2) = Σ1<=j<=T Ε((Yj)^2) + 2 Σ1<=j<k<=T Ε (Yj*Yk). We observe that each terms in the last expression is easy to compute. Being the indicator random variables, the Y's take value 0 or 1. So (a) (Yj)^2 always has the same value as Yj, and its expectation is just the probability that Yj is 1. (b) Yj Yk is 1 if and only if both Yj and Yk are 1. The expectation is the probability that both the j-th and the k-th tournament has a contest on day i. 想到的 algorithm 只能在限定時間內跑完 small data set, 原因是(*)(a)(b)所描述的期望值關係對我而言一點也不 clearly Orz... 麻煩高手幫忙用比較白話的方式開示一下: (1) 為何某一天的 happiness 期望值會等於: (任一比賽發生的機率的和) + 2 * (任兩不同比賽同時發生的機率的和)? (2) 如果這一題的 happiness 定義為 S^3 的話, 要如何化簡呢? <_.._> -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.137.137.126 ※ 編輯: RockLee 來自: 220.137.137.126 (04/12 20:41)