tag:blogger.com,1999:blog-29632375.post8746942358376552354..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: Codeforces round #102 div2Unknownnoreply@blogger.comBlogger7125tag:blogger.com,1999:blog-29632375.post-10059516010133752172012-01-16T12:22:47.194-08:002012-01-16T12:22:47.194-08:00Is another way to look at this as a 7x7x? ([9-2]x[...Is another way to look at this as a 7x7x? ([9-2]x[9-2]x?) problem? i.e. pick any box in a 3x3 set as the anchor for a shape, there are only 49 places that anchor can go, and there are only 4 arrangements of the piece that can use each anchor. and each time you place a piece, you reduce the number of arrangements at 18 or 20 nearby anchors by 2, 3 or 4.Dr. Bitboynoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-11055449831415680082012-01-15T11:11:26.656-08:002012-01-15T11:11:26.656-08:00I think the search space gets smaller if you requi...I think the search space gets smaller if you require any new piece to "touch" an existing piece. I thought there was a problem with this because sometimes you want a new piece X to leave a space between it and the existing spaces for piece Y, but I think it unlikely that any piece will touch no other pieces, so piece X will be placed further down the search path after piece Y.Dr. Bitboynoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-64141225293949796792012-01-14T21:18:33.384-08:002012-01-14T21:18:33.384-08:00Thing is that my current solution is quite long an...Thing is that my current solution is quite long and messy. <br /><br />It is really just a couple of optimizations that started with the normal (and awfully slow) brute force solution.<br /><br />There are two parts which I tried to explain in the blog:<br />- "Pseudo dynamic programming". Whenever my recursion reaches a new row, and it turns out that the row and all the (X-1) rows on top are all empty, then it is just as if we were solving the case when the height is X. Thus we can solve for height = 0, then height = 1 then height = 2 and just include something in the recursion to reuse the best solution for smaller heights if it is possible.<br /><br />For example, imagine you are in the middle of the recursion for 5 rows and you just filled rows 1, 2 and 3. Rows 3, 4 and 5 are empty. We can just get the result for 3 rows (which will probably have some shapes) and replace the characters in those shapes with new characters A-Z that do not coincide the ones you have already added. This makes it possible to precalculate the cases in 40 minutes. But is still very slow.<br /><br />- The second part is the density idea. The idea is that when you are doing backtracking for bruteforce, you should stop recursion if you find that the total number of shapes you have added so far in all your visited cells is not large enough. So you keep two variables in your recursion u, n - U is the number of used cells and n the number of cells you have already visited. Now, for optimal plaments, we want n/u to be as large as possible, and if n/u is currently too small, then it is unlikely the case we are trying is the optimal one. You need to know what is a good constant for the necessary "density" (Picking the largest one that allows the solution to run in time is good enough).<br /><br />--------------<br />Speaking of that. If you made a solution that recursively tries to add shapes to squares but you included something that forced it stop before 3 minutes and just outpuits the current best result you found it should work (And Dr. Bitboy apparently found solutions that do this).<br /> This approach should work for the same density idea. You will normally first try to add shapes in your recurion before trying not adding anything at all, this should mean that the optimal case is easy to find fast.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-29657255542547895592012-01-14T20:53:57.677-08:002012-01-14T20:53:57.677-08:00vexorian,your solutions and explainations are quit...vexorian,your solutions and explainations are quite gud,except for the last one("help caretaker"),can u give some more comprehensive approach to solve it......Anubhaw Rajnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-70461053513163766132012-01-14T18:09:04.210-08:002012-01-14T18:09:04.210-08:00Nice quick summary, thanks!
My 8x8 bruteforce for...Nice quick summary, thanks!<br /><br />My 8x8 bruteforce for D is still running, top says 1598 minutes so far (i think there is something wrong;-). One solution I saw simply watched the clock and returned an answer after so many ticks. Another had a precalculated solution for every possible input, yes all 81 of them.<br /><br />Btw, gotta love this:<br /><br /> if (n == 1) { <br /> //Every one! <br /> return n*m;<br />}<br /><br />wait for it ... yeah!! that moment of dawn comprehension we all live for!Dr. Bitboynoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-10589091709012416422012-01-13T05:00:02.667-08:002012-01-13T05:00:02.667-08:00I second that :)I second that :)Brunonoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-10054549849104753732012-01-12T20:08:52.820-08:002012-01-12T20:08:52.820-08:00Vexorian, I love you man (in a totally admiration ...Vexorian, I love you man (in a totally admiration sense;) ). Thanks for the excellent explanations.Shuaibnoreply@blogger.com