TopCoder - SRM 146 DIV 1 - RectangularGrid - countRectangles

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

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

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

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

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

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