作者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