So, today we had a new test SRM in TopCoder. This time testing the g++ 4.8.1 compiler and a python upgrade too. g++ 4.8.1 has some amazing features over 4.4. So I really wanted to use them in this test. (Disclaimer: I am actually just learning c++11)
Div1 hard
It was a dynamic programming problem. I solved this one before, and though I avoided looking at the past solution, the idea was still evident. This problem is such a standard dynamic programming problem that I don't think we would be able to use it in division 1 as a medium anymore. It was a division 1 hard back in its day...
Was sad because I couldn't find an excuse to put any of the new features.
Div1 Medium: FlightScheduler
The maximum distance a plane can travel given an initial mass of fuel `f` is: `R = K ln( (m + f - t) / m )` where:
- `K` is a constant for the plane (efficiency)
- `m` is the plane's mass.
- `t` is the mass of fuel spent during take off, so the initial amount of fuel has to be at least this.
(Special effort was put to make the problem statement as unclear as possible. I initially didn't know that the take off amount wasn't included in the first formula that appears in the problem statement. This really delayed me).
Anyway, so knowing that, we need to minimize the amount of fuel needed to travel `D` distance units. We are allowed to land at any intermediary point, recharge fuel and take off.
Equal distances
The first thing to know is that if we make `(n-1)` stops, so that the plane takes off `n` times in total, it is always better to cover the same distance in each of the sub-trips. So we should move `D / n` units in each of them.
The independent variable that determines the final fuel cost is then just `n`. We need to find the best value of `n` for this.
Ternary search
So, let us say we make one flight. In this case, the amount of fuel needed for a single round might be too large (Note that the formula for R is logarithmic in the mass of fuel, so increasing the amount of fuel by a large amount will not increase the distance that much).
If we instead do a lot of flights, it is also not very good, because each flight needs at least `t` fuel.
There is a value of `n` that will yield a minimum value for `f(n)`, the total fuel cost. For `(x < n)` and `(y > n)`, we can guess that: `(f(x) > n)` and (f(y) > n). Also, the more we move away from `n`, the worse the result. This is all ternary search-friendly. Let us do it.
f(n)
So let us just find `f(n)`, the minimum fuel cost needed to travel `D` distance units using `n` trips. Let `(d = D / n)` , this is the distance per trip. What is the minimum fuel cost to travel `d` distance units? We need the following to be true::
Let us solve the inequality.
`(m + f - t) / m >= e ^(d / K)`
`m + f - t >= me ^(d / K)`
`f >= me ^(d / K) - m + t`
`f >= m(e ^(d / K) - 1) + t`
So that is the lower bound for f.
Implementing ternary search
So, I really wanted to use the new c++ features. You know what is funny about ternary search? You need to implement the function f. You know what is lame about solving TC problems using multiple functions? TURNING ARGUMENTS INTO CLASS MEMBERS. It is so tedious to copy variables manually just so a new function can use them in their scope. OOP is truly the worst idea ever. Anyway. It occurred to me... I can use a closure! This way when I create the function f() I will do it inside the scope of the main method, so no need to copy arguments manually.
The result is beautiful:
double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel)
{
// so we use closure syntax. The [=] means
// that any variable like "emptyMass"
// that is referenced inside the anonymous function (lambda) will be
// automatically copied, so when we call f() it will use copies just fine.
auto f = [=](long n)->double {
double d = distance * (1.0 / n);
return n * ( takeoffFuel + emptyMass * (exp(d/K) - 1.0) );
};
long lo = 1, hi = 40000100000L;
while (lo + 2 < hi) {
long ha1 = (lo*2 + hi) / 3, ha2 = (lo + hi*2) / 3;
if ( f(ha1) < f(ha2) ) {
hi = ha2;
} else {
lo = ha1;
}
}
// the minimum is one of f(lo), f(lo+1) or hi = f(lo+2):
vector<double> res = { f(lo), f(lo+1), f(lo+2) };
return *min_element(res.begin(), res.end());
}
It turns out that I had to go out in the middle of the match , so I didn't have much time to finish this problem correctly. When I came back, there were few minutes left of coding phase. I tried to debug, I found the bug (The issue with problem statement I mentioned above). But it was still wrong. Eventually, when there were only 5 minutes left, I gave up trying to find the bug and moved on to 250. It turns out that my bug was that I did: d = distance / n. Both distance and n were integers, so it was doing integer division....
Div1 Easy
An implementation problem, I didn't have much time to finish it.
And more
It turns out that lambdas and closures are awesome. There is plenty of more in regards to this new functional c++.
After the match, I figured, that I could actually make myself a TernarySearch library (template) function that does the whole TernarySearch for me and can be used in any situation.
// D: function domain
// R: function range , so f: D -> R
// Yep, std::function is useful:
template<class D, class R> R TernarySearch(D lo, D hi, std::function<R(D)> f) {
while (lo + 2 < hi) {
D ha1 = (lo*2 + hi) / 3, ha2 = (lo + hi*2) / 3;
if ( f(ha1) < f(ha2) ) {
hi = ha2;
} else {
lo = ha1;
}
}
vector<R> res = { f(lo), f(lo+1), f(lo+2) };
return *min_element(res.begin(), res.end());
}
So, if I wanted to use this function to solve today's problem:
double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel)
{
return TernarySearch<long, double>(1, 40000100000L, [=](long n){
double d = distance * (1.0 / n);
return n * ( takeoffFuel + emptyMass * (exp(d/K) - 1.0) );
});
}
Or maybe you prefer the following version:
double minimizeFuel(int D, int K, int m, int t)
{
std::function<double(long)> f = [=](long n){
return n*( t + m * (exp(D / (1.0*n*K)) - 1) );
};
return TernarySearch(1L, 40000100000L, f);
}
Comments?
What do you think of g++ 4.8.1 so far? Worthwhile upgrade?
0 comments:
Post a Comment