tag:blogger.com,1999:blog-31847281.post3947129109452660500..comments2019-04-01T07:08:54.502-07:00Comments on Entropy always increases: ACM ICPC 2014Bruce Merrynoreply@blogger.comBlogger12125tag:blogger.com,1999:blog-31847281.post-14003176458869344202015-12-17T03:54:44.752-08:002015-12-17T03:54:44.752-08:00Hi, anyone knows about problem I (sensor network)?...Hi, anyone knows about problem I (sensor network)? I tried hard to solve but unfortunately I couldn't. Any help please. Yahia Assalimyhttps://www.blogger.com/profile/06836911417106177477noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-21604926966023697372014-09-16T08:47:42.660-07:002014-09-16T08:47:42.660-07:00I am amazed at your level of understanding of algo...I am amazed at your level of understanding of algortihms. I am trying to prepare for the next years ACM ICPC and was pracitising a few problems. I came across the shortest flight path problem from 2012. I havent been able to wrap my head around it. Would you mind giving me headstart on this?James Knothttps://www.blogger.com/profile/18305409108220344752noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-89231380537702777712014-07-08T16:30:22.528-07:002014-07-08T16:30:22.528-07:00Great analysis!
Can you post your code for B conti...Great analysis!<br />Can you post your code for B continues part?<br />Thank you very muchstefano tommasinihttps://www.blogger.com/profile/07781132815759456107noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-40385630807258761752014-06-30T08:31:32.566-07:002014-06-30T08:31:32.566-07:00@Bruce Merry thank you, but it was my centroid for...@Bruce Merry thank you, but it was my centroid formula that was totally wrong, I got the right one from here<br />http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon<br />and got accepted...Zetahttps://www.blogger.com/profile/08665531899030604720noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-82254665654289037182014-06-27T17:53:21.560-07:002014-06-27T17:53:21.560-07:00Hi Bruce,
thanks for the analysis (though I proba...Hi Bruce,<br /><br />thanks for the analysis (though I probably will try first before reading the solutions in detail). I did (and solved) problem A on te plane, described here: http://keet.wordpress.com/2014/06/28/acm-icpc-2014-solution-to-problem-a-baggage/<br /><br />Regards,<br />MariaMaria Keethttps://www.blogger.com/profile/00414155544040626325noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-43722017074562996262014-06-27T07:11:05.270-07:002014-06-27T07:11:05.270-07:00This comment has been removed by the author.Unknownhttps://www.blogger.com/profile/17552123827575738114noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-33914222708441836822014-06-27T07:08:03.079-07:002014-06-27T07:08:03.079-07:00This comment has been removed by the author.Unknownhttps://www.blogger.com/profile/17552123827575738114noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-14757676070579723382014-06-26T18:11:32.806-07:002014-06-26T18:11:32.806-07:00Got it!
Thank Bruce! That was a nice trickGot it!<br />Thank Bruce! That was a nice trickJohn Strawfordhttps://www.blogger.com/profile/12073699609778740105noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-68383839528633648012014-06-26T11:53:36.273-07:002014-06-26T11:53:36.273-07:00@John: me saying "binary search" is slig...@John: me saying "binary search" is slightly misleading. Instead, I work out the bits of c-1, from most significant to least significant. For each bit, I try adding a power of 2 (precomputed) to the candidate number I have, and if the resulting value still doesn't have a jump length of N then I keep the change, otherwise I revert it. It ends up testing exactly the values that a binary search does starting with endpoints at 0 and a large enough power of 2, but each midpoint is computed by adding a power of 2 to the lower bound.<br /><br />@Zeta: I'm not sure. It's most likely just an implementation error: I had to go through a few iterations of bugfixing before I solved the sample.Bruce Merryhttps://www.blogger.com/profile/02150601792587963530noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-60447901333760984612014-06-25T23:56:08.306-07:002014-06-25T23:56:08.306-07:00Thank you, you're the first one posting an ana...Thank you, you're the first one posting an analysis for the problems of the world finals, I was a contestant and I didn't even understand what was the question in problem C (Crane Balancing), and now after seeing your tutorial I implemented it and it gives 0 .. 250 instead of 0 .. 1017 for the first sample test case? is there anything else to be done in that problem? thank youZetahttps://www.blogger.com/profile/08665531899030604720noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-12879577183522795522014-06-25T23:34:55.927-07:002014-06-25T23:34:55.927-07:00This comment has been removed by the author.John Strawfordhttps://www.blogger.com/profile/12073699609778740105noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-86592868218879662472014-06-25T23:34:18.151-07:002014-06-25T23:34:18.151-07:00Great analysis!
I was wondering how you end up wit...Great analysis!<br />I was wondering how you end up with O(N log N) for problem K.<br />If I understand well your approach, given a value c, find if Jc contains a value that is at least N costs O(N).<br />I know how to do it in O(N log N), which leads to an O(N log^2 N) time, but I can't get the idea for O(N).<br />Can you elaborate this, or point me some reference where I can read how to achieve it?<br /><br />Thanks.John Strawfordhttps://www.blogger.com/profile/12073699609778740105noreply@blogger.com