※ 引述《shaopin (problem maker)》之銘言：
: (context)題目在這:
: http://code.google.com/codejam/contest/1836486/dashboard#s=p0&a=0
: 我的問題是關於:
: 1.
: 假設有一個個方程組如下:
: 21 + 75*x = 24 + 75*y = 30 + 75*z;
: x+y+z =1
: 該用什麼algorithm解他?(library就別提了)
: 2.
: 為什麼這樣解出來的x,y,z就剛好是
: 那三個人每一個人避免被淘汰所需的最小支持度?
: 感謝
This is linear programming (LP)....
你可以看看原來的題目, 每個人的得分是
J + X*Y
所以, 要是三個人的狀況下,
A = 24, B = 30, C = 21.
我們換個方式問, 請問, A 一定被淘汰的狀況下,
他的得票率有可能是多少?
It implies..
24 + 75*x < 30 + 75*y ;
24 + 75*x < 21 + 75*z ;
s.t
x + y + z = 1.
這就是一個標準的 LP 中 feasible region 的例子.
(我那時候的高中數學有敎這一段)
那個邊界條件, 就是 "避免被淘汰的" 情況.
然後你變換一下
75* x - 75*y = 6
75* x - 75*z = -3
75*x + 75*y + 75*z = 75
變成一個標準的解 linear equation 問題: A*v = b.
A is full rank and easy to generate.
正面攻擊法, 是用 Gauss-elimiation method 去作
很少人會用 Determinant 去解的, 因為那個會有 det(A) 數值上的問題.
不過, 如果你仔細的把題目再看看, 這題有特殊形式,
因此一下就能解出來..