{"id":743,"date":"2013-06-20T02:22:02","date_gmt":"2013-06-19T18:22:02","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=743"},"modified":"2013-06-21T06:12:19","modified_gmt":"2013-06-20T22:12:19","slug":"google-code-jam-2013-round-3","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/google-code-jam-2013-round-3\/","title":{"rendered":"Google Code Jam 2013 Round 3"},"content":{"rendered":"

Problem A. …..<\/h2>\n

Brief description: <\/h3>\n

\u3002\u3002\u3002\u8f6c\u76d8\u8d4c\u535a\u95ee\u9898\u3002\u3002\u4e00\u5171\u6709 37 \u4e2a\u6570\u5b57\u3002\u3002\u8f6c\u5230\u67d0\u4e2a\u6570\u5b57\u540e\u5f97\u5230\u8fd9\u4e2a\u6295\u6ce8\u7684 36 \u500d\u3002\u3002\u3002\uff08\u8d1f\u548c\uff1f
\n\u3002\u3002\u73b0\u5728\u4f60\u53d1\u73b0\u8d4c\u573a\u7684\u8fd9\u4e2a\u88c5\u7f6e\u662f\u6709\u95ee\u9898\u7684\u3002\u3002\u65e2\u6bcf\u6b21\u53ea\u4f1a\u968f\u673a\u505c\u7559\u5728\u6295\u6ce8\u6700\u5c11\u7684\u6570\u5b57\u4e0a\u3002\u3002
\n\u4f60\u51b3\u5b9a\u4e3e\u62a5\u4e4b\u524d\u3002\u3002\u5148\u5c3d\u53ef\u80fd\u635e\u56de\u672c\u3002\u3002\u3002\u4e8e\u662f\u4f60\u51b3\u5b9a\u4e0b\u4e00\u8f6e\u6700\u540e\u4e00\u4e2a\u6295\u6ce8\u3002\u3002\u7ed9\u5b9a\u4f60\u5f53\u524d\u7684\u7b79\u7801\u548c\u76ee\u524d\u7684\u5c40\u9762\u3002\u3002\u3002
\n\u3002\u3002\u3002\u95ee\u4f60\u6b64\u8f6e\u7684\u6700\u5927\u7684\u671f\u671b\u6536\u76ca\u662f\u591a\u5c11\u3002\u3002\uff09
\n<\/p>\n

Analysis: <\/h3>\n

… \u679a\u4e3e + \u4e8c\u5206\u7b54\u6848\u3002\u3002
\nhttps:\/\/gist.github.com\/lychees<\/a><\/p>\n

Problem B. Rural Planning<\/h2>\n

Brief description: <\/h3>\n

\u3002\u3002\u7ed9\u5b9a\u4e00\u4e2a\u89c4\u6a21\u4e3a n \u7684\u70b9\u96c6\uff0c\u8981\u6c42\u7ed9\u51fa\u4e00\u4e2a\u957f\u5ea6\u4e3a n \u7684\u6392\u5217\u3002
\n\u4f7f\u5f97\u4f9d\u636e\u6b64\u6392\u5217\u987a\u6b21\u8fde\u63a5\u8fd9\u4e9b\u70b9\u6240\u5f62\u6210\u7684\u591a\u53d8\u5f62\u4e0d\u4ea7\u751f\u76f8\u4ea4\uff0c\u4e14\u9762\u79ef\u6bd4\u8fd9\u7ec4\u70b9\u96c6\u6240\u5f62\u6210\u7684\u51f8\u5305\u7684\u9762\u79ef\u7684\u4e00\u534a\u8981\u5927\u3002
\n( Small n = 10, Large n = 1000 )<\/p>\n

Analysis: <\/h3>\n

… Small \u7684\u8bdd\u3002\u3002\u5224\u65ad\u7ebf\u6bb5\u76f8\u4ea4\u5c31\u53ef\u4ee5\u3002\u3002\uff08\u679a\u4e3e\u6240\u6709\u6392\u5217\u3002\u3002\u66b4\u529b\u68c0\u6d4b\u3002\u3002\u3002
\nhttps:\/\/gist.github.com\/lychees\/5815413<\/a><\/p>\n

\u3002\u3002\u4e4b\u540e\u8003\u8651\u4e3a\u4ec0\u4e48\u6ee1\u8db3\u6761\u4ef6\u7684\u89e3\u4e00\u5b9a\u5b58\u5728\u3002\u3002
\n\u3002\u3002\u5982\u56fe\u3002\u3002\u5c06\u51f8\u5305\u8fd9\u6837\u5206\u6210\u4e24\u534a\u3002\u3002\u5fc5\u6709\u4e00\u90e8\u5206\u7684\u9762\u79ef >= \u51f8\u5305\u9762\u79ef\u7684\u4e00\u534a\u3002<\/p>\n

\"\"<\/p>\n

\u3002\u3002\u6211\u4eec\u7528\u5927\u7684\u53bb \u201c\u5438\u6536\u201d \u5c0f\u7684\u3002\u3002\u6240\u5f62\u6210\u7684\u56fe\u5f62\u7684\u9762\u79ef\u5fc5\u5b9a\u8fd8\u4f1a\u589e\u52a0\u3002\u3002\u56e0\u6b64\u6700\u540e\u4e00\u5b9a > \u51f8\u5305\u9762\u79ef\u7684\u4e00\u534a\u3002
\n\u3002\u3002\u8003\u8651\u5438\u6536\u8fc7\u7a0b\u3002\u3002\u6700\u7b80\u5355\u7684\u65b9\u5f0f\u3002\u662f\u5c06\u53e6\u5916\u534a\u4e2a\u51f8\u58f3\u548c\u6298\u7ebf\u5168\u90e8\u653e\u5728\u4e00\u8d77\u6392\u5e8f\u3002\u3002\u3002
\n\u3002\u3002\u9700\u8981\u6ce8\u610f\u7684\u662f\u3002\u3002\u6c42\u51f8\u5305\u7684\u65f6\u5019\u3002\u3002\u5982\u679c\u5b58\u5728\u5171\u7ebf\u70b9\u3002\u3002\u9700\u8981\u5168\u90e8\u7b97\u4e0a\u3002\u3002
\nhttps:\/\/gist.github.com\/lychees\/5816430<\/a><\/p>\n

Problem D. Observation Wheel<\/h2>\n

Brief description: <\/h3>\n

\u3002\u3002\u7ed9\u5b9a\u6709 n \u4e2a\u69fd\u4f4d\u7684\u4e00\u4e2a\u65cb\u8f6c\u6728\u9a6c\u3002\u3002\u3002\u6e38\u5ba2\u5230\u5165\u53e3\u51fa\u65f6\u3002\u3002\u53ef\u80fd\u5f53\u524d\u7684\u69fd\u4f4d\u4e0a\u9762\u5df2\u7ecf\u6709\u4eba\u4e86\u3002\u3002\u9700\u8981\u7b49\u5f85\u4e00\u4e2a\u7a7a\u7684\u69fd\u4f4d\u624d\u80fd\u4e0a\u53bb\u3002\u3002\u3002
\n\u3002\u3002\u3002\u4e3a\u4e86\u7f13\u548c\u56e0\u7b49\u5f85\u800c\u5f15\u8d77\u7684\u4e0d\u6ee1\u60c5\u7eea\u3002\u3002\u3002\u7b49\u5f85\u7684\u65f6\u95f4\u8d8a\u4e45\u6e38\u5ba2\u6240\u652f\u4ed8\u7684\u91d1\u5e01\u8d8a\u5c11\u3002\u3002(\u521d\u59cb\u4e3a N\u3002\u3002\u6bcf\u591a\u7b49\u5f85\u4e00\u56de\u5408\u3002\u53ef\u4ee5\u4f18\u60e0 1\uffe5\u3002\u3002\u3002
\n\u3002\u3002\u3002\u3002\u3002\u7ed9\u5b9a\u5f53\u524d\u65cb\u8f6c\u6728\u9a6c\u7684\u5360\u636e\u4fe1\u606f\u3002\u3002\u95ee\u88c5\u6ee1\u4eba\u65f6\u3002\u3002\u516c\u56ed\u6240\u83b7\u6536\u76ca\u7684\u671f\u671b\u3002\u3002\u3002
\n\u3002\u4e3a\u4e86\u7b80\u5316\u95ee\u9898\u3002\u3002\u3002\u6211\u4eec\u8ba4\u4e3a\u6e38\u5ba2\u968f\u673a\u4e14\u4e00\u4e2a\u4e00\u4e2a\u8fdb\u5165\u3002\u3002\u65e2\u4e0d\u8003\u8651 \u201c\u6392\u961f\u201d \u60c5\u51b5\u3002\u3002\u3002\u5e76\u4e14\u5047\u5b9a\u6e38\u5ba2\u4e0a\u53bb\u4ee5\u540e\u5c31\u4e0d\u4f1a\u4e0b\u6765\u3002\u3002\u3002
\n\uff08 Small n = 20, Large n = 200 \uff09\u3002\u3002\u3002<\/p>\n

Analysis: <\/h3>\n
\n
Small dataset<\/h5>\n

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\u2019t 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.<\/p>\n

Let E<\/b>(mask<\/b>) be the expected amount of money we make starting from the configuration represented by mask<\/b>, where 0 represents an empty gondola, and 1 represents an occupied gondola. A person has a probability of 1\/N<\/b> 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\u2019s where the person will eventually end up. <\/p>\n

We\u2019ll define f<\/b>(i<\/b>) as the index of the gondola occupied by a person who starts at position i<\/b>. Similarly, let c<\/b>(i<\/b>) be the amount of money this person pays, as per the problem statement. Then we have the following recurrence:<\/p>\n

E<\/b>(mask<\/b>)=1\/N<\/b>*\u2211i<\/b>=0..N<\/b>-1<\/sub>(E<\/b>(mask<\/b> | (1 << f<\/b>(i<\/b>)) ) + c<\/b>(i<\/b>))<\/p>\n

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.<\/p>\n

There are 2N<\/b><\/sup> states, each of which can be computed in linear time, so our time complexity is O(N<\/b>*2N<\/b><\/sup>). This is pretty easy for the small data set, but unfortunately it\u2019s far too slow for the large case.<\/p>\n<\/blockquote>\n

\u3002\u3002\u3002\u5982\u679c\u8003\u8651\u6700\u540e\u4e00\u6b65\u53ea\u6709\u4e00\u4e2a\u7a7a\u4f4d\u7684\u60c5\u51b5\u7684\u8bdd\u3002\u3002\u867d\u7136\u4ee3\u4ef7\u662f\u53ef\u4ee5\u76f4\u63a5\u7b97\u51fa\u6765\u7684\u3002\u3002\u3002\u4f46\u662f\u4e2d\u95f4\u8fc7\u7a0b\u4f3c\u4e4e\u6ca1\u6709\u72b6\u6001\u538b\u7f29\u4ee5\u5916\u7684\u65b9\u6cd5\u3002\u3002
\nhttps:\/\/gist.github.com\/lychees\/5818390<\/a><\/p>\n

External link: <\/h3>\n

https:\/\/code.google.com\/codejam\/contest\/2433487\/dashboard#s=p1&a=1<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Problem A. ….. Brief description: \u3002\u3002\u3002\u8f6c\u76d8\u8d4c\u535a\u95ee\u9898\u3002\u3002\u4e00\u5171\u6709 37 \u4e2a\u6570\u5b57\u3002\u3002\u8f6c\u5230\u67d0\u4e2a\u6570\u5b57\u540e\u5f97\u5230\u8fd9\u4e2a\u6295\u6ce8\u7684 36 \u500d\u3002\u3002\u3002\uff08\u8d1f\u548c\uff1f \u3002\u3002\u73b0\u5728\u4f60\u53d1\u73b0\u8d4c\u573a\u7684\u8fd9\u4e2a\u88c5\u7f6e\u662f\u6709\u95ee\u9898\u7684\u3002\u3002\u65e2\u6bcf\u6b21\u53ea\u4f1a\u968f\u673a\u505c\u7559\u5728\u6295\u6ce8\u6700\u5c11\u7684\u6570\u5b57\u4e0a\u3002\u3002 \u4f60\u51b3\u5b9a\u4e3e\u62a5\u4e4b\u524d\u3002\u3002\u5148\u5c3d\u53ef\u80fd\u635e\u56de\u672c\u3002\u3002\u3002\u4e8e\u662f\u4f60\u51b3\u5b9a\u4e0b\u4e00\u8f6e\u6700\u540e\u4e00\u4e2a\u6295\u6ce8\u3002\u3002\u7ed9\u5b9a\u4f60\u5f53\u524d\u7684\u7b79\u7801\u548c\u76ee\u524d\u7684\u5c40\u9762\u3002\u3002\u3002 \u3002\u3002\u3002\u95ee\u4f60\u6b64\u8f6e\u7684\u6700\u5927\u7684\u671f\u671b\u6536\u76ca\u662f\u591a\u5c11\u3002\u3002\uff09<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[67],"tags":[],"class_list":["post-743","post","type-post","status-publish","format-standard","hentry","category-google-code-jam"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-bZ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/743","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=743"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/743\/revisions"}],"predecessor-version":[{"id":744,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/743\/revisions\/744"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=743"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=743"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=743"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}