作者RockLee (Now of all times)
看板Prob_Solve
標題[問題] Google Code Jam 2009, Final - A
時間Thu Apr 12 20:32:26 2012
題目敘述網址:
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)
1F：推 LPH66:Yj 是 indicator (指示變數)不是機率... 04/12 21:19
2F：→ LPH66:指示變數不是 1 就是 0 只不過有分佈而已 04/12 21:20
3F：→ LPH66:於是 (*) 就只是單純展開後拉期望值進和式裡 04/12 21:20
4F：→ LPH66:(a) 把平方項化掉 E(Yj^2) = E(Yj) 因為 Yj 不是 1 就是 0 04/12 21:21
5F：→ LPH66:(b) 則是 E(YjYk) 而裡面只在都是 1 時是 1 04/12 21:22
6F：→ LPH66:於是就是這兩者同在這一天的機率 04/12 21:23
7F：→ RockLee:所以我的問題在於根本沒唸過 indicator Orz googling... 04/12 22:18
8F：→ RockLee:了解了, 感謝 L 大的開示 ~ 04/12 23:37