Monday, June 4, 2018

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.


Saturday, June 2, 2018

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.

Thursday, May 31, 2018

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.

Friday, February 9, 2018

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.


Saturday, February 3, 2018

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)

Thursday, February 1, 2018

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?

Monday, October 23, 2017

UVa - 13257 License Plates

Link to the problem on UVa Online Judge

Presumably you have read the problem. You have to count the number of unique 3-letter subsequences of input string. For example if AABCD is given then AAB, AAC, AAD, ABC, ABD, ACD and BCD are unique subsequences of it. How many 3-letter strings do we have at all? 26 choices for the first letter, 26 choices for the second letter and 26 choices for the third letter, overall we have roughly 18,000 3-letter strings. We can generate them with three nested for loops. Next we have to find out whether a generated 3-letter string is a subsequence of the input string or not?

How shall we do this? The naive solution is to use nested loops to find out whether these 3 letters are a subsequence of input or not, which is very expensive for us, so we can't use this method.

Let's say we want to check whether BHK is a subsequence of the input or not. Do you agree we have to match 'B' with the first occurrence of 'B' in the input? It is the best choice. Let's say we have matched 'B' from BHK with a 'B' at position 1500 from input. Now we have to find a 'H' which is to the right of 1500th position, what if there are several 'H's to the right of this position? Again, isn't it the best solution to match 'H' with the nearest 'H' after index 1500? It is the best choice, because if we match this 'H' with a farther 'H' we might lose the chance to match 'K' with any 'K's at all.

So it seems for each index we need the nearest index of each character that occurs after it, for example nextIndex[position][character]. nextIndex[position][character] is -1 if there are no character's in range [position...length] or index of the nearest character to position.

We calculate nextIndex like this picture. First position has no idea about the nearest character after it, so it asks position+1 about them, the only character position knows about is s[position], so it updates it to position.

And this is how we can find out whether a string of size M is a subsequence of another string of size N with O(M) for each query.

Sunday, December 1, 2013

UVa - 11748 Rigging Elections

Link to the problem on UVa Online Judge

In this problem you must think more than you have to code, you must reason.
First of all if you think of candidates as nodes of a graph, then you'll understand that we are facing a tournament graph (A directed graph in which between any two vertices there is exactly one edge in one direction).
First we have to build the graph in O(n^2 * m), how do we build the graph? For any two candidates if we know voter j prefers which one in O(1) then we can build the graph in the desired order. After we read a voter's preference list we must save candidate i is the k-th person in this voter's list. Then for any two candidates and a voter we will understand the one who he prefers.
After building the graph we must think of different situations, situations that a candidate is winner. The simplest situation that may come to mind is a cycle. In a cycle every node can be a winner. If you look closer each node of a Strongly Connected Component can be a winner. What's the relation between two SCC's? If edges are from SCC A to SCC B, then each node of SCC A can be a winner if no other SCC has edges to SCC A. So we must put these SCC's in topological order and anyone in the first SCC can be a winner.
So the desired candidate can be the winner if he is in the first SCC in the topological order.

Another solution to this problem comes from a similar reasoning and that is : if you have a path to any other node then you can be the winner. Think of this situation and try to understand that if you have a path to a node then you can win any person on this node, especially the last node on this path.
How do you know if you have a path to all the other nodes? You simply use DFS(desiredCandidate), and if all the other nodes are marked as seen, then you have a path to all the other nodes.

Wednesday, November 20, 2013

TIMUS - 1120 Sum of sequential numbers

Link to the problem on Timus Online Judge

The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know that you know problem statement is straight forward :), so let's talk about solution.
What do I do in a problem like this? I pay attention to range of input. Let's rewrite what problem wants for output :
  • N = A + (A + 1) + … + (A + P − 1) 
  • N = P*A + 0 + 1 + 2 + ... + (P-1)
  • N = P*A + (P-1)*P/2
What does a good teacher do when you are solving a problem? He asks you meaningful questions to lead you to the solution. When a good teacher is not available (most of the times) try to do this favor for yourself, ask yourself meaningful questions about input, so you can understand new aspects of the problem you are solving.

Can we iterate over all possible values for P? or What could be maximum value for P according to range of input? Yes, what is the maximum value of P if N=10^9. If you look at the equations, P would be less than square root of 10^9, about 33,000, that's good, cause if you can iterate over all possible values for P, then A would be known in the equation.
What is value of A if we know N and P? A = ( 2*N - (P-1)*P ) / (2*P) such that : numerator must be positive and numerator must be divisible by denominator, then you can pick maximum value over 33,000 possible values for P.