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.