UVa - 10625 - GNU = GNU’sNotUnix

Link to pdf version on UVa OJ

As you see in the problem description we have up to 10 rules, and at each step a character is replaced with the corresponding word. For example N->Not means at each step we look at the current word and we replace all 'N's with "Not".

What happened on my mind : First I was trying to find some kind of solution like finding n-th sentence of Fibonacci, like the matrix multiplication or something. Then I drew the underlying graph of the first test case.

After that the solution started to show itself to me. Let's say we are at G and we want to count the number of 's' after 5 step. All of a sudden I defined this function and tried to explore whether it makes sense or not.

Let's say target is fixed (per query), then:
f(c, step) : counts the number of occurrences of target after step steps, starting from c.

f(c, step) = f(c1, step-1) + f(c2, step-1) + ... + f(ck, step-1) + count( target, rule[c] )

So I could define f(c, step) based on smaller subproblems. By now I was sure I need to solve this using Dynamic Programming. I was just defining different things needed for a DP solution. After finding the recursion formula (which is the harder part in a DP solution) I checked for base case, when step = 0, it means this is what we have, we only have c and we cannot recurse any more. So if c equals target we return 1 otherwise we return zero.



And this is the top-down solution with memoization. Since dp is unsigned long long, I couldn't fill it with -1 (when a state is -1 it shows that this subproblem has not been solved yet), so I used a parallel boolean 2d array to know whether a subproblem has been solved or not. For more details look at the code on github.

Link to my own code on github

UVa - 11491 - Erasing and Winning

Link to the pdf version on UVa OJ

We are given an integer with N digits, we are asked to remove d digits from it so that the remaining number is maximum. For example given 123123, if we have to remove 3 digits, the maximum number we can get is 323 (we erase 1,2,1).

Look at the problem as keeping r = n - d digits, so we know the length of the final number. In a decimal system (or any other system) if we want to have the maximum number with r digits, which digit should we maximize first? Yes, the leftmost digit, so we do the same here. We keep r - 1 digits at the right end of input number, then from index 0 to index r - 1 we look for the biggest digit and we take that, now we have a new problem of the same form.

For example: number = 123123 and we want to keep r = 3 digits.
We put the 123123, we put 23 apart and try to find the maximum digit in the first 4 digits, we take the first 3.
number = 123, result = 3, r = 2 ===>>> number = 123, result = 32, 
number = 3, result = 32, r = 1 ===>>> number = 3, result = 323

Work on this example yourself, number = 1059005838, r = 4, result would be 9838.
How do we find the maximum digit in range [i, j]? We precalculate a frequency array : frequency[idx][digit] means how many of digits we have from index 0 to index idx.
frequency[idx][digit] = frequency[idx-1][digit] + (value[idx] == digit). We just calculate frequency from left to right, each idx depends on idx-1. (Some people call this dynamic programming? :D)

Link to my own code for this problem

UVa - 10484 - Divisibility of Factors

Link to the pdf version on UVa OJ

Given two integers N and D, you will have to find how many of the factors of N! are divisible by D.

The above sentence is the description of the problem. Let's start with an example. Let N be 5 and D be 10.
If any factors of N! must be divisible by D, first N! must be divisible by D itself. Let's factorize N! and D.
5! = 2^3 * 3^1 * 5^1
10 = 2^1 * 5^1
so 5! / 10 would be 2^2 * 3^1. This means we took a "10" out of 5! and 2^2 * 3^1 remains. Now we have options to take zero, one or two 2's and zero or one 3's. So there are 3 options for 2 and 2 options for 3. The answer would be 6. There are 6 different factors of 5! that are divisible by 10.

N=5, D=10

If you code in C++ or Java, be careful, the result could get large, you should use long long in C++, and long in Java.

Implementation:
It's not hard to factorize N!, because N is <= 100. After factorizing N! iterate over factors and for each pair (prime, power) in the factors try to divide D by prime as many times as possible, and by each division decrease power by one. After the iteration ends D must be 1 or -1, otherwise N! is not divisible by D in the first place.

If D is 1 or -1, then you should iterate once more over the factors of N! that you just modified (decreased powers as many time as possible) and calculate the result using the multiplication principle.

If D is -1 you should multiply the result by 2 in the end. why?

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.