I did do a bit of searching and found out the missing piece in my logic.The algorithm that I used was a pretty basic one, where I find all the possible combinations of placement of mines in the grids depending on the size and and number of mines. Then I check for the following basic conditions: 1) Any cell which has non-zero number of mines surrounding it should have at least one cell with zero mines as neighbour. This will ensure that the cell is revealed if that zero cell is clicked. 2) Any cell which has zero mines surrounding it should have at least one zero cell as neighbour (provided that there are more than one of them), so that it is revealed if the other zero cell is clicked. Then it is a simple matter of replacing any of the zero cell with 'c'. This works pretty well for small input where maximum number of checks is 25C12, but for large input that number is going to be 2500C1250! But if I add the above piece by FILLING UP by the grid as suggested while still satisfying above constraints, I find the execution time reduced drastically. *Thanks to Diggory for the input!!*
But I feel that knowledge of algorithms will still provide me an edge in upcoming rounds. I can come up with methods of my own, but it takes a lot of time which is not good if I want compete in further rounds. So please do suggest me some good books targeted at programming contests with special focus on algorithms. On Wed, Apr 16, 2014 at 6:25 PM, Diggory Blake <[email protected]>wrote: > On Tuesday, 15 April 2014 07:39:01 UTC+1, Abhilash Kulkarni wrote: > > Hi everyone, > > I am newbie to competitive programming contest; this code jam was my > first one. I was able to solve the minesweeper master problem and got > correct result for the small input. But my code was perhaps pretty bad and > the execution time for large input crossed the time limit. > > My question is, is it necessary to make separate versions of the program > for small input and large input, and what strategies must we apply to > handle large inputs effectively? Is it necessary to have knowledge of > special algorithms, especially considering that future rounds may contain > more such questions. > > Also please suggest me some good books for algorithms, as I find online > tutorials to limited in detail. > > Thanks in advance! > > Any program that can solve the large inputs should also be able to solve > the small inputs. The main thing to recognise in minesweeper was that the > cell to click should always be in the corner, so it's a case of filling up > the rest of the grid leaving a gap in one corner, plus some special rules > to avoid breaking the constraints. > There are more in-depth explanations around if you search a bit. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/3e8e0df4-882a-420a-a037-21c7c1c1dbbb%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAOxYQk11XJ2Smxugd8%3Djs1RvJck3AXk6MUcqLsaL%3DaMYgmcxnw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
