The content analysis is 2 pages long and evidently not clear enough. Unless someone is willing to up the ante with a 5-page explanation, it might help if you tell us exactly which part of the analysis isn't clear to you. I see a few sections:
1. Understanding the question itself. 2. How to realize that a brute-force solution won't be fast enough. 3. How to build an array that's as large as the bark, where each position contains a number; this number represents the maximum size chessboard you could cut out from this position, by going up and left. e.g. in the example chessboard image when you read the problem description, the bottom-right pixel of the '1' chessboard would contain the number '6', as you can cut out a chessboard up to size 6 by going up and left from that bottom-right pixel. 4. How to prove that the above process is fast (to be precise: takes linear to m * n time). 5. How to prove that the above process allows you to select the next chessboard to cut out (you need to cut out the largest board which is the closest to the top, and then the left). 6. Understanding the need to recalculate a number of squares in this 'how big a chessboard can I cut from here if I go up and left' array after you cut out a chessboard. 7. How to do this recalculating and understanding that you only need to recalculate a small number of pixels, and understanding that this recalculate effort will be very fast (linear to n time, where n is the size of the chessboard you just cut out, to recalculate every pixel that needs it). 8. Understanding that by recursively cutting out the largest (and if multiple, highest, then most towards the left) board by looking at your 'how big a chessboard can I cut from here if I go up and left' array, then recalculating a few squares, and repeating the process, you'll end up cutting out just the right chessboard squares, in a total time that will easily finish in time given the large constraints (512 x 512 board), *but only* if you've first turned that array of 'how big a chessboard...' into a sorted list, so finding the next board to cut out always takes constant time instead of linear to 512 * 512. On May 27, 7:25 am, Manish kumar Singh <[email protected]> wrote: > http://code.google.com/codejam/contest/dashboard?c=619102#s=a&a=2 -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
