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?