ACM Problem Hint

Codeforces Beta Round #91 (Div. 2 Only) - C. Lucky Sum

2012-01-06T19:12:00.000+03:30

problem statement
After reading the problem statement, at first I was shocked by the range of input, 1<=left<=right<=10^9, but after a close look to the problem again, I found that there are not too much lucky numbers in the range, I recursively generate lucky numbers with this function :

#define ll (long long)
vector all;
void back(ll v, ll p10)
{
    all.push_back(v);
    if(v > 1000000000)
        return;
    back(v+4*p10, p10*10);
    back(v+7*p10, p10*10);
}

then I sort "all", sort(all.begin(), all.end()),
and after that, I iterate through "all", I have a variable x that is the leftmost point that next(x) is not calculated yet, then if x <= all[i] this means all of the points k in range [x, all[i]], next(k) = all[i],
so I add (all[i]-x+1) * all[i] to the output, but if for example input is like this 2 6, I add (4-2+1)*4 + (7-5+1)*7 which is wrong, actual output is (4-2+1)*4 + (6-5+1)*7 so I added this if else to my code :
            if(all[i] <= right)
            {
                sum += (all[i]-x+1) * all[i];
                x = all[i]+1;
            }
            else
            {
                sum += (right-x+1) * all[i];
                x = all[i]+1;
            }

Codeforces Beta Round #91 (Div. 2 Only) - B. Lucky Substring

2012-01-06T16:33:00.000+03:30

problem statement
After reading the problem statement carefully and checking the sample test cases, I noticed this part of the problem "needs the lexicographically minimum one", and thought by myself if it is gonna be a substring of input and lucky and lexicographically minimum one, then it has to be "4" or "7" because other substrings that are lucky contain 4 and 7, and there is no lucky number other than "4" or "7" that is repeated more times than "4" or "7" because at least the lucky number is going to be "44", "77", "47", "74", and at this cases "4" and "7" are repeated more times than these substrings.
So I just iterated through input string and counted number of 4's and number of 7's, if there is no 4 or 7, then output -1, otherwise if cnt7 is less than cnt4 output 4 else output 7.

Codeforces Beta Round #91 (Div. 2 Only) - A. Lucky Division

2012-01-06T15:57:00.002+03:30

problem statement
As you read in the problem statement, you have to find out whether a number has a divisor which is also a lucky number, so iterate from 1 to n, if n is divisible by i, then check whether it is a lucky number or not?
Easily write a function that take a number and tell whether it is lucky or not, in other words the function checks whether all of the digits in the given number are 4 or 7.

bool isLucky(int n)
{
int rem;
while(n)
{
rem = n%10;
if(rem != 7 && rem != 4)
return false;
n /= 10;
}
return true;
}

UVA - 10596 - Morning Walk

2011-12-15T01:13:00.001+03:30

problem statement
If you read the problem statement carefully, It's obvious that you have to check whether an undirected graph has an Eulerian tour or not, necessary and sufficient conditions for and undirected graph :
An undirected graph has a closed Euler tour if it is connected and each vertex has an even degree.
I do this using a simple dfs to count the number of components.

UVA - 11099 - Next Same-Factored

2011-12-14T22:41:00.004+03:30

problem statement
After I read the problem statement, I tried to code the first solution that came to my mind, please do not laugh at me for my bad solution :-D, this solution is because I misunderstood the problem statement, my first approach was this : I tried to find the smallest prime factor of n, and output n*smallest factor, but very soon I found that output of 12 is not 12*2 but it's 18, cause 12 = 2^2*3, 24 = 2^3*3 and 18 = 2*3^2, So after I was disappointed for a moment, I tried to think of a new algorithm, and after some nonsense approaches I found that I have to precalculate a list for each number in range 1-10^6 that shows it's factors, and sort them, then whenever I read a number I can check next number in the sorted list, and check whether it's list is equal to the input list or not, if yes print that, and if not print "Not Exist!", I did this, at first run it took 12 seconds to run, and I know what the problem was, that was because of sorting a list which has vectors, I was sure this solution is gonna end with accepted, but don't know how, thinking and thinking..., I found that I have to remove vector, and put something else instead to reduce running time, at this time I remembered hashing :-D the key to solve the problem in my approach came along, and I was happy ;-).
I have a hash function like this :
int hash(string &s)
{
int res = 0;
    for(int i = 0; i < s.size(); i ++)
        res = res*127 + s[i];
    return res;
}
e.g. hash("abcd") = a*127^3 + b*127^2 + c*127^1 + d
and hash("abc") = a*127^2 + b*127^1 + c
6 => 2-3
12 => 2-3
18 => 2-3
24 => 2-3
36 => 2-3
.....
if look at their list like a string and produce their hash, all of them will have the same hash value and when I sort them they will be neighbor, hashValue( 6 ) = 2*127^2 + 3 = hashValue( 12 ) = hashValue( 18 ) = ...
I tried to build these hash values in a bottom-up manner, like this :
#define ll long long
    for(ll i = 0; i < prime.size(); i ++)
    {
        ll curP = prime[i];
        for(ll j = curP; j < SIZE; j += curP)
            all[j].hash = all[j].hash*1046527 + curP;
    }

but at first 1046527 was 127 and I got wrong answer, that was because some numbers hash value was a prime number and that would produce a problem, after I changed 127 I got accepted and running time was about 1 second.

TopCoder - SRM 515 DIV 2 - RotatedClock - getEarliest

2011-12-08T01:53:00.001+03:30

After I read the problem statement, I didn't find out what's going on :-D. I think the most important part of the problem for me was these two sentences : "The clock has a scale marked in 30 degree increments ... She measured the angles of hands from a certain mark". Before I pay attention to these two sentences, I was confused of test case 3, I was thinking why 19 19 is impossible? Then I found that measured degrees are from a certain mark, so both of them can not be 19 19, but of course both of them can be 0 0, 30 30, 60 60, 90 90 ...
At first I was trying to solve the problem in this way : Which mark has she chosen to measure the degrees? 0? 30? 60? 90? 120? 150? 180? 210? 240? 270? 300? 330? I thought that I could map one of the degrees to one of these 12 origins, then map the other one, and check whether the resulted degrees show a true time? then I figured out that it's a little hard to implement. I tried to reverse my approach. I iterated h = 0 to 12 and m = 0 to 60 and each time I made mDegree and hDegree, at this moment I have to verify whether mDegree and hDegree is an answer or not? So I shifted both of them 0 degrees, 30 degrees, 90 degrees, 120 degrees, ... 330 degrees and checked whether they matched input or not, if yes I had found the answer. But at this time I checked though my approach seems true but test case 2 gave me time 07:01 that's 210 degrees and 6 degrees that if I add 30 to both of them it becomes 240 and 36 that matches test case 2, I read the problem statement again and I found that her measurement device supports integer degrees not real numbers, because 07:01 is not 210 degrees and 6 degrees, it is 210.5 and 6. So I added another condition to my program that if minute was odd it is not my answer. And Finally Accepted :-).

TopCoder - SRM 515 DIV 2 - FortunateNumbers - getFortunate

2011-12-08T01:47:00.001+03:30

As you can see in the problem statement just a simple brute force is enough to pass the time limit. I produce all combinations of a[i] + b[j] + c[k] for all i, j, k and check whether it is a fortunate number or not, if yes I insert the number in a set and finally I return the size of the set.

TopCoder - SRM 144 DIV 1 - Lottery - sortByOdds

2011-12-04T10:35:00.001+03:30

If you read the problem statement carefully, you'll find out that we are facing 'blanks' spots that in each spot we can put [1, 'choices'], for simplicity n = blanks, up = choices
I categorize this problem as a counting problem in Combinatorics.

We can break this problem to 4 independent subproblems :

Case 1 : if sorted = false and unique = false, there is no condition, we want to fill each spot, and each spot has up candidates, so the answer is :
(up * up * ... * up)[n times] = up^n

Case 2 : if sorted = false && unique = true, what we put in n spots have to be unique, we have to choose n numbers out of up numbers and put all of the permutations of these numbers in the n spots so the answer is :
combination(up, n) * n! = ( (up!) / ((up-n)! * n!) )* n! = up! / (up-n)! = permutation(up, n)

Case 3 : if sorted = true && unique = true, what we put in spots have to be unique and sorted, so we have to choose n numbers out of up numbers and put the sorted version of this combination in the n spots, so the answer is :
combination(up, n) = up! / ((up-n)! * n!)

Case 4 : if sorted = true && unique = false, at this case suppose we have an array of size n and we want to fill the spots with numbers in range [1, up] and they have to be non-decreasing. e. g. n = 3 & up = 5 then [1, 2, 3], [1, 1, 1], [1, 2, 2], [5, 5, 5] and .... have to be counted in this case.
So we want the number of sorted arrays that are filled with numbers in range [1, up]. I tried to find a recurrent formula for this, think of the array like this that from left to right the indices decrease from n to 1, a[n], a[n-1], a[n-2] ... a[2], a[1]
mem(k, low) is the number of sorted arrays that start from index k and what we can put in this spot is at least low and at most up, what can we do to break the problem? Each time we can put a number at spot k and invoke mem(k-1, something), but what is 'something'? Yes, each time we put T = low...up and call mem(k-1, T), in this way we fix spot number k to T and tell the next index that you can be at least as T because I have fixed previous spot T, so mem(k, low) = mem(k-1, low) + mem(k-1, low+1) + mem(k-1, low+2) + ... + mem(k-1, up-1) + mem(k-1, up)
What is the trivial case? if k is 1(when we have just 1 spot) how many ways can we fill this spot? There are (up-low+1) ways to fill this spot. So the answer is :
mem(n, 1)
At this case we have to memoize the answer to prevent from a "Time Limit Exceeded" verdict.

To calculate combination(n, k) we have a recurrent formula that says combination(n, k) = combination(n-1, k-1) + combination(n-1, k), I also memoized this.

n! = n * (n-1)! -->> I memoized this too.

To calculate p^n, I wrote a function to calculate it in O(logn) with the fact that p^n = p^(n/2) * p^(n/2)

:-D But the problem wants something more than what I described. We have to parse the input and produce output. We need a struct like pair or something like that.
I described a struct by myself :
struct str
{
int p;
    string name;
    str(int _p = 0, string _name = "")
    {
        p = _p, name = name;
    }
    bool operator<(const str &two) const
    {
        return p < two.p && (p == two.p && name < two.name);
    }
};

I parsed input like this
string &s = rules[i];
string name = s.substr(0, s.find(':'));
string rest = s.substr(s.find(':')+1, 1000);
then I stringstream 'rest' and token up, n, sorted, unique.
then calculate probability, sort and produce output.

TopCoder - SRM 146 DIV 1 - RectangularGrid - countRectangles

2011-01-12T11:38:00.002+03:30

problem statement

In this problem you have to count the number of none-square rectangles in a given rectangle.
What I do is this, that I try to count all of
1*2, 1*3 ... 1*w
2*3, 2*4.... 2*w
......................
rectangles.

and I do this once for my rectangle and another time with the new rectangle with width and height swapped.
this is my code:
    long long func(int w, int h)
    {
        long long res = 0;
        for(int i = 1; i <= h; i ++)
            for(int j = i+1; j <= w; j ++)
                res += (w-j+1) * (h-i+1);
        return res;
    }
    long long countRectangles(int w, int h)
    {
        return func( w, h ) + func( h, w );
    }

How did I find this solution? I just tried to check it out on a piece of paper and I saw that there is a template for placing the rectangles with different width and heights in a larger rectangle.
For example if you want to place a 1*2 rectangle in a large rectangle, first you have to count how many of them are placed in a single row, (width-2+1) and multiply this number in height that is the number of 1*2 rectangles that are placed horizontally in a rectangle.

There are another solutions that I'm thinking about them, using 4 and 3 loops that I think they are trivial, and using 1 loop or even no loop that I'm thinking to understand them completely, then I'm gonna add them here.

TopCoder - SRM 145 DIV 1 - Bonuses - getDivision

2011-01-04T18:06:00.000+03:30

problem statement

This is a straight forward simulation problem. As described in the problem statement you find each persons percentage amounts and then you have to distribute the left over percentage among those who have greater points and if they have equal points, give extra 1% to who comes first in input and of course keep track of this person not to give extra 1% to him again.

vector getDivision(vector p)
{
    int n = p.size();
    vector out( n );

    int sum = accumulate( p.begin(), p.end(), 0 );
    for(int i = 0; i < n; i ++)
        out[i] = p[i]*100 / sum;
    int sum2 = accumulate( out.begin(), out.end(), 0 );

    vector mark(n, 0);
    for( ; sum2 < 100; sum2 ++)
    {
        int mx = -1, id = 0;
        for(int j = 0; j < n; j ++)
            if( mx < p[j] && mark[j] == 0 )
                mx = p[j], id = j;

        out[id] ++, mark[id] = 1;
    }
    return out;
}

TopCoder - SRM 145 DIV 2 - DitherCounter - count

2011-01-04T16:34:00.001+03:30

problem statement

In this problem you have to count how many of the characters of screen exist in dithered, to do this you can loop over the elements of screen and then for each element of screen search in dithered whether that character is there or not, O( n^3 ). But I do this O( n^2 ), since characters are only uppercase letters, at first I mark which characters are there in dithered, and then loop over screen and for each character it takes O( 1 ) to check whether it is in dithered or not.

TopCoder - SRM 144 DIV 1 - BinaryCode - decode

2011-01-04T02:23:00.001+03:30

problem statement

The problem sounds a little bit tricky at first but the test cases show you what you have to do. At first, when you assume about the first element of source to be '0' or '1', you can find the rest of them easily. But while doing this you have to take care about what you are pushing back into source, if it is some characters other than '0' or '1' the answer for this assumption is "NONE", and at the end I try to rebuild q from my result and see whether this q is equal to the given q or not? Why? Cause source[q.size()] must be equal to '0' because it's outside the string. There is one other way to do this, that while you are constructing source from given q, check whether source[q.size()] is equal to '0' or not, and there is no need to rebuild q from source.

This function returns the i-th element of string s, if i is out of range returns 0
int f( string &s, int i )
{
    if(i < 0 || i >= s.size() )
        return 0;
    return s[i]-'0';
}

This function checks whether the source that I've decoded is valid or not, by checking whether it has characters other than '0' and '1' or not, and checking that if I build q from s, is it equal to the given q or not?
bool valid( string &s, string &q )
{
    for(int i = 0; i < s.size(); i ++)
        if( s[i] != '0' && s[i] != '1' )
            return false;

    string t(q.size(), '0');
    for(int i = 0; i < s.size(); i ++)
        t[i] = f(s, i-1) + f(s, i) + f(s, i+1) + '0';

    if( q != t )
        return false;

    return true;
}

TopCoder - SRM 144 DIV 2 - Time - whatTime

2011-01-04T00:26:00.003+03:30

problem statement

In this problem, you have to convert a given second into it's equivalent standard time "h:m:s".
Easily I find how many 3600 are there in it, how many 60 are there left in it, and now I have h, m and s that I have to return a string not integers, so I convert each of them into a string and add them together in one string and return it.

int h = seconds/3600;
int m = (seconds%3600)/60;
int s = seconds%60;

        return f(h) + ":" + f(m) + ":" + f(s);

Function f(int) just converts the given integer into a string like this:
int f( int n )
{
   if( n == 0 )
      return "0";
   string res = "";
   while( n )
   {
res += n%10 + '0';
      n /= 10;
   }
   reverse( res.begin(), res.end() );
   return res;
}

UVA - 10082 - WERTYU

2010-12-31T19:03:00.000+03:30

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

2010-12-31T18:42:00.000+03:30

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

2010-12-31T18:35:00.001+03:30

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

2010-12-31T18:28:00.000+03:30

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

2010-12-31T18:11:00.001+03:30

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

2010-12-12T23:06:00.000+03:30

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

2010-12-12T22:25:00.001+03:30

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!

2010-12-12T18:52:00.000+03:30

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

2010-12-05T23:17:00.002+03:30

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

2010-12-05T23:13:00.002+03:30

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)

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

2010-12-05T23:08:00.001+03:30

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)

OUTPUT FORMAT

A single line with one integer that represents the total number of stalls blocked.

SAMPLE OUTPUT (file barn1.out)

[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

2010-12-05T23:05:00.001+03:30

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

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)

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

2010-12-05T23:01:00.001+03:30

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)

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

2010-12-05T22:55:00.001+03:30

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)

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)

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

2010-12-05T22:46:00.002+03:30

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

2010-12-05T01:10:00.015+03:30

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)

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

2010-12-05T00:56:00.004+03:30

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)

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

2010-12-05T00:49:00.001+03:30

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

2010-12-02T04:01:00.002+03:30

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

2010-10-18T01:45:00.001+03:30

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

2010-10-17T11:47:00.001+03:30

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

2010-10-17T10:04:00.001+03:30

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

2010-10-17T09:14:00.001+03:30

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

2010-10-17T09:03:00.001+03:30

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

2010-10-17T07:56:00.002+03:30

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

2010-10-17T07:48:00.001+03:30

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

2010-10-10T17:42:00.001+03:30

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

2010-10-10T16:48:00.001+03:30

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

2010-10-10T16:10:00.001+03:30

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

11388 - GCD LCM - UVA

2009-12-25T12:59:00.002+03:30

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 has mentioned that if there is more than one pair satisfying the condition, output the pair for which number a is minimized. It's a very easy problem, you have to figure out whether the remainder of L / G is equal to zero or not, if so, your answer is G & L otherwise you have to output -1. Note that in the worst case (a, b) = a and these inequalities always satisfy.
(a, b) --->>> GCD of a & b
[a, b] --->>> LCM of a & b
(a, b) <= a (a, b) <= b [a, b] >= a
[a, b] >= b

UserName - SRM 203 Div 2 - TopCoder

2009-09-06T16:43:00.001+04:30

string

Given a list of existing usernames, we are to determine whether a newly requested username already figures among them. If so, we must append to it the lowest possible number to make a new username.

I first checked whether the requested username exists among them, if not I return it, otherwise I iterate starting at 1 and at each step I convert the number to string and add it to the requested username, then check if it doesn't exist I return it.

In this approach I have to added two functions, 1 - search the vector for a string 2 - convert integer to string.

But another solutions exists, at first I implement a set of string and insert all the vector elements to it, I have a char candidate[1024] too.

I use sprintf( candidate, "%s%d", userName.c_str(), number ), then I don't have to implement two extra functions.

423 - MPI Maelstrom - UVA

2009-09-06T15:38:00.001+04:30

graph algorithms - single source shortest path Dijkstra

In this problem you face a communication system, that in this system messages are sent from station 1 to all other n-1 stations, there are costs to send messages from station 'a' to station 'b' if it's possible to send directly otherwise you have to find a route from station 1 to that station.

Since there are communication costs, sometimes it's better to send a message from station 1 to station 'b' not directly to minimize the cost to send message from station 1 to station 'b'.

In this manner each station will have a minimum time required to receive the message from station 1. This problem wants the maximum of these minimum times.

I use dijkstra to solve this problem. Let me explain what I do in my solution.

I have an adjacency matrix[101][101] and an array MIN[101] and a boolean array mark[101]

I construct adjacency matrix from input.

I initialize MIN[i] = infinity for i = 1 to n and MIN[1] = 0

and initialize mark[i] = false for i = 1 to n

I am going to construct a shortest path tree starting at node 1 using dijkstra. I have a node "current". Initially I set it to 1.

Then I check the adjacency matrix for node current and set

MIN[ neighbor[cur] ] = minimum( MIN[neighbor[cur]], MIN[cur] + adjMAT[cur][i] )

after checking all of the current neighbors I set mark[cur] = true and find a new current. how?

I check all of the nodes and from them that haven't been marked yet and has the minimum distance to node start I pick my next "current" node.

Since the graph is connected and has just one component I iterate through MIN[i] and pick the maximum.

10301 - Rings and Glue - UVA

2009-09-06T14:11:00.001+04:30

graph search algorithm, Depth First Search ( DFS ) or BFS + GEOMETRY

I first construct adjacency matrix then use DFS to split each component and find the maximum.

d = distance between two centers of the rings

rPlusR = radius of ring 'a' + radius of ring 'b'

if( d <> max(R[a], R[b])

then adjMat[a][b] = adjMat[b][a] = true

After constructing the adjacency matrix I easily run DFS on the constructed graph, each time DFS is invoked we have a new component so I count the vertices that are being marked during this DFS call and compare to the maximum.

for(int i = 0; i <>

if( mark[i] == false )

{

vertices = 0;

DFS( i );

if( vertices <>

mx = vertices;

}

I made a mistake in the output.

Note that if maximum is equal to 1 you don't have to print 's' at the end of output.

( thanks Pouria for his hint )

LetterStrings - SRM 202 DIV 2 - TopCoder

2009-09-06T00:00:00.001+04:30

Simulation - string

Just iterate through all the strings in 's' and count the letters.

I used function isalpha( s[i][j] ). Since there are just letters and dashes in the input strings you can use this condition too if( s[i][j] != '-' ) sum ++;

ChessMetric - 2003 TCCC Round 4 - TopCoder

2009-09-05T22:57:00.001+04:30

Dynamic Programming

I solved it in O( size*size*numMoves ). I implement an array DP[101][101][51] and what's the state of this DP problem? DP[i][j][m] means number of ways you can reach cell[i][j] in 'm' moves.

Each cell is reachable ( at most ) from 16 other cells, that means if you want to come to cell[i][j] you can reach it from other 16 cells and you are going to add the number of ways you can reach each of them and the result is number of ways you can reach cell[i][j].

At first I set DP[start[0]][start[1]][0] = 1, that means I can reach cell[start[0]][start[1]] in zero moves in one way. So from m=0 to numMoves if DP[i][j][m] != 0 that means I can reach it from start in m moves, I choose it and update it's neighbors DP[a][b][m+1] += DP[i][j][m]

That means I can go to cell[a][b] from cell[i][j] plus one move m --->>> m+1

DP[i][j][m] = DP[i-1][j-1][m-1] + DP[i-1][j][m-1] + ..... + DP[i+2][j+1][m-1]

Multiples - SRM 201 DIV 2 - TopCoder

2009-09-05T19:33:00.001+04:30

Ad Hoc - math

The simplest solution, which works because the constraints are so low, is best here: loop from min to max and check each number to see if it is devisable by factor.

If you want to get more efficient, you can increment min until you hit a number divisible by factor, decrement max until you hit a number divisible by factor, then subtract min from max, divide factor and add 1. that's it.

AvoidRoads - 2003 TCO Semifinals 4 - TopCoder

2009-09-05T18:54:00.001+04:30

Dynamic Programming

The problem wants to know in how many ways one can reach destination ( cell[width][height] )

If there were no obstacles, then it was a discrete mathematics problem, but now that we have obstacles in the path we have to calculate it in a dynamic programming approach.

What's the 'state' in this problem? ( 'state' a way to describe a situation, a sub-solution for the problem )

dp[i][j] = ( i > 0 ? dp[i-1][j] : 0, j > 0 ? dp[i][j-1] : 0 )

This recurrent relation is true if there are no obstacles in the path, but now what? Since we can come from two cells to the current cell, we have to check whether it is possible to come from cell[i-1][j] to cell[i][j] or from cell[i][j-1] to cell[i][j], each of which is not possible we assume it zero, OK but how do we determine whether it is possible or not? I build a set of pair

and that tells me that you cannot go from pairONE to pairTWO.

No Order Of Operations - SRM 200 DIV 2 - TopCoder

2009-09-05T16:56:00.001+04:30

Ad Hoc - String

Just simulate what problem wants, iterate from left to right and evaluate the expression.

Note that the numbers are just one digit from 0 to 9.

FlowerGarden - 2004 TCCC Round 1 - TopCoder

2009-09-05T16:03:00.001+04:30

Dynamic Programming

I first figure out for each flower how many flowers and which flowers have to go first.

It's not difficult to do that. I implemented arr[50][50] if arr[i][j] is true then flower j must go first before flower i. When arr[i][j] is true??? If height[i] > height[j] && inter( bloom[i], wilt[i], bloom[j], wilt[j] ) then arr[i][j] = true

The function "inter" determines whether the time of bloom and wilt for flower i and j have conflict.

After calculating "arr" I start finding the highest flower that doesn't conflict with others and push it back to the output vector and manipulate "arr" after choosing a flower, I mean if arr[i][chosen] == 1 then arr[i][chosen] = 0 and repeat this procedure n times to choose n flowers.

Hawaiian - 2004 TCCC Round 4 - TopCoder

2009-09-05T01:31:00.001+04:30

Ad Hoc + string

I just implemented what problems described. If you know the function isalpha( ch ),

you know what you have to do, you just need to implement function isHawaiian( ch ) which checks whether a given character is in the Hawaiian alphabet or not. Of course you have to split the words in the input string, you have two ways to do it, do it manually or use stringstream which do it for you.

stringstream ssin;

ssin.str( input );

while( ssin >> word )

check( word ) and push back to the output vector if it's ok

BadNeighbors - 2004 TCCC Round 4 - TopCoder

2009-09-05T01:10:00.001+04:30

Dynamic Programming

For simplicity you can calculate two different sets, one with all elements except the first and the other with all elements except the last one, cause the first and the last element can't be in the desired sequence. So now we have a linear sequence which we want to maximize the sum.

Suppose dp[i] is the maximum sum after checking the elements to position i.

dp[i] = max( element[i]+dp[i-2], element[i-1]+dp[i-3] )

What does it mean? The first (element[i]+dp[i-2]) means it's better to include element 'i' in the set and the second means it's better to include element 'i-1' in the set.

ZigZag - 2003 TCCC Semifinals 3 - TopCoder

2009-09-04T21:25:00.001+04:30

Dynamic Programming - Longest Increasing Subsequence( LIS )

It's something like LIS. You have to manipulate the original algorithm to obtain the answer.

I used a two dimensional array ZIGZAG[60][2] such that ZIGZAG[i][0] is the length of the longest ZigZag sequence ending at sequence[i] and ZIGZAG[i][1] is the sign of the last difference ending at sequence[i].

Suppose we have a sequence like this:

1, 8, 7, 6, 9, 10

ZIGZAG[1][0] = 1, ZIGZAG[1][1] = 0

ZIGZAG[2][0] = 2, ZIGZAG[2][1] = +1

ZIGZAG[3][0] = 3, ZIGZAG[3][1] = -1

ZIGZAG[4][0] = 3, ZIGZAG[4][1] = -1

ZIGZAG[5][0] = 4, ZIGZAG[5][1] = +1

ZIGZAG[6][0] = 4, ZIGZAG[6][1] = +1

I implemented the solution in O( n^2 ), since I have to check n items and for each item I will check n items to choose the appropriate subsequence.

116 - Unidirectional TSP - UVA

2009-09-01T05:28:00.002+04:30

dynamic programming

All you have to do is to find a path that have the minimal weight path.

I first started to construct my table from the first column and in each step I picked the minimum weight till that step that had the minimum row, but that was wrong because if there are several paths, my program might pick the wrong path.

for example ( nimA, one of my friends pointed this test case out )

4 3

2 1 1

2 1 2

1 2 2

my program produced

4 1 1

but the correct answer is

3 2 1

that is lexicographically smaller.

I first construct the last column of my table

dp[i][n] = a[i][n] for all i

then I want to construct the rest of my table, in each cell [i][j] I can go to next column one row upper, same row, or one row lower, I pick the minimum value of them and when I have several minimum I pick the one with minimum row.

for( int j = n-1; j >= 1; j --)

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

in these two loops I fill my table and finally I find my minimum in the first column and print the path.

136 - Ugly Numbers - UVA

2009-08-31T18:44:00.002+04:30

Ad Hoc OR Dynamic Programming

You can pre-calculate calculate the answer by checking all the numbers till you find the 1500'th ugly number by checking each number prim factors to see whether they are just 2, 3 and 5.

You can build a list of ugly numbers in a bottom-up dynamic programming approach. How?

I use a set and a vector of integers for simplicity. Both the set and the vector have the same numbers, I can use just a set too without no vectors.

I must build the list of ugly numbers, since my first ugly number in the list is 1, so the next one must be retrieved by multiplying 2, 3 and 5 by 1 ( the first number in the list ). I pick 2*1 ( the minimum ), then 2 must be multiplied by the next number in the list( 2 ). At next step I choose 3 out of ( 2*2, 3*1, 5*1 ), and 3 must be multiplied by 2( the next number in the list for factor 3 ), then I pick 4 out of ( 2*2, 3*2, 5*1 ) and so on.

2*1 3*1 5*1

2*2 3*2 5*2

2*3 3*3 5*3

2*4 3*4

2*5

2*6

My function min3 is invoked in this order:

2*1, 3*1, 5*1

2*2, 3*1, 5*1

2*2, 3*2, 5*1

2*3, 3*2, 5*1

2*3, 3*2, 5*2

2*4, 3*2, 5*2

2*4, 3*3, 5*2

2*5, 3*3, 5*2

2*5, 3*4, 5*2

2*6, 3*4, 5*2

2*6, 3*4, 5*3

2*8, 3*4, 5*3

2*8, 3*5, 5*3

........

497 - Strategic Defense Initiative - UVA

2009-08-30T13:58:00.001+04:30

dynamic programming - Longest Increasing Subsequence ( LIS ) - O( n^2 )...O( nLOG(n) )

This problem is a classic dynamic programming problem that if you are familiar with the type of the problem, you will solve it in less than 10 minutes.

I use O( nLOG(n) ) implementation of LIS, you can find an implementation of it at

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

762 - We Ship Cheap - UVA

2009-08-30T01:30:00.001+04:30

graph search algorithm - single source shortest path - BFS

The problem takes as input the description of a city (graph) and prints the shortest path from source city to destination city.

The challenging part of this problem is that how you want to represent the graph?

Since there are just 26*26 distinct city names you can use adjacency matrix too, but I use adjacency list by using a map of "string" to "vector". I also use a map of "string" to "string" to save the precedence (father) node of another node, so I can print the path easily, and I use a set of "string" to mark nodes that I have visited recently.

And the rest and main part of the problem is to find the shortest path from source city to destination city that I do it using a queue of "string".

10102 - The path in the colored field - UVA

2009-08-28T19:24:00.001+04:30

graph search algorithm - BFS OR Ad Hoc

At first I was confused by the problem description, and I thought that the sample output doesn't match the sample input. The problem wants to know that if you are standing in a cell occupied with digit '1', at most how many steps does it take to get to a cell (just one) occupied with digit 3.
So first I find the minimum distance from each '1' to each '3' and take the minimum of these values, then I just iterate through the minimum values I took for each '1' and print the maximum one.
To find the minimum distance from each '1' to each '3' you can run a BFS from that '1' and then pick the minimum of the distances from the '1', but I don't suggest to do that, because in grids BFS is used when you have some special adjacency for cells or you have some obstacles in the path between two cells, but here you can easily calculate the minimum distance between two cells.
the Distance from cell A to cell B = abs( A.x-B.x ) + abs( A.y-B.y )
This is true if you are allowed to move one cell up, down, left or right, but not diagonally.

11448 - Who said crisis? - UVA

2009-08-27T03:49:00.001+04:30

big integer - subtraction

The problem wants you just to subtract two positive integers that can be up to 10000 ( I think ) digits.
If you have a big integer library, that's a simple work, otherwise you have to implement subtraction yourself, as I did.

11474 - Dying Tree - UVA

2009-08-27T02:22:00.001+04:30

graph search algorithm - DFS( Depth-First Search )

The problem wants to know whether there is a tree to call a doctor to save the sick tree or not?
This tree can also be the sick tree.
I first construct an adjacency matrix from the trees,( excluding doctors ), HOW? Two trees can talk to each other if the minimum distance between them is less than or equal to k. Then I run DFS from node 1, in the DFS function I check whether there is a doctor to whom the current tree in the DFS function can communicate? HOW? An ordinary tree can communicate to a doctor if the minimum distance between them is less than or equal to d. I have a global boolean variable for checking the answer. If in DFS function I find a connection between a tree and a doctor I set it to true and return, otherwise I continue searching from the adjacent trees to the current tree( adjacency matrix ).

10793 - The Orc Attack - UVA

2009-08-26T13:02:00.001+04:30

graph algorithms - all pairs shortest paths - floyd warshall

Another shortest path problem. As you can see in the problem description you have to find the minimum distance from locations 1-5 to all other locations other than 1-5. Then you have to pick the candidates, which are equidistant from these 5 locations. That location must be reachable from all the locations in the graph. If such a location exist, then pick the one which has the minimum farthest distance, that means this location( rally point ) is reachable from all other locations and has a minimum distance to all of them, there is a location that has the maximum minimum ( :-D ) distance from rally point, you have to pick a rally point that this value for that is minimum( distance to the farthest location ).
I simply construct the graph from input, run floyd-warshall on it, and the rest of the problem that has described and I just simulate it.

291 - The House Of Santa Claus - UVA

2009-08-26T02:14:00.001+04:30

backtracking

Another backtracking problem. As you can see in the problem description you are not allowed to pass each edge twice. ( Euler tour in lexicographical order )
I make an adjacency matrix, and a boolean matrix for marking the edges I have visited till now.
int mat[6][6];
bool mark[6][6];

Then I start backtracking from node 1 and each time checking whether to continue from current node or not I check ( mark[cur][i] == false && mat[cur][i] == 1 ) and then mark this edge to true and keep on backtracking. I have a variable d which denotes the depth of the backtracking whenever it reaches 9 I completely print the tour I have saved.

10171 - Meeting Prof. Miguel - UVA

2009-08-26T01:16:00.001+04:30

graph algorithms - all pairs shortest path - floyd warshall

This is a double all pairs shortest path problem. As you see in the problem description you are facing two distinct graphs which at most each one has 26 nodes( upper case letters ), one of them is for Manzoor and the other is for Prof. Miguel.
I first construct two graphs and initialize the adjacency matrices to 100000, then read input and finally run floyd warshall one both of them, and find the minimum cost, how? The places which both of them can go, I add the cost for both of them and find the minimum of these.
Don't forget if there are several places with minimum cost, print them in lexicographical order like this.
10 A G N
Be careful about zero costs, the problem has pointed that the costs are non-negative integers, so it can be zero.
My program first got WA because of this test case.

input :
2
Y U B D 0
M U B D 0
B B

output :
0 B D

because first I checked if they are in the same place and separated this test case from the others.
0 B

10637 - Coprimes - UVA

2009-08-25T22:47:00.001+04:30

backtracking

As the problem says, you should print all possible partitions of S into t co-prime numbers.
The order doesn't matter, so If you have to choose 1 & 2 & 5, you just need to print 1 2 5 not 5 2 1 or 2 5 1. This fact prunes backtracking and helped me pass time limit.
I implemented a function called solve( start, m, d ). In this function I start checking from start, and each time I find a number that is coprime to the selected items, I put it in the list and keep on backtracking with ( number, m-number, d+1 ), when the function reaches at ( d == numberOfPartitions ) and m is equal to zero( that means there are no values to choose and the partitioning is complete ), I completely print the selected list.

10422 - Knights in FEN - UVA

2009-08-25T20:17:00.001+04:30

backtracking

This problem gives you a 5x5 chess board with 24 knights ( 12 of them are white and the other 12 are black ) and wants you to turn the board to the initial board that is described in the problem with minimum moves.
I think there are better approaches, because in the rank list the first 20 have solved this problem with time 0.000, but if you implement a careful backtracking you will pass time limit.
Since the depth is just 10, backtracking is sufficient.
I just replaced the empty cell with every possible replacement, except the cell that in previous move was empty.

for(int p = 0; p < 8; p ++) // 8 directions to move from space { // x & y are the previous cell that was empty i = x+dir[p][0]; j = y+dir[p][1]; if( i >= 0 && j >= 0 && i < 5 && j < 5 && ( i != a || j != b ) )
{
swap( input[i][j], input[x][y] );
solve( d+1, x, y );
swap( input[i][j], input[x][y] );
}
}

If the problem is solvable in less than 11 moves, maybe it's possible to solve it in several paths, so each time the puzzle was solved, I saved the length of the shortest path.

11569 - Lovely Hint - UVA

2009-08-25T02:01:00.001+04:30

backtracking

The problem wants you to count all the strings that you can construct under the restriction in the problem and print the length of the longest and the ways you can achieve that length.

Simply I start backtracking from all the characters and in the function you just backtrack with the characters that can be placed next to the current character under the restriction.
Each time I invoke the function for a character, I mark it, then I just pick it once.
Be careful! Don't invoke the function for 'L' in "HELLO" twice.

if( line[i] != line[i-1] && !mark[i] && 5 * (line[cur]-'A'+1) <= 4 * (line[i]-'A'+1) )
{
mark[i] = true;
solve( i, d+1 );
mark[i] = false;
}

I sort the input string, something like this is the main condition in the function.
'i' is the current character I'm checking, 'd' is the length of the string I've made till now.

length[d ++]
This array tracks how many strings up to 'd' characters I can construct.
At last I find the maximum length and print length[maximum_length].

775 - Hamiltonian Cycle - UVA

2009-08-24T23:51:00.002+04:30

backtracking - graph representation - finding the hamiltonian path

The problem gives you the adjacency matrix and wants you to find the hamiltonian path.
First, since the graph is dense the hamiltonian path exists( I think so ), so for all test cases you have an answer to this problem, and since the order is not important your path can start from node 1 and end at node 1.
What you have to do is to construct just a path from node 1 that ends up in a node which is adjacent to node 1, so you can print the path at that time.
I use a 2-dimensional array for adjacency matrix, a boolean array for marking nodes, because each node can be traversed once except node 1 which is the start and the end of the path, and an array of integers for saving the order of the nodes I'm visiting.
I start backtracking from node 1 and each time in the function I check whether there exist another node which is not visited and continue backtracking with this node.
As backtracking goes on, sometime I find out that I have visited all nodes once and that's the time I print the path and that's it.

423 - MPI Maelstram - UVA

2009-08-24T23:20:00.002+04:30

graph algorithms - all pairs shortest path - floyd warshall O( n^3)

In a system they want to send a message from a source called station 1 to all other n-1 stations.
What question want is the minimum time to do that, so we have to find the minimum time from station 1 to all other stations and then find the maximum between these minimum times and that's the longest time in which all the other stations have gotten the message.
We don't have to send a message directly because of the expensive costs and so we can use intermediate stations to convey the message from station 1 to station k for example.
'n' is not so large so I used floyd-warshall to do this.