UVa - 196 - Spreadsheet

Link to the problem on UVa Online Judge
Link to the pdf version

In my opinion this is a classic Dynamic Programming problem which can be solved with a top-down approach. The most important part of this problem is that it explicitly states that there are no cyclic dependencies between cells, a key part in a dynamic programming solution.
The fact that we can solve a problem with a top-down approach shows that there are no cyclic dependencies between subproblems. Actually it's a DAG, Directed Acyclic Graph, in which larger subproblems are dependent on smaller subproblems.
The tricky part which requires more attention is parsing input and calculating row number and column number correctly.

This is my code for converting a string like A, AAB, AZ ... to column number.
The rest is a simple function which memoizes the answer to each cell, if it has been calculated before, it doesn't calculate it again and only returns the result.

UVa - 10688 - The Poor Giant

Link to the problem on UVa Online Judge
Link to the pdf version

In this problem we want to create a binary decision tree which sum of all of the searches is minimum.
Let's understand the problem with an example:

Let's think we have an array like shown in the picture : [1, 2, 3, 7, 8, 9, 10, 20, 21]
For the first apple to eat we have several options, let's assume we choose 7 to eat first, no matter which apple is sweet at the end, how many times 7 must be eaten? 9 times, because if 1, 2 or 3 is sweet first we have chosen to eat 7, then we know the sweet is on the left side of 7 and we go to the left subtree, if 7 is sweet we have already eaten it, if 8, 9, 10, 20 or 21 is sweet, first we eat 7 and then we move to the right subtree.

So if we choose 7 to be eaten at first, the total cost would be something like this : 7*9 + cost(left_subtree) + cost(right_subtree)
If we use indexes for the cost function it would be something like this: 7*9 + cost(0, 2) + cost(4, 8)

What if we choose to eat 8 at first? Then the cost would be 8*9 + cost(0, 3) + cost(5, 8), because still 8 must be eaten 9 times no matter which apple is sweet and then recursively solve (0, 3) and (5, 8).

int cost(int i, int j) must calculate the cost of the best decision tree for the numbers in [i...j]

So in order to calculate cost(i, j) we iterate over all possible options for the first apple to be eaten and take the minimum of them as the answer.

What are the basic steps? What if only one apple is remained? We must have already figured it out if only one apple is remained, then cost would be zero.
Formally if i == j then cost is equal to zero.
What if only two numbers are remained? We can eat the lighter apple and figure out if the lighter is sweet or the heavier, then must return weight[i] * 2.

Since there are a lot of overlapping subproblems we memoize answer to each cost(i, j) and use a top-down dynamic programming approach.

UVa - 10980 - Lowest Price in Town

Link to the problem on UVa Online Judge

For this problem we have to calculate the minimum price of buying at least K cooking oils. Whenever a problem asks you to calculate minimum or maximum of something, one possible approach is to think about optimizations and dynamic programming.

If you have solved some coin change challenges before, understanding the main approach to this problem won't be that hard for you.

I define the state of dynamic programming to be
    f(n) : the minimum price we have to pay to buy exactly n cooking oils.

The recurrent formula would be something like this:
    f(n) = min( pack_price[h] + f(n - pack_count[k]) : for all possible packs

What are the basic steps?
f(0) = zero, because buying no cooking oils needs zero dollars.
f(m) = INFINITY for m < 0, because negative m is invalid we return INFINITY to prevent using  an invalid subproblem answer.

After calculating f(n) for each n, the answer of the problem is not f(n), actually you have to iterate starting at n and find some n greater than or equal to n which f(n) is minimum. For more detail look at the third sample case where you can buy 3 cooking oils for $40.00.

I had some problem reading input data, at first I read half of input using scanf and last line of each test with getline, then I changed it and read all input using getline and parse input myself.

UVa - 1714 - Keyboarding

Link to the problem on UVa Online Judge

For this problem imagine of an imaginary person that is walking on the grid and always is searching for the next character of the text message and when he is standing on the character that he seeks for he presses "select" button. Can you define the state of this person? What are the characteristics of this persons situation? Of course the row and the column he is standing on and the character of the text message he is trying to match next. What can he do when he is in state (row, column, index)? If the character at mat[row][col] is equal to the character at textMessage[row][column] then he can go to the state (row, column, index+1) with cost of cost(row, column, index) + 1, which means an stroke that helps him to go from state (row, column, index) to state (row, column, index+1).
What other options he has when he is in state (row, column, index), he can move left, right, up or down which yields to a new state (newRow, newColumn, index) which means still searching for the index character of text message but in a new position on the grid.
This is actually the definition of Breadth First Search algorithm which is one of the most popular algorithms of Graph Theory.
The hidden part of the solution is (newRow, newColumn) when the person chooses to go left, right, up or down. If the person chooses to move in one direction when would he end up? This can also be precalculated (like the following image) and be used in BFS.

TopCoder - SRM 178 DIV 1 - MiniPaint - leastBad

Link to the problem statement

First of all it must be clear that having a fixed number of strokes for each row, the problem can be solved independently for each row, so on a top level we have to decide how many strokes to assign to each row and tell them to solve themselves (paint themselves) and then we choose the best combination. So in order to solve the assignment problem we use dynamic programming.
 
    int g(int row, int strokes)

This is the state of our outer DP, which tells if we have to solve rows in range [0...row] and only have strokes number of strokes left, what would be the minimum number of mispainted cells? So we can assign 0, 1, 2, ..., width assigns to the current row and solve g(row-1, strokes-k) which k is the number of strokes that we have assigned to the current row, in this case what would be the number of mispainted cells for this row? f(row, length-1, k) but what this means?

     int f(int row, int idx, int strokes)

This is the state of our inner DP, which means we want to paint row of the picture in range [0...idx] and only have strokes number of strokes left. There are two options for us, first not paint cell at (row, idx), which means cost off(row, idx-1, strokes-1) + 1, or paint cells in range [k...idx] with cost of f(row, k-1, strokes-1) + numberOfCellsDifferent to cell at (row, idx).

Think about base cases yourself. (e.g. where row is -1 or strokes is equal to zero)

USACO - Combination Lock

After you read the problem statement you must have some insights about the solution (brute force over all possible settings, mark them and finally count them to print the answer).

We have to brute force over all possible settings that open the combination, the tricky case is where one setting opens both combinations, you must not count this twice, I used a set data structure to mark good settings (a setting that opens at least one of the combinations).

Now you have to decide how you want to do the brute force? Since I like recursions I did it using a simple recursive function.

A recursive functions consists of repetitive work on some state :

In my recursive function "markThem", I work on x[ idx ] and call the same method to work on x[idx + 1]. What must happen to x[ idx ]? It can have any value in range [x[idx]-2, x[idx]+2], so there are 5 possible values for x[idx], at each step (in for loop) I assign a value from that range to x[idx] and call markThem with argument idx+1.
What is the stop condition? When idx equals 3, then we have changed values of x[0], x[1] and x[2] and we have a possible settings and we must mark that.

Finally in main function I print size of the set data structure as the answer.

UVa - 13249 - A Contest to Meet

Link to the problem on UVa Online Judge

There are a few key points in the problem statement that can guide you to the solution. We want to calculate the worst case scenario of putting three people in random intersections and calculate the time they arrive at a common intersection. So no matter where they are located initially they will find an intersection and meet each other there. It's not the best choice, and that's the point, we have to calculate how long a live TV broadcast must last to cover their journey.
First question : From the three persons who is the worst walker and will take longer to get to the destination? The person with the slowest speed.
Next question : Which path is the worst for the slowest person to traverse? Actually which two intersections as start and end is the worst for the slowest person of the group? The two intersections that are farthest from each other.
So we have to calculate shortest path between each two pairs of intersections. Which algorithm you know that is asymptotically optimal for this job? The answer is Floyd-Warshall algorithm. After calculating all pairs shortest path using this algorithm, find the two farthest intersections and calculate how long does it take for the slowest person to get from one of them to the other.

As you know X = V.T so T = X / T. If we want to round up a division operation instead of X / T we can use (X + T - 1) / T, think about this, why this rounds up the division?