tag:blogger.com,1999:blog-29632375.post3200138014409178817..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: Google Codejam 2013 Qualification RoundUnknownnoreply@blogger.comBlogger10125tag:blogger.com,1999:blog-29632375.post-89106198931842198192013-06-01T19:10:05.208-07:002013-06-01T19:10:05.208-07:00Hey try finding a solution to that problem on go-h...Hey try finding a solution to that problem on go-hero.net in your favourite language and run it on your input. Then you should get the correct output file and do a diff :)xnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-75439176451688317872013-04-15T11:06:13.781-07:002013-04-15T11:06:13.781-07:00Would anyone be willing to post the correct output...Would anyone be willing to post the correct output file for problem B (lawnmower) large? I have tried a million times over but cannot get a correct solution accepted, though in every single attempt passed the small set with flying colors. I am trying to see which cases I messed up to nail where my problem is at. Thanks!DC2noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-71423362203663153832013-04-15T06:40:15.687-07:002013-04-15T06:40:15.687-07:00They posted an analysis in the contest dashboard.
...They posted an analysis in the contest dashboard.<br /><br />But it is all about how there should be no carry operations when raising to square.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-61620410498808004272013-04-15T02:12:01.984-07:002013-04-15T02:12:01.984-07:00I got stuck on this problem. Would you mind explai...I got stuck on this problem. Would you mind explaining why sum can not be higher that 9?fakalakanoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-33928167885435968642013-04-14T05:00:42.263-07:002013-04-14T05:00:42.263-07:00D Large - brute force with one more additional che...D Large - brute force with one more additional check:<br />Before each step of recursion do the following:<br />- sum up all remaining keys less chests and check that all numbers are positive (so before recursion we know that branch we going to check is theoretically solvable)<br />- pretend that keys do not disappear after they used and under that condition quickly check that the branch is solvable.<br /><br /><br />Just this two things speed up things enough to solve D-large in seconds. Without saying how stupid I was... I would say that we were cheated - I mean, the problem was really MUCH easier than we thought and that was the biggest problem coming up with solution. Instead of thinking about Dynamic programming, Graphs, Max Flows and all other clever things, we should have just think about optimizing brute force a little bit. Oh.Stanislav Zholninnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-45645836755301121482013-04-13T23:48:06.338-07:002013-04-13T23:48:06.338-07:00Nice analysis, ... I also couldn't come up wit...Nice analysis, ... I also couldn't come up with D-large solution, and my D-small approach is exactly like what you described.<br />On C-large, very interesting that even I first thought of the 3^25 thing, ... that's still too large a number, I think ... but then the OEIS page has something really interesting, ... the palindromic square root has to have its sum of square of its digits to be strictly less than 10, ... only then if it is squared, it will also result in a palindrome. Of course I don't have the proof, that's why I'm waiting for some analysis ... I did solve it during the contest using python, not too bad, ... so all in all, I'm interested to see the analysis of D-large and the proof of C-large-2.turuthoknoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-37917109115589742742013-04-13T21:33:11.694-07:002013-04-13T21:33:11.694-07:00The solution I see now (which does Large input in ...The solution I see now (which does Large input in few seconds) is really a brute-force with just one more smart idea to limit search tree. How stupid I was - I added just one line to my solution and now it works with the same speed.Stanislav Zholninnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-18215058950161440092013-04-13T21:16:24.476-07:002013-04-13T21:16:24.476-07:00For D - I was 100 times reading this phrase about ...For D - I was 100 times reading this phrase about "not more than 400 keys" which in my opinion was pointing to graphs or dynamic programming, or something which treats keys individually, not by type, but I failed to come up with any reasonable solution.<br /><br /><br />I am still to review actual solutions submitted by people.Stanislav Zholninnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-86340125167053397662013-04-13T21:14:34.936-07:002013-04-13T21:14:34.936-07:00For C - sum of all digits in number cannot be high...For C - sum of all digits in number cannot be higher than 9. This means that it can't be higher than 4 in half-number. This leaves us with all permutations of 1,2,3's and 0's with sum not more than 4 to check, which is really not much. (you also should think what you use to glue the halves - you can use "", "0", "1" or other numbers so that total sum is less than 9). Then you just find all needed numbers. Very fast. I think I could do 10^200 with the same code.Stanislav Zholninnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-75470774072745334892013-04-13T20:52:46.187-07:002013-04-13T20:52:46.187-07:00It seems D is greedy. According to the top solutio...It seems D is greedy. According to the top solutions, it seems.<br /><br /><br />2 at the ends and center is a great idea.vexoriannoreply@blogger.com