JOIN
 Match Editorial
SRM 352
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.

This SRM seemed more difficult than the last few challenges. Division I participants easily rushed through the easy, but only 24 of them were able to successfully pass the medium, though many tried. There were less then 20 coders who opened the Hard and they were faced with a ferocious problem, with only Petr solving it correctly. As a result of two above-average problems a lot of high-rated coders, and even a few targets, took very low places.

This SRM became a good start for two newcomers who were able to take two of the three top spots in Division II. Moreover both gained yellow color and moved to Division I. falsifian, a newcomer from the United States wins, At_the_Summit finished second and programdigest from India is third.

# The Problems

AttendanceShort
Used as: Division Two - Level One:
 Value 250 Submission Rate 649 / 702 (92.45%) Success Rate 546 / 649 (84.13%) High Score Petrs for 248.31 points (2 mins 20 secs) Average Score 199.10 (for 546 correct submissions)

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.

Note, in this problem you can safely use float point arithmetic because 75% has only power of two in divisor. Change it with, for example, 80%, and number of accepted solutions will decrease in half.

You can use falsifian's C++ solution as a reference:

```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:
 Value 500 Submission Rate 608 / 702 (86.61%) Success Rate 521 / 608 (85.69%) High Score programdigest for 493.93 points (3 mins 9 secs) Average Score 400.11 (for 521 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 571 / 576 (99.13%) Success Rate 560 / 571 (98.07%) High Score JongMan for 249.03 points (1 mins 46 secs) Average Score 231.78 (for 560 correct submissions)

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.

Let F[i][0] and F[i][1] be the number of times '0' and '1', respectively, will be printed during a fibonacci(i) call. Then

• F[0][0] = 1; F[0][1] = 0;
• F[1][0] = 0; F[1][1] = 1;
• For i greater than 1: F[i][0] = F[i-1][0] + F[i-2][0]; F[i][1] = F[i-1][1] + F[i-2][1];
The answer is F[n][0] and F[n][1]. F values can be calculated either by forward dynamic programming (calculate F[i] using known F[i-1] and F[i-2]) or by lazy evaluations with memorization (do not calculate F[i] in recursive function if it was calculated before, just take it from the cache). Here is JongMan's code which uses the second (lazy evaluations) approach:
```  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(n-1);
vector<int> b = fiboCallsMade(n-2);
ret[0] = a[0] + b[0];
ret[1] = a[1] + b[1];
}
return ret;
}
```

RaceManagement
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 149 / 702 (21.23%) Success Rate 44 / 149 (29.53%) High Score falsifian for 758.58 points (17 mins 13 secs) Average Score 498.00 (for 44 correct submissions)

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 i-th horse wins outright and W[i] be the earnings of the company in case that i-th horse wins outright. The fact that the i-th 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 i-th horse and (100%-probability[j]) for all other horses. The value W[i] equals to (S - amounts[i]) - amounts[i]* payload_factor.

Therefore, the expected company's earnings can be calculated by the following formula:

`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:
 Value 500 Submission Rate 188 / 576 (32.64%) Success Rate 24 / 188 (12.77%) High Score bmerry for 373.23 points (12 mins 34 secs) Average Score 242.88 (for 24 correct submissions)

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.

Let's represent the C value into the Fibonaccimal system (it is also called as Zeckendorf Representation). This action gives us the array C0, C1, ..., CM where each Ci represents how many Fibonacci numbers Fi we have (initially 0 or 1). Let's consider the maximal Ci that is greater than 0. We can take from 0 to Ci items with the weight Fi. If we take less than Ci such items, we transform the remaining Fibonacci numbers into Ci-1 and Ci-2.

More formally, let's A[i][Ci][Ci-1] be a maximal cost that could be taken by items with weight greater than Fi in such way, that all Cj with j > i are equal to zero, Ci and Ci-1 have corresponding values and all Cj with j < i - 1 remain as in the initial Zeckendorf Representation. Choosing how many items with weight equal to Fi are taken, we can update next values of the A.

Note, that if Ci is not less than number of remained items, we can easily take all of them. This optimization gives no more than M*N*N (M - index of largest Fibonacci number in C's Zeckendorf Representation, N - number of items) distinct indexes for the array A.

This wandering around Zeckendorf Representation and many-dimensional dynamic programming is, of course, very interesting, but, in fact, is not necessary at all. You can take a look at halyavin's solution. He has implemented simple memorization with the optimization that if we have enough space to take all remained items we should get them all. Our preceding matting shows that this solution will be fast enough as well.

PaperRacing
Used as: Division One - Level Three:
 Value 1000 Submission Rate 18 / 576 (3.12%) Success Rate 1 / 18 (5.56%) High Score Petr for 661.83 points (22 mins 56 secs) Average Score 661.83 (for 1 correct submission)

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 Breadth-first search algorithm to find the shortest path to the finish.

The most tricky part of this problem is to check if a move is possible or not. This part can be solved using Bresenham's line algorithm. Look at Petr's perfect realization of it.

By Andrew_Lazarev
TopCoder Member