UVA - 10082 - WERTYU

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.

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 );
}

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;

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;

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 );
        }

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;

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.

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.

USACO - Calf Flac

Calf Flac
It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties.
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).

USACO - Prime Cryptarithm

Prime Cryptarithm
The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a 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.