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

[RockLee (Now of all times)]

題目敘述網址:
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)
推 LPH66:Yj 是 indicator (指示變數)不是機率...
→ LPH66:指示變數不是 1 就是 0  只不過有分佈而已
→ LPH66:於是 (*) 就只是單純展開後拉期望值進和式裡
→ LPH66:(a) 把平方項化掉  E(Yj^2) = E(Yj) 因為 Yj 不是 1 就是 0
→ LPH66:(b) 則是 E(YjYk) 而裡面只在都是 1 時是 1
→ LPH66:於是就是這兩者同在這一天的機率
→ RockLee:所以我的問題在於根本沒唸過 indicator Orz googling...
→ RockLee:了解了, 感謝 L 大的開示 ~