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.

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