11388 - GCD LCM - UVA

Mathematics

As you can see in the problem description, you have to find numbers a & b such that (a, b) = G and [a, b] = L and also it has mentioned that if there is more than one pair satisfying the condition, output the pair for which number a is minimized. It's a very easy problem, you have to figure out whether the remainder of L / G is equal to zero or not, if so, your answer is G & L otherwise you have to output -1. Note that in the worst case (a, b) = a and these inequalities always satisfy.
(a, b) --->>> GCD of a & b
[a, b] --->>> LCM of a & b
(a, b) <= a (a, b) <= b [a, b] >= a
[a, b] >= b

UserName - SRM 203 Div 2 - TopCoder

string

Given a list of existing usernames, we are to determine whether a newly requested username already figures among them. If so, we must append to it the lowest possible number to make a new username.

I first checked whether the requested username exists among them, if not I return it, otherwise I iterate starting at 1 and at each step I convert the number to string and add it to the requested username, then check if it doesn't exist I return it.

In this approach I have to added two functions, 1 - search the vector for a string 2 - convert integer to string.

But another solutions exists, at first I implement a set of string and insert all the vector elements to it, I have a char candidate[1024] too.

I use sprintf( candidate, "%s%d", userName.c_str(), number ), then I don't have to implement two extra functions.

423 - MPI Maelstrom - UVA

graph algorithms - single source shortest path Dijkstra

In this problem you face a communication system, that in this system messages are sent from station 1 to all other n-1 stations, there are costs to send messages from station 'a' to station 'b' if it's possible to send directly otherwise you have to find a route from station 1 to that station.

Since there are communication costs, sometimes it's better to send a message from station 1 to station 'b' not directly to minimize the cost to send message from station 1 to station 'b'.

In this manner each station will have a minimum time required to receive the message from station 1. This problem wants the maximum of these minimum times.

I use dijkstra to solve this problem. Let me explain what I do in my solution.

I have an adjacency matrix[101][101] and an array MIN[101] and a boolean array mark[101]

I construct adjacency matrix from input.

I initialize MIN[i] = infinity for i = 1 to n and MIN[1] = 0

and initialize mark[i] = false for i = 1 to n

I am going to construct a shortest path tree starting at node 1 using dijkstra. I have a node "current". Initially I set it to 1.

Then I check the adjacency matrix for node current and set 

MIN[ neighbor[cur] ] = minimum( MIN[neighbor[cur]], MIN[cur] + adjMAT[cur][i] )

after checking all of the current neighbors I set mark[cur] = true and find a new current. how?

I check all of the nodes and from them that haven't been marked yet and has the minimum distance to node start I pick my next "current" node.

Since the graph is connected and has just one component I iterate through MIN[i] and pick the maximum.

10301 - Rings and Glue - UVA

graph search algorithm, Depth First Search ( DFS ) or BFS  +  GEOMETRY

I first construct adjacency matrix then use DFS to split each component and find the maximum.

d = distance between two centers of the rings

rPlusR = radius of ring 'a' + radius of ring 'b'

if( d <> max(R[a], R[b]) 

    then adjMat[a][b] = adjMat[b][a] = true

After constructing the adjacency matrix I easily run DFS on the constructed graph, each time DFS is invoked we have a new component so I count the vertices that are being marked during this DFS call and compare to the maximum.

for(int i = 0; i <>

if( mark[i] == false )

{

vertices = 0;

DFS( i );

if( vertices <>

mx = vertices;

}

I made a mistake in the output.

Note that if maximum is equal to 1  you don't have to print 's' at the end of output.

( thanks Pouria for his hint )

LetterStrings - SRM 202 DIV 2 - TopCoder

Simulation - string

Just iterate through all the strings in 's' and count the letters.

I used function isalpha( s[i][j] ). Since there are just letters and dashes in the input strings you can use this condition too if( s[i][j] != '-' ) sum ++;

ChessMetric - 2003 TCCC Round 4 - TopCoder

Dynamic Programming

I solved it in O( size*size*numMoves ). I implement an array DP[101][101][51] and what's the state of this DP problem? DP[i][j][m] means number of ways you can reach cell[i][j] in 'm' moves.

Each cell is reachable ( at most ) from 16 other cells, that means if you want to come to cell[i][j] you can reach it from other 16 cells and you are going to add the number of ways you can reach each of them and the result is number of ways you can reach cell[i][j].

At first I set DP[start[0]][start[1]][0] = 1,     that means I can reach cell[start[0]][start[1]] in zero moves in one way. So from m=0 to numMoves if DP[i][j][m] != 0 that means I can reach it from start in m moves, I choose it and update it's neighbors DP[a][b][m+1] += DP[i][j][m]

That means I can go to cell[a][b] from cell[i][j] plus one move m --->>> m+1

DP[i][j][m] = DP[i-1][j-1][m-1] + DP[i-1][j][m-1] + ..... + DP[i+2][j+1][m-1]

Multiples - SRM 201 DIV 2 - TopCoder

Ad Hoc - math

The simplest solution, which works because the constraints are so low, is best here: loop from min to max and check each number to see if it is devisable by factor.

If you want to get more efficient, you can increment min until you hit a number divisible by factor, decrement max until you hit a number divisible by factor, then subtract min from max, divide factor and add 1. that's it.

AvoidRoads - 2003 TCO Semifinals 4 - TopCoder

Dynamic Programming

The problem wants to know in how many ways one can reach destination ( cell[width][height] )

If there were no obstacles, then it was a discrete mathematics problem, but now that we have obstacles in the path we have to calculate it in a dynamic programming approach.

What's the 'state' in this problem? ( 'state' a way to describe a situation, a sub-solution for the problem )

dp[i][j] = ( i > 0 ? dp[i-1][j] : 0, j > 0 ? dp[i][j-1] : 0 )

This recurrent relation is true if there are no obstacles in the path, but now what? Since we can come from two cells to the current cell, we have to check whether it is possible to come from cell[i-1][j] to cell[i][j] or from cell[i][j-1] to cell[i][j], each of which is not possible we assume it zero, OK but how do we determine whether it is possible or not? I build a set of pair

and that tells me that you cannot go from pairONE to pairTWO.

No Order Of Operations - SRM 200 DIV 2 - TopCoder

Ad Hoc - String

Just simulate what problem wants, iterate from left to right and evaluate the expression.

Note that the numbers are just one digit from 0 to 9.

FlowerGarden - 2004 TCCC Round 1 - TopCoder

Dynamic Programming

I first figure out for each flower how many flowers and which flowers have to go first.

It's not difficult to do that. I implemented arr[50][50] if arr[i][j] is true then flower j must go first before flower i. When arr[i][j] is true??? If height[i] > height[j] && inter( bloom[i], wilt[i], bloom[j], wilt[j] ) then arr[i][j] = true

The function "inter" determines whether the time of bloom and wilt for flower i and j have conflict.

After calculating "arr" I start finding the highest flower that doesn't conflict with others and push it back to the output vector and manipulate "arr" after choosing a flower, I mean if arr[i][chosen] == 1 then arr[i][chosen] = 0 and repeat this procedure n times to choose n flowers.

Hawaiian - 2004 TCCC Round 4 - TopCoder

Ad Hoc + string

I just implemented what problems described. If you know the function isalpha( ch ), 

you know what you have to do, you just need to implement function isHawaiian( ch ) which checks whether a given character is in the Hawaiian alphabet or not. Of course you have to split the words in the input string, you have two ways to do it, do it manually or use stringstream which do it for you.

stringstream ssin;

ssin.str( input );

while( ssin >> word )

check( word ) and push back to the output vector if it's ok

BadNeighbors - 2004 TCCC Round 4 - TopCoder

Dynamic Programming

For simplicity you can calculate two different sets, one with all elements except the first and the other with all elements except the last one, cause the first and the last element can't be in the desired sequence. So now we have a linear sequence which we want to maximize the sum.

Suppose dp[i] is the maximum sum after checking the elements to position i.

dp[i] = max( element[i]+dp[i-2], element[i-1]+dp[i-3] )

What does it mean? The first (element[i]+dp[i-2]) means it's better to include element 'i' in the set and the second means it's better to include element 'i-1' in the set.

ZigZag - 2003 TCCC Semifinals 3 - TopCoder

Dynamic Programming - Longest Increasing Subsequence( LIS )

It's something like LIS. You have to manipulate the original algorithm to obtain the answer.

I used a two dimensional array ZIGZAG[60][2] such that ZIGZAG[i][0] is the length of the longest ZigZag sequence ending at sequence[i] and ZIGZAG[i][1] is the sign of the last difference ending at sequence[i].

Suppose we have a sequence like this:

1, 8, 7, 6, 9, 10

ZIGZAG[1][0] = 1,          ZIGZAG[1][1] = 0

ZIGZAG[2][0] = 2,         ZIGZAG[2][1] = +1

ZIGZAG[3][0] = 3,         ZIGZAG[3][1] = -1

ZIGZAG[4][0] = 3,         ZIGZAG[4][1] = -1

ZIGZAG[5][0] = 4,         ZIGZAG[5][1] = +1

ZIGZAG[6][0] = 4,         ZIGZAG[6][1] = +1

I implemented the solution in O( n^2 ), since I have to check n items and for each item I will check n items to choose the appropriate subsequence.

116 - Unidirectional TSP - UVA

dynamic programming

All you have to do is to find a path that have the minimal weight path.

I first started to construct my table from the first column and in each step I picked the minimum weight till that step that had the minimum row, but that was wrong because if there are several paths, my program might pick the wrong path.

for example ( nimA, one of my friends pointed this test case out )

4 3

2 1 1

2 1 2

1 2 2

1 2 2

my program produced

4 1 1

3

but the correct answer is

3 2 1

3

that is lexicographically smaller.

I first construct the last column of my table

dp[i][n] = a[i][n] for all i

then I want to construct the rest of my table, in each cell [i][j] I can go to next column one row upper, same row, or one row lower, I pick the minimum value of them and when I have several minimum I pick the one with minimum row.

for( int j = n-1; j >= 1; j --)

for(int i = 1; i <= m; i ++)

in these two loops I fill my table and finally I find my minimum in the first column and print the path.

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.