Saturday, June 2, 2007 Match summary
Petr continues his dominance, winning for the 3rd time out of the past three challenges.
After his third win he has also gained a new TopCoder rating record  3744! Congratulations!
bmerry took the second place. He submitted Medium and Hard problems in about 12 minutes. However, as it is often the case, quick code is not always good code, and he had to resubmit them both. Chmel_Tolstiy finished third with two problems and four successful challenges.
The ProblemsAttendanceShortUsed as: Division Two  Level One:
The problem was pretty straightforward. To solve it we need to check if each student meets the attendance requirements or not. A student doesn't meet the requirements if and only if the number of 'P' characters in his attendance string is less than 75% of the total amount of 'P' and 'A' characters altogether.
vector<string> shortList(vector<string> names, vector<string> attendance) { vector<string> ret; for (int i = 0; i < names.size(); i ++) { int present = 0, total = 0; for (int j = 0; j < attendance[i].size(); j ++) { switch(attendance[i][j]) { case 'P': present ++; case 'A': total ++; default: break; } } if (present * 4 < total * 3) ret.push_back(names[i]); } return ret; }NumberofFiboCalls Used as: Division Two  Level Two: Used as: Division One  Level One:
Usually a Fibonacci numbers example is used in computer science lectures to illustrate the principles of dynamic programming. Exponentially slow algorithms become sufficiently fast by inserting a few lines of code. In this problem we should do the same with two element vectors instead of numbers.
vector<int> cache[41]; vector <int> fiboCallsMade(int n) { if(cache[n].size()) return cache[n]; vector<int>& ret = cache[n]; ret.resize(2); if(n == 0) ret[0] = 1; else if(n == 1) ret[1] = 1; else { vector<int> a = fiboCallsMade(n1); vector<int> b = fiboCallsMade(n2); ret[0] = a[0] + b[0]; ret[1] = a[1] + b[1]; } return ret; }RaceManagement Used as: Division Two  Level Three:
First we will calculate the expected earnings of the company.
The company can lose money if some horse wins outright, and it can earn money in all
other cases. Let S be the sum of all amounts, P[i] be the probability that
the ith horse wins outright and W[i] be the earnings of the company in case that ith
horse wins outright. The fact that the ith horse wins the race outright means that this
horse wins and all others lose. So, the probability P[i] equals to the product
of shares of all horses: probability[i] for the ith horse and (100%probability[j]) for all other horses. The value W[i] equals to (S  amounts[i])  amounts[i]* payload_factor.
expected_earnings = (100%  sum(all P[i]))*S  sum(all products P[i]*W[i])To solve the problem we should solve the inequality "expected_earnings ≥ minimumMoney" with the only unknown variable  payload_factor. Note that in this problem the maximal number of horses is 5. This fact allows us to write the solution without using a double type and to avoid precision issues. Here is Java sample code without using float point operations: public double getPayoutFactor(int[] probability, int[] amounts, int minimumMoney) { long sum = 0; for (int amount : amounts) { sum += amount; } long minm = minimumMoney; //long type variable for minimumMoney long p=1; for (int amount : amounts) { p*=100; minm *= 100; } long win = 0; long payloadFactor = 0; for(int i=0; i<amounts.length; i++) { long cur = 1; for(int j = 0; j<amounts.length; j++) cur *= i == j? probability[j] : 100  probability[j]; payloadFactor += cur * amounts[i]; win += (sum  amounts[i]) * cur; p= cur; } win += sum * p; if (payloadFactor == 0) { if (win  minm >=0) return 2; else return 1; } if (win  minm < 0) return 1; return (double)(win  minm) / payloadFactor; }FibonacciKnapsack Used as: Division One  Level Two:
The key to this problem is the fact that the weight of the item can take
on only a few distinct values. And it is important that these values
increase exponentially. This condition allows us to put
forward the bold idea: "If we dismiss an item with a big weight the
released space can hold a lot of smaller items." This idea is not a
strict proof of a solution but it is good enough to understand the main process.
Used as: Division One  Level Three:
This problem is not very hard theoretically but most of the coders who tried to solve
it were confronted with difficulties in realizing the theoretical solution. It is quite obvious that the car is represented by four parameters  its coordinates and its speed.
So, it is possible to build the graph where vertices are the car states and edges are the possible moves.
After that we just need to run Breadthfirst search algorithm to find the shortest path to the finish.

