POJ - Drainage Ditches

Link to the problem on Peking Online Judge

This is a primitive and classic Maximum Flow Problem.
We have a weighted directed graph in this problem, and we need to find maximum flow from node 1 to node M.

POJ - Optimal Milking

Link to the Problem on Peking Online Judge

If you look closer to the problem statement and model it on a piece of paper, we have C cows each of which must be assigned to one of the K milking machines, so that the maximum distance walked by one of the cows is minimum. The bold phrase is one of the most important keys to problems which are solved using binary search + some other algorithm. Minimizing Maximum Distance.

In this problem we need to do a Binary Search over the maximum Distance and then check according to our limitation (at most M cows for each milking machine) whether we can find an assignment which obeys Maximum Distance which for now is fixed with Binary Search.

After these steps we know each cow can go to which machines. Here we have to find a good assignment of cows to milking machines if exists. We decide CowX goes to MilkingMachineY, but we are not sure that this decision is a good decision, so we make a plan to change our mind in the future if needed and send CowA to another milking machine (back edge in Max Flow). This behavior in the problem remembers us of Maximum Flow, which by each decision we are not completely sure of it's correctness and we make a plan to change it in the future if needed.
Edges of our graph :

• from source to each milking machine an edge with capacity M
• from each cow to sink and edge with capacity 1
• from each cow to each milking machine which mat[cowX][MMY] <= DIS an edge with capacity 1

Where does mat[i][j] come from? It is calculated using a floyd-warshall algorithm after reading input, mat[i][j] means the shortest path from entity i to entity j.

DIS comes from our Binary Search. After making the graph we run Max Flow on it, if the flow is equal to C DIS is good and we may find another DIS1 which is less than DIS, otherwise we need to find another DIS2 which is greater than DIS (What we do in Binary Search depending on the flow - if...else)

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.

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.

USACO - Calf Flac

Calf Flac
It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties.
Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z' and `a-z'.
Find the largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.

PROGRAM NAME: calfflac

INPUT FORMAT

A file with no more than 20,000 characters. The file has one or more lines. No line is longer than 80 characters (not counting the newline at the end).

SAMPLE INPUT (file calfflac.in)

Confucius say: Madam, I'm Adam.

OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.

SAMPLE OUTPUT (file calfflac.out)

11
Madam, I'm Adam

Greedy - longest palindrome with size less than 2000 - brute force

In this problem you have a string with size 20,000 and want to find the longest palindrome with size less than 2000, but there are non-alphabetical characters in the input file. So I first read input, I have two arrays for input, one is the input and the other is the transformed input and indexing of the alphabets that I have saved in lower case.
Then I iterate from 0 to size of input and each time I check two things: First : if current character is the middle character, how much can we extend the palindrome from left and right, So I iterate 1000 to left and 1000 to right and wherever it's not yet a palindrome I stop continuing to expand the palindrome,this is when the size of the palindrome is odd, when the size of the palindrome is even I set the current and next character as the core of my palindrome with size even, and again expand the current palindrome. In this approach time complexity is O(20,000 * 2000).