tag:blogger.com,1999:blog-34454975.post5815643251377907790..comments2023-06-28T16:58:41.189+02:00Comments on Web Reflection: Google Code Jam: Mousetrap in 4 languages - GAME OVERAndrea Giammarchihttp://www.blogger.com/profile/16277820774810688474noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-34454975.post-21834274914359697672008-07-30T21:23:00.000+02:002008-07-30T21:23:00.000+02:00Well done, that's why I am not good for GCJ, I use...Well done, that's why I am not good for GCJ, I use different stuff every day, and think about a binary tree or log something is not my daily tasks, while somebody solved all problems in two hours: respect!<BR/><BR/>Anyway, the next post shows my poor solution, implemented in a better C language, the fifth one :D<BR/><BR/>Fast enough to solve up to 5000 cards deck, not enough, as you said, for large data set.<BR/><BR/>Kind RegardsAndrea Giammarchihttps://www.blogger.com/profile/16277820774810688474noreply@blogger.comtag:blogger.com,1999:blog-34454975.post-27641432293313501112008-07-30T21:13:00.000+02:002008-07-30T21:13:00.000+02:00I finally solved it using binary tree. Counting to...I finally solved it using binary tree. Counting to find the space to create perfect deck is fine, but normal counting is O(n^2). To solve this issue, I use binary tree to do partitioning of the available space. This would help reduce to O(n log n), which is feasible for large set.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-34454975.post-45499601993881369702008-07-28T00:57:00.000+02:002008-07-28T00:57:00.000+02:00Miguel, this is absolutely true, other guys have b...Miguel, this is absolutely true, other guys have been more clever than us :)<BR/><BR/>Somebody was so smart that was able to commit all of them, 3 problems, finding directly a fast way to solve the problem.<BR/><BR/>The main difference I have spotted between their code and mine, for example, is that as was for the qualification, I simply though about a "universal solution" able to solve the problem, and not about an algorithm that is able to get quickly only "that" index.<BR/><BR/>At the same time, usage of bitwise operators, and other algos, is something I could not think at all in two hours, so that is why I would like to say good luck to every other developer, but before, I have to say Good stuff guys! :)Andrea Giammarchihttps://www.blogger.com/profile/16277820774810688474noreply@blogger.comtag:blogger.com,1999:blog-34454975.post-6358241680424893972008-07-27T22:14:00.000+02:002008-07-27T22:14:00.000+02:00Same experience here. I'm glad I have participated...Same experience here. I'm glad I have participated in Code Jam 2008 till round 1. I do too think the problems and the organization was good (though the time frames do not always fit my time zone nicely, I guess there is not a global optimum solution for this). <BR/><BR/>I've failed to create a fast enough solution for Ugly Numbers. As you said, my procedural approach worked in theory but it was too slow. <BR/><BR/>Other people however came up with a better (and faster) idea. Those continue the game :-)misanhttps://www.blogger.com/profile/10960543302205348008noreply@blogger.comtag:blogger.com,1999:blog-34454975.post-12827374331600130972008-07-27T14:46:00.000+02:002008-07-27T14:46:00.000+02:00Thank you Alsanan, and congratulations to you too....Thank you Alsanan, and congratulations to you too.<BR/><BR/>I am sure I have solved the problem, but speed was not enough (about half an hour to parse the small input with C# and my poor PC).<BR/><BR/>At the same time, this is the reson I am sure I used the wrong procedure as well, since it costs too much for every kind of CPU / processor.<BR/><BR/>Factorial switches are the main limit of my code, and I am sure there is a truly simple way to perform N switches with a single operation, that will bring Mousetrap execution close to zero.<BR/><BR/>I would like to find them, but at the same time I have to admit that for me, in two hours, I am not that clever to solve in a correct way, test results, and commit them.<BR/><BR/>So Google Code Jam is not for me, and I will follow next week problems too, and try to solve them in two hours, for a personal challenge (but I am sure, I will not be able to do that)<BR/><BR/>Kind RegardsAndrea Giammarchihttps://www.blogger.com/profile/16277820774810688474noreply@blogger.comtag:blogger.com,1999:blog-34454975.post-16294703330328275272008-07-27T14:21:00.000+02:002008-07-27T14:21:00.000+02:00I've solved both A and B as seen here but the comp...I've solved both A and B as seen <A HREF="http://digitta.com/2008/07/no-pudo-ser.html" REL="nofollow">here</A> but the complexity of the data sets has made impossible to get the results.<BR/><BR/>Congratulations anyway. May be some more examples would help to understand the problems.Anonymousnoreply@blogger.com