Problem A. …..
Brief description:
。。。转盘赌博问题。。一共有 37 个数字。。转到某个数字后得到这个投注的 36 倍。。。（负和？
。。现在你发现赌场的这个装置是有问题的。。既每次只会随机停留在投注最少的数字上。。
你决定举报之前。。先尽可能捞回本。。。于是你决定下一轮最后一个投注。。给定你当前的筹码和目前的局面。。。
。。。问你此轮的最大的期望收益是多少。。）
Analysis:
… 枚举 + 二分答案。。
https://gist.github.com/lychees
Problem B. Rural Planning
Brief description:
。。给定一个规模为 n 的点集，要求给出一个长度为 n 的排列。
使得依据此排列顺次连接这些点所形成的多变形不产生相交，且面积比这组点集所形成的凸包的面积的一半要大。
( Small n = 10, Large n = 1000 )
Analysis:
… Small 的话。。判断线段相交就可以。。（枚举所有排列。。暴力检测。。。
https://gist.github.com/lychees/5815413
。。之后考虑为什么满足条件的解一定存在。。
。。如图。。将凸包这样分成两半。。必有一部分的面积 >= 凸包面积的一半。
。。我们用大的去 “吸收” 小的。。所形成的图形的面积必定还会增加。。因此最后一定 > 凸包面积的一半。
。。考虑吸收过程。。最简单的方式。是将另外半个凸壳和折线全部放在一起排序。。。
。。需要注意的是。。求凸包的时候。。如果存在共线点。。需要全部算上。。
https://gist.github.com/lychees/5816430
Problem D. Observation Wheel
Brief description:
。。给定有 n 个槽位的一个旋转木马。。。游客到入口出时。。可能当前的槽位上面已经有人了。。需要等待一个空的槽位才能上去。。。
。。。为了缓和因等待而引起的不满情绪。。。等待的时间越久游客所支付的金币越少。。(初始为 N。。每多等待一回合。可以优惠 1￥。。。
。。。。。给定当前旋转木马的占据信息。。问装满人时。。公园所获收益的期望。。。
。为了简化问题。。。我们认为游客随机且一个一个进入。。既不考虑 “排队” 情况。。。并且假定游客上去以后就不会下来。。。
（ Small n = 20, Large n = 200 ）。。。
Analysis:
Small dataset
In this problem we are interested in calculating the average amount of money we will make from filling up every gondola on our observation wheel. Because of linearity of expectation, this is equivalent to summing up the expected amount of money paid by each person. Given the fact that the amount a person pays doesn’t depend on the order in which gondolas got occupied, we can represent the current free/occupied state of gondolas as a bitmask and use dynamic programming to solve the small case.
Let E(mask) be the expected amount of money we make starting from the configuration represented by mask, where 0 represents an empty gondola, and 1 represents an occupied gondola. A person has a probability of 1/N of starting at any given position. Once that starting position is fixed, we simply find the first 0 following it (in cyclic order), and that’s where the person will eventually end up.
We’ll define f(i) as the index of the gondola occupied by a person who starts at position i. Similarly, let c(i) be the amount of money this person pays, as per the problem statement. Then we have the following recurrence:
E(mask)=1/N*∑i=0..N-1(E(mask | (1 << f(i)) ) + c(i))
The bitwise operation here simply sets the bit corresponding to the gondola the user occupied. The base case is when there are no empty positions, in which case the expected amount of money is 0.
There are 2N states, each of which can be computed in linear time, so our time complexity is O(N*2N). This is pretty easy for the small data set, but unfortunately it’s far too slow for the large case.
。。。如果考虑最后一步只有一个空位的情况的话。。虽然代价是可以直接算出来的。。。但是中间过程似乎没有状态压缩以外的方法。。
https://gist.github.com/lychees/5818390
External link:
https://code.google.com/codejam/contest/2433487/dashboard#s=p1&a=1
