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.
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
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 = r1; i <= r+1; i ++)
for(int j = c1; 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 = r1; i <= r+1; i ++)
for(int j = c1; j <= c+1; j ++)
if( inRange( i, j ) && grid[i][j] == '@' && mark[i][j] == false )
dfs( i, j );
}
UVA  11063  B2sequence
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[i1] )
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[i1] )
isB2 = false;
if( mark.count( a[i]+a[j] ) == true )
isB2 = false;
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;
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 );
}
Sunday, December 12, 2010
UVA  10077  The SternBrocot 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;
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.
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.
Sunday, December 5, 2010
USACO  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 `AZ' and `az'.
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 nonalphabetical 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).
USACO  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.
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 2C+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 38, one covering 1421, one covering 2531, and one covering 4043.]
Greedy  sorting  finding maximum difference each time
Here you have a problem that you have C numbers and you want to split them in M1 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 M1 places so that :
aK1a1+1 + aK3aK2+1 + aK4aK3+1 + ..... + aCaKM1 +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 M1 times and then you have M sequences that the sum of the differences between the first and last number in each sequence is minimum.
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
USACO  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."
USACO  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.
USACO  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.
USACO  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 TouchTone(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.
USACO  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 nonnegative 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.
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 nth 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 nth car to come and this time is calculated.
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
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 (n1) 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 (n1) 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
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
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).
10928  My Dear Neighbours  UVA
graph representation or Ad Hoc
In this problem you have to count the OUTDEGREE of each node and find the minimum OUTDEGREE and print nodes with the minimum OUTDEGREE 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 OUTDEGREE of each node and find the minimum OUTDEGREE and print nodes with the minimum OUTDEGREE sequentially.
What you have to concern is type of input. I get input using stringstream and getline and count the neighbors of each node.
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.
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 BFStree in which level you have the most nodes and in which level the most nodes come to BFStree.
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 BFStree in which level you have the most nodes and in which level the most nodes come to BFStree.
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
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, y2)
(x1, y+2)
(x1, y2)
(x+2, y+1)
(x+2, y1)
(x2, y+1)
(x2, y1)
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, y2)
(x1, y+2)
(x1, y2)
(x+2, y+1)
(x+2, y1)
(x2, y+1)
(x2, y1)
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.
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 DFStree 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 DFStree 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
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'.
Subscribe to:
Posts (Atom)
USACO  Prime Palindromes
I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...

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 ...

Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing al...

I don't know why, but I had a great misunderstanding of the problem statement from this sentence "FJ pours milk from one bucket t...