problem statement

Ad Hoc

Easily you have to convert each character in the input to its left character on the keyboard.

string kb = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;\'ZXCVBNM,./";

while( getline(cin, line) )

{

for(int i = 0; i < line.size(); i ++)

cout << (line[i] != ' ' ? kb[ kb.find(line[i]) - 1 ] : ' ');

cout << endl;

}

In this solution I saved all the keyboard in a string named kb, and for each character, I find it in the string kb and print the previous character.

I use a good member function of class string, stringName.find( ch ) that return the position of ch in stringName or string::pos if ch is not in the string.

## Friday, December 31, 2010

### UVA - 572 - Oil Deposits

problem statement

graph algorithms, finding number of components using DFS or BFS

If you read the problem statement carefully you can see that you have to find the number of components of a graph, I use DFS to do that.

in body of main :

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

for(int j = 0; j < n; j ++)

if( grid[i][j] == '@' && mark[i][j] == false )

dfs( i, j ), comp ++;

void dfs( int r, int c )

{

mark[r][c] = true;

for(int i = r-1; i <= r+1; i ++)

for(int j = c-1; j <= c+1; j ++)

if( inRange( i, j ) && grid[i][j] == '@' && mark[i][j] == false )

dfs( i, j );

}

graph algorithms, finding number of components using DFS or BFS

If you read the problem statement carefully you can see that you have to find the number of components of a graph, I use DFS to do that.

in body of main :

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

for(int j = 0; j < n; j ++)

if( grid[i][j] == '@' && mark[i][j] == false )

dfs( i, j ), comp ++;

void dfs( int r, int c )

{

mark[r][c] = true;

for(int i = r-1; i <= r+1; i ++)

for(int j = c-1; j <= c+1; j ++)

if( inRange( i, j ) && grid[i][j] == '@' && mark[i][j] == false )

dfs( i, j );

}

Labels:
UVA

### UVA - 11063 - B2-sequence

problem statement

Simulation - STL - set

complete search

take care about negative numbers

take care about repetitive numbers

take care about this numbers have to be in increasing order

1 <= b1 < b2 < b3 ...

if( a[i] <= 0 )

isB2 = false;

if( i >= 1 && a[i] <= a[i-1] )

isB2 = false;

if( mark.count( a[i]+a[j] ) == true )

isB2 = false;

Simulation - STL - set

complete search

take care about negative numbers

take care about repetitive numbers

take care about this numbers have to be in increasing order

1 <= b1 < b2 < b3 ...

if( a[i] <= 0 )

isB2 = false;

if( i >= 1 && a[i] <= a[i-1] )

isB2 = false;

if( mark.count( a[i]+a[j] ) == true )

isB2 = false;

Labels:
UVA

### UVA - 11340 - Newspaper

problem statement

string - Ad Hoc

As you can see in the problem description, some characters with their costs are given to you, a passage comes after that, and you have to count each character in that passage and find out how much money publisher must pay for a text, characters that are not given a specific cost have to be considered with cost 0.

After I read and count occurrence of each character, I find the cost of the passage with these two lines of code :

for(int i = 0; i < 400; i ++)

cent += occurrence[i] * cost[i];

and print output in this manner :

int dol = cent / 100;

cent %= 100;

cout << dol << "." << (cent < 10 ? "0": "") << cent << "$" << endl;

string - Ad Hoc

As you can see in the problem description, some characters with their costs are given to you, a passage comes after that, and you have to count each character in that passage and find out how much money publisher must pay for a text, characters that are not given a specific cost have to be considered with cost 0.

After I read and count occurrence of each character, I find the cost of the passage with these two lines of code :

for(int i = 0; i < 400; i ++)

cent += occurrence[i] * cost[i];

and print output in this manner :

int dol = cent / 100;

cent %= 100;

cout << dol << "." << (cent < 10 ? "0": "") << cent << "$" << endl;

Labels:
UVA

### UVA - 11228 - Transportation System

problem statement

graph algorithms, minimum spanning tree, Prim - Kruskal

In this problem you have to find several MSTs. (one MST in each state and one MST between all states)

First you have to find out which cities are in each state and then run MST for that state and

then suppose each state as a node that have railroads to other states(nodes) and run MST for the whole states that now are considered as single nodes.

I want to describe all my code here.

I have a struct to save edge i-->j and the cost :

struct edge

{

int p, q;

double d;

edge ( int _p = 0, int _q = 0, double _d = 0 )

{

p = _p, q = _q, d = _d;

}

const bool operator <( const edge &two ) const

{

return d < two.d;

}

};

I save my input in this datastructure :

double p[1001][2];

This function gives me the distance between point 'i' and point 'j' :

double distF( int i, int j )

{

return sqrt( (p[i][0]-p[j][0])*(p[i][0]-p[j][0]) + (p[i][1]-p[j][1])*(p[i][1]-p[j][1]) );

}

I use disjoint set datastructure two time in my code, first to find out whether point A and point B are in the same state, how do I do that? I mark each node with par[i],

that means if for example par[2] = 3 node 2 is in the same state as 3 is and 3 is the representative of the state( or set ), and par[4] = 5 mean that node 4 is in the same state as 5 and the representative of the set is 5, then if I find an edge between node 2 and node 4, I have to merge these two sets, and I do it with function merge(int, int), and whenever I want to know whether two nodes are in the same state or not, I use function find(int) which gives me the representative of the set which my node is in and then compare find( x ) and find( y ) if they are equal they are in the same set, otherwise I have to merge them.

int find( int x )

{

if(x == par[x])

return x;

return par[x] = find( par[x] );

}

void merge( int x, int y )

{

par[ find(x) ] = find( y );

}

Now I'm ready to read input, I save input in p[i][0] and p[i][1] and then run distF( int, int ) and set the distance between point 'i' and point 'j' and then run disjoint set datastructure to find out which nodes are in the same state( as mentioned in the problem description two nodes are in the same state if the distance between them is less than 'r' ), now I have some states that I have to run MST in each state and after that I have to look at each state as single node, that have several edges to other states, so now I have to find the complete graph of the states, and then run MST for that, but between each node I have several edges( a multigraph ) so I have to choose the minimum edge between two states( suppose state 'i' has A nodes and state 'j' has B nodes, there are A*B edges between these two states that I just want the edge with minimum cost ), so I construct my graph in this way and run MST for that.

This is my MST body, "all" is a vector of edge, that all the edges of a graph are pushed back into it.

sort( all.begin(), all.end() );

for(int i = 0; i < n; i ++)

par[i] = i;

for(int k = 0; k < all.size(); k ++)

{

if( find( all[k].p ) == find( all[k].q ) )

continue;

railRoads += all[k].d;

merge( all[k].p, all[k].q );

}

graph algorithms, minimum spanning tree, Prim - Kruskal

In this problem you have to find several MSTs. (one MST in each state and one MST between all states)

First you have to find out which cities are in each state and then run MST for that state and

then suppose each state as a node that have railroads to other states(nodes) and run MST for the whole states that now are considered as single nodes.

I want to describe all my code here.

I have a struct to save edge i-->j and the cost :

struct edge

{

int p, q;

double d;

edge ( int _p = 0, int _q = 0, double _d = 0 )

{

p = _p, q = _q, d = _d;

}

const bool operator <( const edge &two ) const

{

return d < two.d;

}

};

I save my input in this datastructure :

double p[1001][2];

This function gives me the distance between point 'i' and point 'j' :

double distF( int i, int j )

{

return sqrt( (p[i][0]-p[j][0])*(p[i][0]-p[j][0]) + (p[i][1]-p[j][1])*(p[i][1]-p[j][1]) );

}

I use disjoint set datastructure two time in my code, first to find out whether point A and point B are in the same state, how do I do that? I mark each node with par[i],

that means if for example par[2] = 3 node 2 is in the same state as 3 is and 3 is the representative of the state( or set ), and par[4] = 5 mean that node 4 is in the same state as 5 and the representative of the set is 5, then if I find an edge between node 2 and node 4, I have to merge these two sets, and I do it with function merge(int, int), and whenever I want to know whether two nodes are in the same state or not, I use function find(int) which gives me the representative of the set which my node is in and then compare find( x ) and find( y ) if they are equal they are in the same set, otherwise I have to merge them.

int find( int x )

{

if(x == par[x])

return x;

return par[x] = find( par[x] );

}

void merge( int x, int y )

{

par[ find(x) ] = find( y );

}

Now I'm ready to read input, I save input in p[i][0] and p[i][1] and then run distF( int, int ) and set the distance between point 'i' and point 'j' and then run disjoint set datastructure to find out which nodes are in the same state( as mentioned in the problem description two nodes are in the same state if the distance between them is less than 'r' ), now I have some states that I have to run MST in each state and after that I have to look at each state as single node, that have several edges to other states, so now I have to find the complete graph of the states, and then run MST for that, but between each node I have several edges( a multigraph ) so I have to choose the minimum edge between two states( suppose state 'i' has A nodes and state 'j' has B nodes, there are A*B edges between these two states that I just want the edge with minimum cost ), so I construct my graph in this way and run MST for that.

This is my MST body, "all" is a vector of edge, that all the edges of a graph are pushed back into it.

sort( all.begin(), all.end() );

for(int i = 0; i < n; i ++)

par[i] = i;

for(int k = 0; k < all.size(); k ++)

{

if( find( all[k].p ) == find( all[k].q ) )

continue;

railRoads += all[k].d;

merge( all[k].p, all[k].q );

}

Labels:
UVA

## Sunday, December 12, 2010

### UVA - 10077 - The Stern-Brocot Number System

problem statement

Divide and Conquer, like binary search

In this problem You have a number a/b that want to construct it as stated in the problem description.

In each step you have to decide whether go left or go right? So you compare a/b with your current number which is (s1+t1)/(s2+t2) and decide to go right or left and when you arrive in a level that you've found the number, write the string that you've constructed.

Initially s1=0, t1=1 and s2=1, t2=0.

I have a function which takes ( s1, s2, a, b, t1, t2 ) and Divides and Conquers. :-D

if( b*(s1+t1) < a*(s2+t2) ) D_and_C( s1+t1, s2+t2, a, b, t1, t2 ), output += 'R';

else D_and_C( s1, s2, a, b, t1+s1, t2+s2 ), output += 'L';

if( a==s1+t1 && b==s2+t2 ) print output;

Divide and Conquer, like binary search

In this problem You have a number a/b that want to construct it as stated in the problem description.

In each step you have to decide whether go left or go right? So you compare a/b with your current number which is (s1+t1)/(s2+t2) and decide to go right or left and when you arrive in a level that you've found the number, write the string that you've constructed.

Initially s1=0, t1=1 and s2=1, t2=0.

I have a function which takes ( s1, s2, a, b, t1, t2 ) and Divides and Conquers. :-D

if( b*(s1+t1) < a*(s2+t2) ) D_and_C( s1+t1, s2+t2, a, b, t1, t2 ), output += 'R';

else D_and_C( s1, s2, a, b, t1+s1, t2+s2 ), output += 'L';

if( a==s1+t1 && b==s2+t2 ) print output;

Labels:
UVA

### UVA - 10167 - Birthday Cake

problem statement

computational geometry, brute force, complete search

In this problem You have a cake with radius 100 and 2N cherries that are placed on the cake.

The center of the cake is Origin, You have to cut the cake in 2 parts in a fairly manner that each part has equal cherries and no cherry is on the beeline of division.

Since There are at most 100 cherries and the beeline must go through the center of the cake and the radius of the cake is 100, You can set (A >= 0 && A <= 100) and (B >= -100 && B <= 100) and each time make a beeline with this A and B (Ax+By=0) that goes through the Origin and check whether there are equal cherries

in each side of the beeline and no cherry is on the beeline, if yes print x and y and break.

Check if( A*x[i]+B*y[i] > 0 ) one ++; else if( A*x[i]+B*y[i] < 0 ) two ++;

if( one == n && two == n ) print A and B.

In this way you will get an accept in the suggested time limit.

computational geometry, brute force, complete search

In this problem You have a cake with radius 100 and 2N cherries that are placed on the cake.

The center of the cake is Origin, You have to cut the cake in 2 parts in a fairly manner that each part has equal cherries and no cherry is on the beeline of division.

Since There are at most 100 cherries and the beeline must go through the center of the cake and the radius of the cake is 100, You can set (A >= 0 && A <= 100) and (B >= -100 && B <= 100) and each time make a beeline with this A and B (Ax+By=0) that goes through the Origin and check whether there are equal cherries

in each side of the beeline and no cherry is on the beeline, if yes print x and y and break.

Check if( A*x[i]+B*y[i] > 0 ) one ++; else if( A*x[i]+B*y[i] < 0 ) two ++;

if( one == n && two == n ) print A and B.

In this way you will get an accept in the suggested time limit.

Labels:
UVA

### UVA - 11792 - Krochanska is Here!

problem statement

graph search algorithm - single source unweighted shortest path - BFS from some sources

You are facing a multi BFS problem that you have to run BFS from multiple sources, that are called important stations here.

First I have a boolean 2d array "mark" that I can figure out that in each line which stations are used and find out which stations are "important stations".

Important stations are stations that mark is true for that station in more than one line.

Then easily I run BFS for each important station and find the sum of the distances from

the current important station that I've run BFS from to the other important stations and save that in a vector ave, and finally I find the minimum sum of distances from vector ave and print output.

And how I save my graph : I use a vector adj[10001] and try to save each vertex's

neighbours in that.

graph search algorithm - single source unweighted shortest path - BFS from some sources

You are facing a multi BFS problem that you have to run BFS from multiple sources, that are called important stations here.

First I have a boolean 2d array "mark" that I can figure out that in each line which stations are used and find out which stations are "important stations".

Important stations are stations that mark is true for that station in more than one line.

Then easily I run BFS for each important station and find the sum of the distances from

the current important station that I've run BFS from to the other important stations and save that in a vector

And how I save my graph : I use a vector

neighbours in that.

Labels:
UVA

## Sunday, December 5, 2010

### USACO - Calf Flac

**Calf Flac**

Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z' and `a-z'.

Find the largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.

### PROGRAM NAME: calfflac

### INPUT FORMAT

A file with no more than 20,000 characters. The file has one or more lines. No line is longer than 80 characters (not counting the newline at the end).### SAMPLE INPUT (file calfflac.in)

Confucius say: Madam, I'm Adam.

### OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.### SAMPLE OUTPUT (file calfflac.out)

11 Madam, I'm Adam

Greedy - longest palindrome with size less than 2000 - brute force

In this problem you have a string with size 20,000 and want to find the longest palindrome with size less than 2000, but there are non-alphabetical characters in the input file. So I first read input, I have two arrays for input, one is the input and the other is the transformed input and indexing of the alphabets that I have saved in lower case.

Then I iterate from 0 to size of input and each time I check two things: First : if current character is the middle character, how much can we extend the palindrome from left and right, So I iterate 1000 to left and 1000 to right and wherever it's not yet a palindrome I stop continuing to expand the palindrome,this is when the size of the palindrome is odd, when the size of the palindrome is even I set the current and next character as the core of my palindrome with size even, and again expand the current palindrome. In this approach time complexity is O(20,000 * 2000).

Labels:
USACO

### USACO - Prime Cryptarithm

**Prime Cryptarithm**

* * * x * * ------- * * * <-- partial product 1 * * * <-- partial product 2 ------- * * * *Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed. Note that the 'partial products' are as taught in USA schools. The first partial product is the product of the final digit of the second number and the top number. The second partial product is the product of the first digit of the second number and the top number.

Write a program that will find all solutions to the cryptarithm above for any subset of digits from the set {1,2,3,4,5,6,7,8,9}.

### PROGRAM NAME: crypt1

### INPUT FORMAT

Line 1: | N, the number of digits that will be used |

Line 2: | N space separated digits with which to solve the cryptarithm |

### SAMPLE INPUT (file crypt1.in)

5 2 3 4 6 8

### OUTPUT FORMAT

A single line with the total number of unique solutions. Here is the single solution for the sample input:2 2 2 x 2 2 ------ 4 4 4 4 4 4 --------- 4 8 8 4

### SAMPLE OUTPUT (file crypt1.out)

1

Ad hoc - iteration - simulation

There are two ways to solve this problem.

First you can easily iterate from a=100 to a=999 and from b=10 to b=99 in nested for loops, then you can produce the product of a and b and check whether the digits of a, b and a*b are valid or not, if yes increment your output. This approach runs in O(1000 * 100).

Second you can set the digits of a and b, a[0], a[1], a[2] and b[0], b[1] from your input, in this way you don't have to check the validity of a[i] and b[i] and then produce the product of a and b, and now check whether the digits of a*b are valid or not. This approach runs in O(9^5) that is a little better but harder to implement.

Labels:
USACO

### USACO - Barn Repair

# Barn Repair

The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width.

Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase.

Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calculate the minimum number of stalls that must be blocked in order to block all the stalls that have cows in them.

Print your answer as the total number of stalls blocked.

### PROGRAM NAME: barn1

### INPUT FORMAT

Line 1: | M, S, and C (space separated) |

Lines 2-C+1: | Each line contains one integer, the number of an occupied stall. |

### SAMPLE INPUT (file barn1.in)

4 50 18 3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43

### OUTPUT FORMAT

A single line with one integer that represents the total number of stalls blocked.### SAMPLE OUTPUT (file barn1.out)

25[One minimum arrangement is one board covering stalls 3-8, one covering 14-21, one covering 25-31, and one covering 40-43.]

Greedy - sorting - finding maximum difference each time

Here you have a problem that you have C numbers and you want to split them in M-1 places so remains M sequences that the sum of the difference between the first and last number is each sequence becomes minimum.

For example something like this :

a1 a2 a3 ..... aC

you have to split this sequence in M-1 places so that :

aK1-a1+1 + aK3-aK2+1 + aK4-aK3+1 + ..... + aC-aKM-1 +1 is minimized.

First you have to sort the numbers. Then each time you have to find the maximum difference between two adjacent numbers and choose it to be the index you want to split your sequence. Do this M-1 times and then you have M sequences that the sum of the differences between the first and last number in each sequence is minimum.

Labels:
USACO

### USACO - Mixing Milk

# Mixing Milk

The Merry Milk Makers company has several farmers from which they may buy milk, and each one has a (potentially) different price at which they sell to the milk packing plant. Moreover, as a cow can only produce so much milk a day, the farmers only have so much milk to sell per day. Each day, Merry Milk Makers can purchase an integral amount of milk from each farmer, less than or equal to the farmer's limit.

Given the Merry Milk Makers' daily requirement of milk, along with the cost per gallon and amount of available milk for each farmer, calculate the minimum amount of money that it takes to fulfill the Merry Milk Makers' requirements.

Note: The total milk produced per day by the farmers will be sufficient to meet the demands of the Merry Milk Makers.

### PROGRAM NAME: milk

### INPUT FORMAT

Line 1: | Two integers, N and M. The first value, N, (0 <= N <= 2,000,000) is the amount of milk that Merry Milk Makers' want per day. The second, M, (0 <= M <= 5,000) is the number of farmers that they may buy from. |

Lines 2 through M+1: | The next M lines each contain two integers, P_{i} and A_{i}. P _{i} (0 <= P_{i} <= 1,000) is price in cents that farmer i charges.A _{i} (0 <= Ai <= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day. |

### SAMPLE INPUT (file milk.in)

100 5 5 20 9 40 3 10 8 80 6 30

### OUTPUT FORMAT

A single line with a single integer that is the minimum price that Merry Milk Makers can get their milk at for one day.### SAMPLE OUTPUT (file milk.out)

630

Greedy - sorting

This problem is solved using a straight forward greedy algorithm, you can easily see that if you sort the input by prices and buy milk from those who sell milk cheaper, you will result in the optimum answer.

For example in the sample input you can see that : you need 100 gallons of milk and there are 5 farmers available for you to buy milk from. First you buy

10 gallons from the farmer who sells milk 3 cents per gallon, then

20 gallons from the farmer who sells milk 5 cents per gallon, then

30 gallons from the farmer who sells milk 6 cents per gallon, then

40 gallons from the farmer who sells milk 8 cents per gallon ( this farmer has 80 gallons available but you just need 40 gallons to reach 100 gallons each day )

So the answer is 10*3 + 20*5 + 30*6 + 40*8 = 30 + 100 + 180 + 320 = 630

Labels:
USACO

### USACO - Transformations

**Transformations**

- #1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
- #2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
- #3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
- #4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).
- #5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).
- #6: No Change: The original pattern was not changed.
- #7: Invalid Transformation: The new pattern was not obtained by any of the above methods.

### PROGRAM NAME: transform

### INPUT FORMAT

Line 1: | A single integer, N |

Line 2..N+1: | N lines of N characters (each either `@' or `-'); this is the square before transformation |

Line N+2..2*N+1: | N lines of N characters (each either `@' or `-'); this is the square after transformation |

### SAMPLE INPUT (file transform.in)

3 @-@ --- @@- @-@ @-- --@

### OUTPUT FORMAT

A single line containing the the number from 1 through 7 (described above) that categorizes the transformation required to change from the `before' representation to the `after' representation.### SAMPLE OUTPUT (file transform.out)

1

Ad hoc - string manipulation

In my solution I have 3 funcions f90(), cmp() and reflect()

f90( string [], string [], int ); takes two arrays of string and an integer -the size of arrays- and rotates the grid 90 degrees clockwise and put it into the second array of string

cmp( string [], string [], int ); takes two arrays of string and an integer -the size of arrays- and compares them whether they are equal or not

reflect( string [], string [], int ); takes two arrays of string and an integer -the size of arrays- and reflects the first one round a vertical line and put it into the second one

for rotating 180 and 270 degrees I used 2 or 3 times of f90(), respectively.

read the problem description carefully as it says : "In the case that more than one transform could have been used, choose the one with the minimum number above."

Labels:
USACO

### USACO - Palindromic Squares

**Palindromic Squares**

Rob Kolstad

Given a number base B (2 <= B <= 20 base 10), print all the integers N (1 <= N <= 300 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters 'A', 'B', and so on to represent the digits 10, 11, and so on.

Print both the number and its square in base B.

### PROGRAM NAME: palsquare

### INPUT FORMAT

A single line with B, the base (specified in base 10).### SAMPLE INPUT (file palsquare.in)

10

### OUTPUT FORMAT

Lines with two integers represented in base B. The first integer is the number whose square is palindromic; the second integer is the square itself.### SAMPLE OUTPUT (file palsquare.out)

1 1 2 4 3 9 11 121 22 484 26 676 101 10201 111 12321 121 14641 202 40804 212 44944 264 69696

Brute force - base conversion - palindrome checking

Produce all the squares of numbers from 1 to 300, convert them to base b and check whether they are palindrome or not, if they are, convert the number to base b too and print both the number and it's square that has been converted to base b.

I have two functions in my solution, toBase( int, int ) and isPal( string ). In toBase() function I convert the given number to base b, and in function isPal() I check whether the given string is palindrome or not with two iterators to the beginning and to the end of the string.

Labels:
USACO

### USACO - Dual Palindromes

**Dual Palindromes**

**Mario Cruz (Colombia) & Hugo Rickeboer (Argentina)**

The number 21 (base 10) is not palindrome in base 10, but the number 21 (base 10) is, in fact, a palindrome in base 2 (10101).

Write a program that reads two numbers (expressed in base 10):

- N (1 <= N <= 15)
- S (0 < S < 10000)

### PROGRAM NAME: dualpal

### INPUT FORMAT

A single line with space separated integers N and S.### SAMPLE INPUT (file dualpal.in)

3 25

### OUTPUT FORMAT

N lines, each with a base 10 number that is palindromic when expressed in at least two of the bases 2..10. The numbers should be listed in order from smallest to largest.### SAMPLE OUTPUT (file dualpal.out)

26 27 28

Brute force search - base conversion - palindrome checking

Easily iterate from s+1 and each time convert the number to all the bases and check whether they are palindrome or not, if the number is palindrome in more than 2 bases, print that number and decrement n.

when I want to convert a number to base b, I used strings, it's simpler to check whether it is palindrome or not, and for checking whether the given string is palindrome or not I use two pointers to the beginning and to the end of the string and check whether they are equal or not, whenever a position is found that they are not equal I return false, otherwise I return true at the end.

Labels:
USACO

### USACO - Name That Number

**Name That Number**

Help the poor cowhands out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone(R) telephone keypad mapping to get from numbers to letters (except for "Q" and "Z"):

2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,SAcceptable names for cattle are provided to you in a file named "dict.txt", which contains a list of fewer than 5,000 acceptable cattle names (all letters capitalized). Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary which is supplied as dict.txt in the grading environment (and is sorted into ascending order).

For instance, the brand number 4734 produces all the following names:

GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFIAs it happens, the only one of these 81 names that is in the list of valid names is "GREG".

Write a program that is given the brand number of a cow and prints all the valid names that can be generated from that brand number or ``NONE'' if there are no valid names. Serial numbers can be as many as a dozen digits long.

### PROGRAM NAME: namenum

### INPUT FORMAT

A single line with a number from 1 through 12 digits in length.### SAMPLE INPUT (file namenum.in)

4734

### OUTPUT FORMAT

A list of valid names that can be generated from the input, one per line, in ascending alphabetical order.### SAMPLE OUTPUT (file namenum.out)

GREG

String - complete search - using STL map, string & vector

There are two approaches to this problem:

First : since the input number has at most 12 digits and for each digit there are 3 candidates if you build all the possibilities and then search them in the dictionary the order of your program will become

O(3^12 * nlog(n)) n = 5000 531441 * 42585 that I think is a little too high to run in the time limit.

Second : you can map all the strings in the dictionary to The explained number, and then easily when you read the input number search that whether you have that number in your map data structure and print all the strings mapped to that number, print "NONE" otherwise.

Labels:
USACO

### USACO - Milking Cows

**Milking Cows**

Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):

- The longest time interval at least one cow was milked.
- The longest time interval (after milking starts) during which no cows were being milked.

### PROGRAM NAME: milk2

### INPUT FORMAT

Line 1: | The single integer |

Lines 2..N+1: | Two non-negative integers less than 1000000, the starting and ending time in seconds after 0500 |

### SAMPLE INPUT (file milk2.in)

3 300 1000 700 1200 1500 2100

### OUTPUT FORMAT

A single line with two integers that represent the longest continuous time of milking and the longest idle time.### SAMPLE OUTPUT (file milk2.out)

900 300

Sorting - Ad hoc - iteration with high precisionFirst sort the elements by the start time of milking then iterate and keep track of maxEnd and minStart till now, if the current times have intersection with the minStart and maxEnd, then update your maxEnd time, else change the minStart and maxEnd to the current times (start[i], end[i]), this is for the longest time that at list one cow is being milked.

For the longest time that no cow is being milked, easily do the same, if the current start[cur] > maxEnd, you have a gap here, so keep track of start[cur]-maxEnd and update minStart and maxEnd.

At the end choose the maximum between your values.

Labels:
USACO

### TJU - 1415 - Ferry Loading II

problem statement

greedy - ad hoc - simulation

you have to check whether you can load each time n cars or not, if not the first load must be m%n and the rest loads n cars.

then you have to iterate to see when a load comes back are there n other cars ready or not and then decide what to do next.

if they are ready ferry loads the cars and leaves soon, otherwise ferry has to wait for the n-th car to come and this time is calculated.

greedy - ad hoc - simulation

you have to check whether you can load each time n cars or not, if not the first load must be m%n and the rest loads n cars.

then you have to iterate to see when a load comes back are there n other cars ready or not and then decide what to do next.

if they are ready ferry loads the cars and leaves soon, otherwise ferry has to wait for the n-th car to come and this time is calculated.

Labels:
TJU

## Thursday, December 2, 2010

### TJU - 1477 - binary numbers

problem statement

bits - binary presentation of N

Easily in this problem you have to find out the locations of 1's in the binary presentation of a number N.

I iterate from i=0 to 2^i <= 1000000 and each time check whether ( N & 2^i != 0 ) or not and print i if result is true.

1 << i

00000001

00000010

00000100

00001000

00010000

00100000

01000000

10000000

bits - binary presentation of N

Easily in this problem you have to find out the locations of 1's in the binary presentation of a number N.

I iterate from i=0 to 2^i <= 1000000 and each time check whether ( N & 2^i != 0 ) or not and print i if result is true.

1 << i

00000001

00000010

00000100

00001000

00010000

00100000

01000000

10000000

Labels:
TJU

## Monday, October 18, 2010

### 11000 - Bee - UVA

Fibonacci numbers

If you write the sequence resulted from the description, you'll see that you have to find sum of the first n Fibonacci numbers + sum of the first (n-1) Fibonacci numbers.

Sum Fib( i ) = Fib(n+2)-1

----- i = 0...n

Use long long int and you just need to calculate the first 46 sentences of the Fibonacci numbers.

For more information about Fibonacci numbers read this :

http://en.wikipedia.org/wiki/Fibonacci_number

If you write the sequence resulted from the description, you'll see that you have to find sum of the first n Fibonacci numbers + sum of the first (n-1) Fibonacci numbers.

Sum Fib( i ) = Fib(n+2)-1

----- i = 0...n

Use long long int and you just need to calculate the first 46 sentences of the Fibonacci numbers.

For more information about Fibonacci numbers read this :

http://en.wikipedia.org/wiki/Fibonacci_number

Labels:
UVA

## Sunday, October 17, 2010

### 11239 - Open Source - UVA

Data Structures - STL map or set - sorting

As shown in the problem description, you have to count the number of students who have signed up for each project. There are some important hints in this problem that you have to concern :

If someone has signed up for more than one project do not count him for any of them.

If someone has written his name for a project more than one time, It's OK, just count him once in that project.

Data structure I use in this problem :

map (string, set(string) ) === to save for each project which students want to attend

map (string, string) === to save this student is singed for which project previously

set (string) === to save which student has signed up and can not attend any other project, if a student want to sign up for more than one project I find the previous project he/she has signed up for and delete him/her from that list

vector (int, string) === to produce output and sort it by number of students attending each project and then alphabetically by the name of the project

As shown in the problem description, you have to count the number of students who have signed up for each project. There are some important hints in this problem that you have to concern :

If someone has signed up for more than one project do not count him for any of them.

If someone has written his name for a project more than one time, It's OK, just count him once in that project.

Data structure I use in this problem :

set (string) ===

vector (int, string) === to produce output and sort it by number of students attending each project and then alphabetically by the name of the project

Labels:
UVA

### 10226 - Hardwood Species - UVA

Data Structures - STL map or set

In this problem you will read some tree names from input and must count the number of trees and at the end print the percentage of trees.

What can we do? We read tree names one by one, when reading a tree name, you have to increment the number of that tree counted till now, so you have to find the index of that tree to increment it. If you use linear search to find the index you will get a TLE (Time Limit Exceeded), so you have to use a binary search. using set or map data structures that have a binary search with them is appropriate. MAPs and SETs are always sorted.

I use a map data structure from string to int and each time I read a tree name I increment the counter of that tree.

map mp;

while( getline( cin, tree ), tree != "" )

{

mp[tree] ++;

total ++;

}

and at the end I print (each counter/total).

In this problem you will read some tree names from input and must count the number of trees and at the end print the percentage of trees.

What can we do? We read tree names one by one, when reading a tree name, you have to increment the number of that tree counted till now, so you have to find the index of that tree to increment it. If you use linear search to find the index you will get a TLE (Time Limit Exceeded), so you have to use a binary search. using set or map data structures that have a binary search with them is appropriate. MAPs and SETs are always sorted.

I use a map data structure from string to int and each time I read a tree name I increment the counter of that tree.

map

while( getline( cin, tree ), tree != "" )

{

mp[tree] ++;

total ++;

}

and at the end I print (each counter/total).

Labels:
UVA

### 10928 - My Dear Neighbours - UVA

graph representation or Ad Hoc

In this problem you have to count the OUT-DEGREE of each node and find the minimum OUT-DEGREE and print nodes with the minimum OUT-DEGREE sequentially.

What you have to concern is type of input. I get input using stringstream and getline and count the neighbors of each node.

In this problem you have to count the OUT-DEGREE of each node and find the minimum OUT-DEGREE and print nodes with the minimum OUT-DEGREE sequentially.

What you have to concern is type of input. I get input using stringstream and getline and count the neighbors of each node.

Labels:
UVA

### 599 - The Forrest for the Trees - UVA

graph search algorithm - DFS

In this problem you have to find the number of components in a graph and you have to distinguish which components are isolated vertices. Easily run DFS for each unvisited node and count the number of components, set a counter before running DFS to find the number of vertices in a component, increment it at the beginnig and if this number was 1, it is an isolated vertex.

In this problem you have to find the number of components in a graph and you have to distinguish which components are isolated vertices. Easily run DFS for each unvisited node and count the number of components, set a counter before running DFS to find the number of vertices in a component, increment it at the beginnig and if this number was 1, it is an isolated vertex.

Labels:
UVA

### 924 - Spreading The News - UVA

graph search algorithm - BFS

In this problem you have to run BFS from a source, and find out that in the BFS-tree in which level you have the most nodes and in which level the most nodes come to BFS-tree.

I run BFS from the given source and find out the depth of each node from the source and then calculate which depth has the most nodes and what the level is.

if d[i] is the depth for node i from source then

for(int i = 0; i < n; i ++)

output[ d[i] ] ++;

find max from output and print the index of maximum as depth and output[index] as size of the maximum.

problem sample test case :

http://www.4shared.com/photo/va73oUQD/924_spreading_the_news.html

In this problem you have to run BFS from a source, and find out that in the BFS-tree in which level you have the most nodes and in which level the most nodes come to BFS-tree.

I run BFS from the given source and find out the depth of each node from the source and then calculate which depth has the most nodes and what the level is.

if d[i] is the depth for node i from source then

for(int i = 0; i < n; i ++)

output[ d[i] ] ++;

find max from output and print the index of maximum as depth and output[index] as size of the maximum.

problem sample test case :

http://www.4shared.com/photo/va73oUQD/924_spreading_the_news.html

Labels:
UVA

### 439 - Knight Moves - UVA

graph search algorithm - BFS

In this problem you are going to find out the shortest path between two cells of a chess board for a knight. I don't know how, but you have to prove that in a 8x8 chess board if you place a knight in a cell then it can reach any cell you want. So the shortest path problem works here.

The neighbors of a cell are these cells, if the cell is (x, y):

(x+1, y+2)

(x+1, y-2)

(x-1, y+2)

(x-1, y-2)

(x+2, y+1)

(x+2, y-1)

(x-2, y+1)

(x-2, y-1)

In this problem you are going to find out the shortest path between two cells of a chess board for a knight. I don't know how, but you have to prove that in a 8x8 chess board if you place a knight in a cell then it can reach any cell you want. So the shortest path problem works here.

The neighbors of a cell are these cells, if the cell is (x, y):

(x+1, y+2)

(x+1, y-2)

(x-1, y+2)

(x-1, y-2)

(x+2, y+1)

(x+2, y-1)

(x-2, y+1)

(x-2, y-1)

Labels:
UVA

## Sunday, October 10, 2010

### 10610 - Gopher and Hawks - UVA

graph search algorithm - BFS

You are given some points in a grid and have to calculate whether you can reach a end point from a start point or not. When you leave a point to reach another point you can just run for m*60 seconds, if you run more you will disappear ;-). So "distance between pi and pk / V < m*60" must satisfy to be sure that you can go from pi to pk, in this way I create adjacency matrix and then easily run a BFS on the graph to find the shortest path from the start point to the end point.

You are given some points in a grid and have to calculate whether you can reach a end point from a start point or not. When you leave a point to reach another point you can just run for m*60 seconds, if you run more you will disappear ;-). So "distance between pi and pk / V < m*60" must satisfy to be sure that you can go from pi to pk, in this way I create adjacency matrix and then easily run a BFS on the graph to find the shortest path from the start point to the end point.

Labels:
UVA

### 10926 - How Many Dependencies? - UVA

graph search algorithm - DFS

In this problem you have to find that if you start DFS from a node how many nodes are under this node in the DFS-tree and choose the maximum value of these for output.

Cause the input size is small and you are facing a DAG, don't think of complex algorithms to solve this problem, easily run DFS for each node and count how many nodes are invoked from this DFS and don't worry about cycles(there are no cycles in this problem). O(n^3)

data structures:

mat[101][101] = adjacency matrix

mark[101] = to mark which nodes are visited

In this problem you have to find that if you start DFS from a node how many nodes are under this node in the DFS-tree and choose the maximum value of these for output.

Cause the input size is small and you are facing a DAG, don't think of complex algorithms to solve this problem, easily run DFS for each node and count how many nodes are invoked from this DFS and don't worry about cycles(there are no cycles in this problem). O(n^3)

data structures:

mat[101][101] = adjacency matrix

mark[101] = to mark which nodes are visited

Labels:
UVA

### 928 - Eternal Truths - UVA

graph search algorithm - BFS

According to the problem description, you have to find the shortest path between two points in a grid, 'S' & 'E'.

data structures :

triple = a structure with 3 elements( x, y, length ), 'length' is the length of the last jump that has entered this cell

grid[301][301] = an array of strings with size of more than 300 for input grid

mark[301][301][4] = a 3d array to mark and save the distance from the start cell in a jump with size of 1, 2 or 3

After I get input, I find the position of the start and end point, then set all the members of mark to -1, and then create a queue of 'triple', push start to queue and set it's length to 1, because the next jump I can do from this point is a jump with length 1.

Then in a while loop I retrieve the last triple that I have pushed to queue and continue jumping from this point to the neighbor points, before I push the new triple into the queue, I set the length of it to "1 + the current triple's length" to save that how I can continue jumping from this point.

What you have to be careful of is that you can't jump through obstacles, for example assume that you can make jumps with size of 3 at this level. S.#E but you can't reach from 'S' to 'E', so check whether there are any obstacles in your jump or not.

At the end check mark[end.first][end.second][1,2,3], any of them that is not -1 and is the smallest one is the answer otherwise the answer is 'NO'.

According to the problem description, you have to find the shortest path between two points in a grid, 'S' & 'E'.

data structures :

triple = a structure with 3 elements( x, y, length ), 'length' is the length of the last jump that has entered this cell

grid[301][301] = an array of strings with size of more than 300 for input grid

mark[301][301][4] = a 3d array to mark and save the distance from the start cell in a jump with size of 1, 2 or 3

After I get input, I find the position of the start and end point, then set all the members of mark to -1, and then create a queue of 'triple', push start to queue and set it's length to 1, because the next jump I can do from this point is a jump with length 1.

Then in a while loop I retrieve the last triple that I have pushed to queue and continue jumping from this point to the neighbor points, before I push the new triple into the queue, I set the length of it to "1 + the current triple's length" to save that how I can continue jumping from this point.

What you have to be careful of is that you can't jump through obstacles, for example assume that you can make jumps with size of 3 at this level. S.#E but you can't reach from 'S' to 'E', so check whether there are any obstacles in your jump or not.

At the end check mark[end.first][end.second][1,2,3], any of them that is not -1 and is the smallest one is the answer otherwise the answer is 'NO'.

Labels:
UVA

Subscribe to:
Posts (Atom)