Match Editorial

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

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

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)

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

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

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])

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

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 C₀, C₁, ..., C_M where each C_i represents how many Fibonacci numbers F_i we have (initially 0 or 1). Let's consider the maximal C_i that is greater than 0. We can take from 0 to C_i items with the weight F_i. If we take less than C_i such items, we transform the remaining Fibonacci numbers into C_i-1 and C_i-2.

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

Note, that if C_i 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.

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.