tag:blogger.com,1999:blog-29632375.post4519792441838154582..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: Google Code Jam 2012: Qualification roundUnknownnoreply@blogger.comBlogger5125tag:blogger.com,1999:blog-29632375.post-65874190824308971482012-04-15T05:47:38.465-07:002012-04-15T05:47:38.465-07:00Well, I guess they are just the mathematical or co...Well, I guess they are just the mathematical or computational views of the same problem :)César Puertanoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-23247922019284111262012-04-15T05:33:43.978-07:002012-04-15T05:33:43.978-07:00I think this is exactly Fred Coughlin's algori...I think this is exactly Fred Coughlin's algorithm. From what he explained, it is probably fine. The tops and people that have been too long in these contests like me prefer to do dp and bruteforce - even though the amount of code looks longer, it is much easier to think of those solutions and they don't need proof. But it does not necessarily mean the easier solutions are wrong.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-19222664859571146232012-04-15T02:44:44.546-07:002012-04-15T02:44:44.546-07:00I wrote a very simple solution for B and I'm w...I wrote a very simple solution for B and I'm wondering if something might be wrong with it? Every other solution I've seen is much harder.<br /><br />In order to have a best result of at least p with no surprises, you need a score of 3*p-2 or above. If you factor in surprises (only for a score >=2), you can then accept 3*p-3 and 3*p-4. The final solution looks like this:<br /><br /> int remainingSurprises = Surprises;<br /> int count = 0;<br /> foreach (var score in Scores)<br /> {<br /> if (score >= 3 * Threshold - 2)<br /> {<br /> ++count;<br /> }<br /> else if (score >= 2 && score >= 3 * Threshold - 4 && remainingSurprises > 0)<br /> {<br /> ++count;<br /> --remainingSurprises;<br /> }<br /> }<br /> return count;César Puertanoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-90663585210281844962012-04-14T20:56:42.190-07:002012-04-14T20:56:42.190-07:00awesome work, I actually tried only the first one....awesome work, I actually tried only the first one.. hehe most one did it thoughharshaduranoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-75574713258337417782012-04-14T18:55:14.983-07:002012-04-14T18:55:14.983-07:00FYI, B could be solved greedily. For a given scor...FYI, B could be solved greedily. For a given score, its scores given by the judges were unique in both the surprising and the unsurprising cases. Analysis of those cases leads to a simple formula for surprising and unsurprising. Then you can go through the scores, and greedily assign the surprising scores.Fred Coughlinnoreply@blogger.com