某島

… : "…アッカリ~ン . .. . " .. .
June 20, 2013

Google Code Jam 2013 Round 3

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