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.)

UVA - 12516 - Cinema-cola

problem statement 
After reading the problem statement, I just figured out a greedy solution. After reading the queries I sort them from top to bottom and from left to right, then I iterate over queries and try to assign supports to the current person, if his left support is free then I give him his left support otherwise if his right support is free I give him his right support, if both of them are not free then it is impossible to assign supports to them so that every person has a support.
This problem has another special solution, Maximum Bipartite Matching, We can build a bipartite graph, one part places to seat, another part supports, the edge are obvious, then we run MBM, if we can match all of the seats so that each seat has a support then the answer is YES otherwise the answer is NO.
Time complexity of the second solution is not good enough to pass the time limit I think so.

USACO - The Clocks

Let's think about the problem statement more, what do we have?

We have a set of 9 clocks that we want them all to show 12 o'clock and we have a set of 9 different keys that we can push to change the time of a subset of clocks. For example key #1 can change the time of clocks ABDE, so if you press key #1 then clocks labeled A, B, D and E will show a new time which is 3 hours plus their previous time.

If you don't observe any facts in the problem statement, This problem can be modeled as a graph which you want to go from a 'start' node to a 'destination' node, and can be solved using BFS. How many nodes do we have? By 'node' I mean a set of 9 clocks each of which shows a specific time (12-3-6-9), so each clock has 4 situations and the number of nodes is equal to 4*4*...*4 = 4^9 = 262144 that's not too many for a graph to run BFS on it. So you run BFS from the start node and try to reach node(12,12,12 --- 12,12,12 --- 12,12,12) How many neighbors does a node have? Each node has 9 other neighbors through 9 different keys.

But as I told if you observe a simple fact you can see that each key has 4 different situations, so instead of running BFS to find the solution you can use recursion to decide how many times you want to push key #i, and check if you can change all the clocks to show 12 o'clock. I myself think the second solution is more cute than the first solution, there is also another solution which takes O(1) and needs much more insight about the problem.