TopCoder - SRM 178 DIV 1 - MiniPaint - leastBad

Link to the problem statement

First of all it must be clear that having a fixed number of strokes for each row, the problem can be solved independently for each row, so on a top level we have to decide how many strokes to assign to each row and tell them to solve themselves (paint themselves) and then we choose the best combination. So in order to solve the assignment problem we use dynamic programming.
 
    int g(int row, int strokes)

This is the state of our outer DP, which tells if we have to solve rows in range [0...row] and only have strokes number of strokes left, what would be the minimum number of mispainted cells? So we can assign 0, 1, 2, ..., width assigns to the current row and solve g(row-1, strokes-k) which k is the number of strokes that we have assigned to the current row, in this case what would be the number of mispainted cells for this row? f(row, length-1, k) but what this means?

     int f(int row, int idx, int strokes)

This is the state of our inner DP, which means we want to paint row of the picture in range [0...idx] and only have strokes number of strokes left. There are two options for us, first not paint cell at (row, idx), which means cost off(row, idx-1, strokes-1) + 1, or paint cells in range [k...idx] with cost of f(row, k-1, strokes-1) + numberOfCellsDifferent to cell at (row, idx).

Think about base cases yourself. (e.g. where row is -1 or strokes is equal to zero)

TopCoder - SRM 144 DIV 1 - Lottery - sortByOdds

 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

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

UserName - SRM 203 Div 2 - TopCoder

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.

LetterStrings - SRM 202 DIV 2 - TopCoder

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

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

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

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

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

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

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

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

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.