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.

USACO - Barn Repair

Barn Repair

It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John's cows. Happily, many of the cows were on vacation, so the barn was not completely full.
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.

USACO - Mixing Milk

Mixing Milk

Since milk packaging is such a low margin business, it is important to keep the price of the raw product (milk) as low as possible. Help Merry Milk Makers get the milk they need in the cheapest possible manner.
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, Pi and Ai. Pi (0 <= Pi <= 1,000) is price in cents that farmer i charges. Ai (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

Transformations
A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible 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.

In the case that more than one transform could have been used, choose the one with the minimum number above.

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

Palindromic Squares
Rob Kolstad Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.
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

Dual Palindromes
Mario Cruz (Colombia) & Hugo Rickeboer (Argentina) A number that reads the same from right to left as when read from left to right is called a palindrome. The number 12321 is a palindrome; the number 77778 is not. Of course, palindromes have neither leading nor trailing zeroes, so 0220 is not a palindrome.
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)

and then finds and prints (in base 10) the first N numbers strictly greater than S that are palindromic when written in two or more number bases (2 <= base <= 10). Solutions to this problem do not require manipulating integers larger than the standard 32 bits.

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

Name That Number
Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of this filing system, though, and wish to call the members of their herd by a pleasing name rather than saying, "C'mon, #4734, get along."
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,S

Acceptable 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 ISFI

As 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

Milking Cows
Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).
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 precision

First 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 n-th car to come and this time is calculated.

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

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

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

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

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.

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.

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

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)

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.

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

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