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