Continuing solving USACO

It is embarrassing, but I haven't finished USACO training pages. Even though I have started doing them a while ago. I decided to be done with all of the problems by the end of the August, 2009.

The problem that I finally finished was Primes (prime3). This problem is from IOI 94 and once you know what to do it just takes time to implement. My solution is over 230 lines of actual code. In this problem you are always given a field 5 x 5 you need to fill with digits such that all rows, columns and both diagonals when concatenated each would be a five digit prime number and also the sum of the digits of those primes have to equal to the given sum. Also the digit at the cell (1, 1) is also given.

It's a brute-force problem with optimizations. You have to carefully optimize your solution in order to pass time limit. I submitted many solutions which got TLE. I eventually understood how to solve the problem after reading nice post by ar2rd. The most important optimization is the order in which you fill out the table. Here is the "magic" order:
Fill out main diagonal and then secondary diagonal.
Next fill the first row.
Then second and forth columns.
Next compute the third digit of the fifth row.
Then do the second column.
Finally do the rows two, three and four.
At the end just check if the column one and five are correct (are primes and sum of digits is equal to the given) then memorize the solution.
Also, the other optimization that I did was to precompute all five digit primes with the sum of digits equal to the given and then I used them when I was fill out the table.
That's it!