USACO - Ordered Fractions

One way to solve this problem is to construct all possible fractions, reduce all of them as possible, sort them and print them.

Another way is to use DFS.
 

Lets start with (0,1) and see what can we build? (Check it yourself)
and fraction is something like this :
 

USACO - The Castle

Think about problem, what does the problem wants? We have a grid and we want to find the number of connected components in this grid, the largest component before breaking a wall, and the largest component after breaking a wall, we also need the wall itself.

To find connected components one can easily use DFS.
int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
To deal with neighbors I have this array 'dir', a[i][j] is the value of cell (i, j), I want to know whether I can go to the other cells connected to (i, j) or not.

 

After DFS, I iterate over cells as the problem statement wants and check it's neighbors, if its neighbor is in another component I check the size of the merged component to the maximum size found.

USACO - Checker Challenge

If you are familiar with n-queen problem, when you are reading the problem statement you will remember that problem, Yes we are facing a n-queen problem, we want to count different ways to put n queens in a n*n board.

For those not familiar with n-queen problem

From Wikipedia, the free encyclopedia :
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of 2 and 3.

We have to construct solutions, but how? We know that in each row and each column we have to put just one queen, the same thing applies to the diagonals.
So we start building solutions from row 1, we place one queen in row 1 column  j, for each j, recursively we put queens in appropriate columns. When we are putting a queen in column j, how do we know that this is an appropriate column? I have an array named bool column[n], which states whether there is a queen in column j (which has been put there in the previous rows.) This array suffices to check column condition, Row condition is already satisfied, because we are iterating over rows, but what about diagonals?
 
But how to mark diagonals so that we can check it in O(1),
Take a look at these diagonals, what is the relation between (row,column) in each diagonal. I write diagonals here :
4,1 -> column-row is -3
3,1 | 4,2 -> column-row is -2
2,1 | 3,2 | 4,3 -> column-row is -1
1,1 | 2,2 | 3,3 | 4,4 -> column-row is 0
1,2 | 2,3 | 3,4 -> column-row is 1
1,3 | 2,4 -> column-row is 2
1,4 -> column-row is 3

What about other kind of diagonals, I mean diagonals like /?
1,1 -> column+row is 2
2,1 | 1,2 -> column+row is 3
3,1 | 2,2 | 1,3 -> column+row is 4
4,1 | 3,2 | 2,3 | 1,4 -> column+row is 5
4,2 | 3,3 | 2,4 -> column+row is 6
4,3 | 3,4 -> column+row is 7
4,4 -> column+row is 8

So I have two other arrays diag1[128], diag2[128] which is used to mark each diagonal. 

USACO - Superprime Rib

As you know reading the problem statement carefully is crucial to find the first hints for solving the problem. After I noticed the structure of the problem, I found something important. Each number you print in the output, what is the first digit of that? 2, 3, 5 or 7, isn't it? Another thing is that you can find super prime numbers with length n, from the super prime numbers of length (n-1). If we have super prime numbers of length (n-1) which digits can we add to construct super prime numbers with length n? We can add 1, 3, 7 or 9 to the end of a super prime number of length (n-1) to build a number of length n which could be a super prime number of length n(if we add other digits to the end of that number it would be divisible by 2 or 5). After doing this we check whether it is a prime or not? To check whether a number is prime or not I refer you to my previous post about usaco-prime palindromes.

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everything gonna be alright ;-). My first approach was to find all the prime numbers in range 1...100,000,000 and check whether each of them is a palindrome or not? then push all the prime palindromes in an array and for input binary search for the first and last palindrome number. But soon I noticed that I can approach the problem from another aspect, produce all palindromes and check whether they are prime or not? So I had to have an idea about the number of palindromes less than 100,000,000, I started counting them.

1 digit (preferably prime) palindromes  --> 2 - 3 - 5 - 7 - 9 => 5 numbers

2 digit (preferably prime) palindromes --> 5 numbers.

3 digit (preferably prime) palindromes --> 50 numbers

4 digit (preferably prime) palindromes --> 50 numbers

5 digit (preferably prime) palindromes --> 500 numbers

6 digit (preferably prime) palindromes --> 500 numbers

....

I counted them using rule of product (multiplication principle).

They are not too many to check, I check each of them to see whether it is a prime or not, if yes I push them in an array. But the problem is how do we check an 8 digit palindrome to see whether it is a prime or not?
To see a number n is prime or not, you have to check all the prime numbers less than sqrt(n), if n is divisible by a prime number less than sqrt(n), then it is not prime, otherwise it is a prime. So at first I find all the prime numbers from 1...10000, which 10000 = sqrt(100,000,000). You can find these prime numbers using sieve of eratosthenes or just by checking each number to see it is prime or not. That's how I solved the problem:-).

USACO - Number Triangles

Take a look at the problem statement, take a look at  the boundaries, what about the structure of the solution? How is the solution like? It's a path from the top row to the bottom row, isn't it? So Let's break down the problem to a similar problem with the same shape, Can we? Let's assume we have R rows, Instead of finding the best path from row 1 to row R, let's find the best path from row 1 to row (R-1), if we have the best path from row 1 to row (R-1) can we find the best path from row 1 to row R? Yes of course, if our imaginary best path ends at (R,C) then it has to come from (R-1,C-1) or from (R-1, C) plus the value of (R,C).
So dp[r][c] = max(dp[r-1][c-1], dp[r-1][c]) + a[r][c]. And after filling the table we find the maximum value in the last row.

USACO - Arithmetic Progressions

Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing all possible values of p^2+q^2 good? Because they are not too many, and the biggest p^2+q^2 is when p=250 and q=250, in which p^2+q^2 = 125,000. So let's produce all of them.
Now take a look at N, If we brute force over the length of the progression, and start from each possible starting value, and check whether this start with this length can end up an arithmetic progression with N values? There is a little thing we have to be concerned about, after picking starting value and length of the progression, how do we check whether this would end up in a progression with N values?
Suppose the starting value is 13 and the length is 5, we want to know whether 18, 23, 28, 33 are available or not? To do so, when producing all possible p^2+q^2 just mark them in an array, if mark[x] is set to true, then we know that there exist p and q such that p^2+q^2 = x. In this way you can pass the test in the given time limit.

USACO - Mother's Milk

I don't know why, but I had a great misunderstanding of the problem statement from this sentence "FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty" :-) I thought by second bucket he means bucket B, and by first bucket he means bucket A. But no problem I will pay more attention from now on. So after I understood the problem statement correctly, I thought a little about the "states" in pouring buckets, I felt that I can present each state as a node, and cause each bucket has a capacity from 1 to 20, so we have at most 20*20*20 nodes, we can DFS over all of them and find what can remain at bucket C when bucket A is empty. Now that we have presented nodes, we are facing a graph, graphs do need edges don't they? (Unless we are facing a null graph). So what is an edge in our graph? By edge I mean how can we go from one node to another? Consider first sample input in the problem statement, Suppose this triple as a staring node (0,0,10), what other nodes can we visit directly from this node?

(8,0,2) & (0,9,1) am I right? what happens after that? Just like DFS (or BFS) other nodes that are not visited and can be visited, must be visited :-) (too many 'visited's) 

USACO - Packing Rectangles

After reading the problem statement I noticed the number of rectangles and their length and widths, as they are small enough to check all the combinations, 4! * 2^4, all permutations and each permutation you decide which rectangles to rotate. This would be enough, each time you check all the 6 layouts to put the rectangles, and find the minimum area.

I approached a little different, in a worse running time, I checked each possible enclosing rectangle X*Y, X=1...200, Y=1...200, so Order of this would be O(200 * 200 * 4! * 2^4) which is fast enough to pass the tests. For each Rectangle I check all the 4! * 2^4 possible ways to put the rectangles, and see whether I can put all the rectangles in that enclosing Rectangle or not, if yes, then I presume this rectangle would be an answer, then between all these rectangles I find the answer.

UVA - 10839 - The Curse of Barbosa

problem statement
This problem is just a Dynamic Programming problem. Observe the problem as a graph with 3 nodes, if self loop was allowed in this problem then it would become a matrix multiplication problem, but now we have to count special paths, dp[x][y][z][node] means how many different roads can be made which city 1 is seen x times, city 2 is seen y times, city 3 is seen z times and we are at city 'node'. How to update this?

dp[x][y][z][node] += dp[x-1][y][z][1]  if node != 1
dp[x][y][z][node] += dp[x][y-1][z][2]  if node != 2
dp[x][y][z][node] += dp[x][y][z-2][3]  if node != 3

We know the basic case dp[0][0][0][1] = 1, in this way we can update our table.
Each time we read n, output = dp[n/3][n/3][n/3][1] is the number of ways we can start from 1 and end at 1, but output counts some paths and it's reverse, some paths not all paths, palindrome paths are counted just once, their reverse is not counted, so if we add the number of palindrome paths, we can divide that number by two.
How to add palindrome paths? If n is even then there is no palindrome path, but if n is odd,  m = (n+1)/2, and we calculate dp[m/3][m/3][m/3][1] and add it to dp[n/3][n/3][n/3][1], the result would be (dp[m/3][m/3][m/3][1] + dp[n/3][n/3][n/3][1] ) / 2. (Of course we need BigInteger here.)