136 - Ugly Numbers - UVA

Ad Hoc OR Dynamic Programming

You can pre-calculate calculate the answer by checking all the numbers till you find the 1500'th ugly number by checking each number prim factors to see whether they are just 2, 3 and 5.

OR

You can build a list of ugly numbers in a bottom-up dynamic programming approach. How?

I use a set and a vector of integers for simplicity. Both the set and the vector have the same numbers, I can use just a set too without no vectors.

I must build the list of ugly numbers, since my first ugly number in the list is 1, so the next one must be retrieved by multiplying 2, 3 and 5 by 1 ( the first number in the list ). I pick 2*1 ( the minimum ), then 2 must be multiplied by the next number in the list( 2 ). At next step I choose 3 out of ( 2*2, 3*1, 5*1 ), and 3 must be multiplied by 2( the next number in the list for factor 3 ), then I pick 4 out of ( 2*2, 3*2, 5*1 ) and so on.

2*1     3*1     5*1

2*2    3*2    5*2

2*3    3*3    5*3

2*4    3*4 

2*5

2*6

My function min3 is invoked in this order:

2*1,   3*1,   5*1

2*2,   3*1,   5*1

2*2,   3*2,   5*1

2*3,   3*2,   5*1

2*3,   3*2,   5*2

2*4,   3*2,   5*2

2*4,   3*3,   5*2

2*5,   3*3,   5*2

2*5,   3*4,   5*2

2*6,   3*4,   5*2

2*6,   3*4,   5*3

2*8,   3*4,   5*3

2*8,   3*5,   5*3

........

........

497 - Strategic Defense Initiative - UVA

dynamic programming - Longest Increasing Subsequence ( LIS ) - O( n^2 )...O( nLOG(n) )

This problem is a classic dynamic programming problem that if you are familiar with the type of the problem, you will solve it in less than 10 minutes.

I use O( nLOG(n) ) implementation of LIS, you can find an implementation of it at

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

762 - We Ship Cheap - UVA

graph search algorithm - single source shortest path - BFS

The problem takes as input the description of a city (graph) and prints the shortest path from source city to destination city.

The challenging part of this problem is that how you want to represent the graph?

Since there are just 26*26 distinct city names you can use adjacency matrix too, but I use adjacency list by using a map of "string" to "vector". I also use a map of "string" to "string" to save the precedence (father) node of another node, so I can print the path easily, and I use a set of "string" to mark nodes that I have visited recently.

And the rest and main part of the problem is to find the shortest path from source city to destination city that I do it using a queue of "string".

10102 - The path in the colored field - UVA

graph search algorithm - BFS OR Ad Hoc

At first I was confused by the problem description, and I thought that the sample output doesn't match the sample input. The problem wants to know that if you are standing in a cell occupied with digit '1', at most how many steps does it take to get to a cell (just one) occupied with digit 3.
So first I find the minimum distance from each '1' to each '3' and take the minimum of these values, then I just iterate through the minimum values I took for each '1' and print the maximum one.
To find the minimum distance from each '1' to each '3' you can run a BFS from that '1' and then pick the minimum of the distances from the '1', but I don't suggest to do that, because in grids BFS is used when you have some special adjacency for cells or you have some obstacles in the path between two cells, but here you can easily calculate the minimum distance between two cells.
the Distance from cell A to cell B = abs( A.x-B.x ) + abs( A.y-B.y )
This is true if you are allowed to move one cell up, down, left or right, but not diagonally.

11448 - Who said crisis? - UVA

big integer - subtraction

The problem wants you just to subtract two positive integers that can be up to 10000 ( I think ) digits.
If you have a big integer library, that's a simple work, otherwise you have to implement subtraction yourself, as I did.

11474 - Dying Tree - UVA

graph search algorithm - DFS( Depth-First Search )

The problem wants to know whether there is a tree to call a doctor to save the sick tree or not?
This tree can also be the sick tree.
I first construct an adjacency matrix from the trees,( excluding doctors ), HOW? Two trees can talk to each other if the minimum distance between them is less than or equal to k. Then I run DFS from node 1, in the DFS function I check whether there is a doctor to whom the current tree in the DFS function can communicate? HOW? An ordinary tree can communicate to a doctor if the minimum distance between them is less than or equal to d. I have a global boolean variable for checking the answer. If in DFS function I find a connection between a tree and a doctor I set it to true and return, otherwise I continue searching from the adjacent trees to the current tree( adjacency matrix ).

10793 - The Orc Attack - UVA

graph algorithms - all pairs shortest paths - floyd warshall

Another shortest path problem. As you can see in the problem description you have to find the minimum distance from locations 1-5 to all other locations other than 1-5. Then you have to pick the candidates, which are equidistant from these 5 locations. That location must be reachable from all the locations in the graph. If such a location exist, then pick the one which has the minimum farthest distance, that means this location( rally point ) is reachable from all other locations and has a minimum distance to all of them, there is a location that has the maximum minimum ( :-D ) distance from rally point, you have to pick a rally point that this value for that is minimum( distance to the farthest location ).
I simply construct the graph from input, run floyd-warshall on it, and the rest of the problem that has described and I just simulate it.

291 - The House Of Santa Claus - UVA

backtracking

Another backtracking problem. As you can see in the problem description you are not allowed to pass each edge twice. ( Euler tour in lexicographical order )
I make an adjacency matrix, and a boolean matrix for marking the edges I have visited till now.
int mat[6][6];
bool mark[6][6];

Then I start backtracking from node 1 and each time checking whether to continue from current node or not I check ( mark[cur][i] == false && mat[cur][i] == 1 ) and then mark this edge to true and keep on backtracking. I have a variable d which denotes the depth of the backtracking whenever it reaches 9 I completely print the tour I have saved.

10171 - Meeting Prof. Miguel - UVA

graph algorithms - all pairs shortest path - floyd warshall

This is a double all pairs shortest path problem. As you see in the problem description you are facing two distinct graphs which at most each one has 26 nodes( upper case letters ), one of them is for Manzoor and the other is for Prof. Miguel.
I first construct two graphs and initialize the adjacency matrices to 100000, then read input and finally run floyd warshall one both of them, and find the minimum cost, how? The places which both of them can go, I add the cost for both of them and find the minimum of these.
Don't forget if there are several places with minimum cost, print them in lexicographical order like this.
10 A G N
Be careful about zero costs, the problem has pointed that the costs are non-negative integers, so it can be zero.
My program first got WA because of this test case.

input :
2
Y U B D 0
M U B D 0
B B

output :
0 B D

because first I checked if they are in the same place and separated this test case from the others.
0 B

10637 - Coprimes - UVA

backtracking

As the problem says, you should print all possible partitions of S into t co-prime numbers.
The order doesn't matter, so If you have to choose 1 & 2 & 5, you just need to print 1 2 5 not 5 2 1 or 2 5 1. This fact prunes backtracking and helped me pass time limit.
I implemented a function called solve( start, m, d ). In this function I start checking from start, and each time I find a number that is coprime to the selected items, I put it in the list and keep on backtracking with ( number, m-number, d+1 ), when the function reaches at ( d == numberOfPartitions ) and m is equal to zero( that means there are no values to choose and the partitioning is complete ), I completely print the selected list.

10422 - Knights in FEN - UVA

backtracking

This problem gives you a 5x5 chess board with 24 knights ( 12 of them are white and the other 12 are black ) and wants you to turn the board to the initial board that is described in the problem with minimum moves.
I think there are better approaches, because in the rank list the first 20 have solved this problem with time 0.000, but if you implement a careful backtracking you will pass time limit.
Since the depth is just 10, backtracking is sufficient.
I just replaced the empty cell with every possible replacement, except the cell that in previous move was empty.

for(int p = 0; p < 8; p ++) // 8 directions to move from space { // x & y are the previous cell that was empty i = x+dir[p][0]; j = y+dir[p][1]; if( i >= 0 && j >= 0 && i < 5 && j < 5 && ( i != a || j != b ) )
{
swap( input[i][j], input[x][y] );
solve( d+1, x, y );
swap( input[i][j], input[x][y] );
}
}

If the problem is solvable in less than 11 moves, maybe it's possible to solve it in several paths, so each time the puzzle was solved, I saved the length of the shortest path.

11569 - Lovely Hint - UVA

backtracking

The problem wants you to count all the strings that you can construct under the restriction in the problem and print the length of the longest and the ways you can achieve that length.

Simply I start backtracking from all the characters and in the function you just backtrack with the characters that can be placed next to the current character under the restriction.
Each time I invoke the function for a character, I mark it, then I just pick it once.
Be careful! Don't invoke the function for 'L' in "HELLO" twice.

if( line[i] != line[i-1] && !mark[i] && 5 * (line[cur]-'A'+1) <= 4 * (line[i]-'A'+1) )
{
mark[i] = true;
solve( i, d+1 );
mark[i] = false;
}

I sort the input string, something like this is the main condition in the function.
'i' is the current character I'm checking, 'd' is the length of the string I've made till now.

length[d ++]
This array tracks how many strings up to 'd' characters I can construct.
At last I find the maximum length and print length[maximum_length].

775 - Hamiltonian Cycle - UVA

backtracking - graph representation - finding the hamiltonian path

The problem gives you the adjacency matrix and wants you to find the hamiltonian path.
First, since the graph is dense the hamiltonian path exists( I think so ), so for all test cases you have an answer to this problem, and since the order is not important your path can start from node 1 and end at node 1.
What you have to do is to construct just a path from node 1 that ends up in a node which is adjacent to node 1, so you can print the path at that time.
I use a 2-dimensional array for adjacency matrix, a boolean array for marking nodes, because each node can be traversed once except node 1 which is the start and the end of the path, and an array of integers for saving the order of the nodes I'm visiting.
I start backtracking from node 1 and each time in the function I check whether there exist another node which is not visited and continue backtracking with this node.
As backtracking goes on, sometime I find out that I have visited all nodes once and that's the time I print the path and that's it.

423 - MPI Maelstram - UVA

graph algorithms - all pairs shortest path - floyd warshall O( n^3)

In a system they want to send a message from a source called station 1 to all other n-1 stations.
What question want is the minimum time to do that, so we have to find the minimum time from station 1 to all other stations and then find the maximum between these minimum times and that's the longest time in which all the other stations have gotten the message.
We don't have to send a message directly because of the expensive costs and so we can use intermediate stations to convey the message from station 1 to station k for example.
'n' is not so large so I used floyd-warshall to do this.