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.