## TopCoder SRM 144 Lottery Published on: 22 Sep 2010

• Used As : Division I Level Two

### Math:

Reading the problem statement it should be clear that generating all the possible lottery numbers and then verifying them is not an option. The most important thing is realizing that the question is in fact just asking you to find combinations and permutations with and without repetitions. Equipped with the formulas, all that remains is parsing and final sorting of the results. Let's abstract away the fact that we need to do it for a vector. If we can calculate the odds for one string, then we can loop through and calculate the odds for n number of strings. So lets concentrate on calculating the odds for just one string

### Parsing:

We can use the istringstream class to easily allow us to parse the string.

istringstream in(rule);
getline(in,szName, ':');
in>>nChoices>>nBlanks>>cSorted>>cUnique;



c++

Yes its as simple as that! Now on to calculating the Odds.

### Calculating Odds:

The key thing to note here is that we need to be using unsigned long long as the type since the numbers can get pretty big. We also don't want to generate all the factorials and then divide, so we write two simple functions

• unsigned long long factorialDivide(int num, int den) - This returns the results of num!/ div!
• unsigned long long factorial(int num) - This just returns num!
//Unique Permutations: n!/(n -r)!
if(cUnique == 'T' && cSorted=='F'){
return make_pair(factorialDivide(nChoices, nChoices - nBlanks),szName);
}

//Non-Unique Permutations n ^ r
else if(cUnique == 'F'  && cSorted == 'F'){
return make_pair(pow(nChoices, nBlanks), szName);
}

//Unique Combinations: n! / r! (n-r)!
else if(cUnique=='T' && cSorted=='T'){
unsigned long long temp = factorialDivide(nChoices, nChoices - nBlanks);
return make_pair(temp / factorial(nBlanks), szName);
}

//Non-Unique Combinations: (n+r-1)! / r! (n-1)!
else if(cUnique=='F' && cSorted=='T'){
unsigned long long temp = factorialDivide(nChoices + nBlanks - 1, nChoices - 1);
return make_pair(temp / factorial(nBlanks), szName);
}



c++

### Doing it for 'n' strings:

This is the part where STL shines ! We will use the STL transform function to do this in one line.

typedef std::pair LotteryOdds<unsigned long long, string>;
vector results <LotteryOdds>;
transform(rules.begin(),rules.end(),
inserter(results,results.begin()),Lottery::getOdds);



c++

The transform function runs every 'rule' through the getOdds function which returns the LotteryOdds pairs. We store this in a vector.

### Sorting:

Now that we have all the results, we need to sort them. This is a little tricky since we can have equal odds. We can utilize the STL sort but we wil need to provide our own comparator function.

 struct LotteryOddsCompare{
bool operator()(const LotteryOdds& left, const LotteryOdds& right)
if(left.first == right.first)  // equal odds then compare names
return left.second < right.second;
else
return left.first < right.first;
}
};

sort(results.begin(), results.end(), LotteryOddsCompare());



c++

Thats it. We have the sorted odds in the results vector!

New herbs/comments/suggestions/shout-out/tweets for the problem appreciated !