Note 1: Know your STL.
You can find the following in my code for div1 600:
// If you know a better way to append a 0 to the beginning of
// this, I am listening...
reverse(districts.begin(), districts.end());
districts.push_back(0);
reverse(districts.begin(), districts.end());
I knew I had to insert a 0 to the beginning of the vector<int> but I could not think of a quick STL way to do it. I was later able to find it, the (actually intuitive for a STL feature):
districts.insert(districts.begin(), 0);
It is a little strange it needs an iterator when it is a non-static method. As always with the STL you will type the same thing more times than needed.
Note 2: Don't code, think!
At one point of the code, you need to get the time to move from a district i to j using no cars and also to calculate the time using each of the available cars. Coding this is actually where I spent most of the 58 minutes I used to solve this problem. The reason is that I, for some reason decided to use a Bellman-Ford (instead of Dijkstra) that starts at district i, may decide to pick the car (if it exists) and then goes to district j. In total it is
a complicated minimum path problem in which the state has two dimensions for its vertices (district, are we inside car?) and thus the transitions are also complicated to code. After using the car, the cost uses the inverse drive velocity instead of the walk velocity.
The one blunder here was to rush into coding that Bellman-Ford. It was better to just stop for a second, and note that you can multiply inverseWalkSpeed or inverseDriveSpeed after the minimum distance is calculated instead of during. What this means is that if you
just had precoded a dist[x][y] matrix that yielded the minimum distance between districts x and y. Then the minimum time without using a car is:
dist[x][y]*inverseWalkSpeed and the time using a certain car z that is in district c is simply: (dist[x][c]*inverseWalkSpeed + dist[c][y]*inverseDriveSpeed). This helps because the dist array is very easy to generate by using Floyd-Warshall on the original road cost matrix (the one in the input).
A similar issue is with the max flow part. In my original analysis, I first calculate the total cost without using cars, and then I make a max-benefit matching to maximize the reductions in cost (for each pair (transition, car) calculate the reduction in cost between not using any car and that option). Max benefit is the same as min cost when the cost is negative, and although it is possible to do that in min cost max flow, the implementation is harder (you need Bellman-Ford instead of Dijkstra for the first iteration, then stick to slow Bellman-Ford or do a trick with "potentials" to use Dijkstra. The min-cost-max-flow algorithm can be done much simpler without negative costs.
Instead of diving into negative costs that quickly, I could have tried to get rid of the negative part. Which is perfectly possible. Just include the cost to use no car and the costs to use each car in the network. Not using any car should have infinite capacity, alternatively, just connect each transition directly to the sink with capacity 1 and cost = cost of normal travel. Either way, what follows is what my code could have been if I stopped to improve the analysis of the problem instead of just starting to type quickly:
int travel(vector <int> cars, vector <int> districts, vector <string> roads,
int inverseWalkSpeed, int inverseDriveSpeed)
{
t = roads.size();
iws = inverseWalkSpeed;
ids = inverseDriveSpeed;
this->roads = roads;
districts.insert(districts.begin(),0);
int n = districts.size()-1;
int m = cars.size();
// Floyd-Marshall to get the minimum distances.
int dist[t][t];
for (int i=0; i<t; i++) {
for (int j=0; j<t; j++) {
dist[i][j] = roadCost(i,j);
}
}
for (int k=t; k--;) {
for (int i=t; i--;) {
for (int j=t; j--;) {
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j] );
}
}
}
network * G = new network;
for (int i=0; i<n+m; i++) {
G->addVertex();
}
G->sink = G->addVertex();
G->source = G->addVertex();
for (int i=0; i<n; i++) {
int u = districts[i], v = districts[i+1];
G->addEdge(G->source, i, 1, 0);
for (int j=0; j<m; j++) {
//Time to travel from u to v using car j:
int costUsingCar = dist[u][cars[j]]*iws + dist[cars[j]][v]*ids;
G->addEdge(i, j+n, 1, costUsingCar );
}
//Time to travel from u to v not using any car:
G->addEdge(i, G->sink, 1, dist[u][v]*iws );
}
for (int j=0; j<m; j++) {
G->addEdge(j+n, G->sink, 1, 0);
}
int flow; long long cost;
G->minCostMaxFlow(flow, cost);
delete G;
assert(flow == n);
return (int)(cost);
}
It is a lot more concise than what I submitted during the match.
Mantain your own code library.
I had to use min-cost max flow to solve this problem. It is a particularly complicated algorithm and for that reason I use a library code. Unfortunately, It seems had not updated nor used that code in years. It seems that the last few years I have only used min-cost-max-flow in editorials and problems of my own, and that means Java. I could not have used my Java implementation either because I needed negative costs (thanks poor analysis!). So, I used the c++ code I've written before.
The horror. It seems that back when I wrote that code, I was a lot less concise, and also liked code hacks like avoiding the use of {} brackets when not necessary (That is silly, they are ALWAYS necessary, else it will take you more time to update the code after you want to add lines to your if-then-else that only used one line... =) . Worse, it was particularly abusive of the >? <? g++ extensions (Very useful min and max operators, that were removed from more modern versions of g++). So I could not compile the code locally. After thinking that I should not waste time redoing such code, and remember that the VERY OLD g++ version in Topcoder's server does support those g++ extensions. I decided to switch to manual compilation and tests using the compile and test button from the arena. But that turned out to be very slow, specially because I had to correct some syntax errors when building the network.
Focus, please focus
I finally implemented the min-cost max flow. And the sweetest thing happened. All results were wrong. I was getting 44 instead of 36. I knew that the normal cost without using any car is 40, so the min cost flow should have returned -4. So, what happened? I came to conclude that, unlike what I remembered about my precoded min cost flow solution, it did not support negative numbers. Panic. So, what was I supposed to do. I needed negative costs (I thought I did, but it turns out it was not true) and I had no min cost flow implementation that solves it.
Then I remembered that I had a Hungarian algorithm code lying around, since I was doing min-cost Bipartite matching, that was actually a useful thing. The problem is that my Hungarian algorithm code was much older and I did not remember how to use it... I was in the process of analyzing it, when I noticed something funny...
When I was coding the thing that uses min-cost max flow. I was multiply the costs by -1, because that is what you do. But then, the returned cost would be -BENEFIT. But I was doing MaxBonus = result of cost flow. And finally (total - result). Do you see it? I was multiplying by -1 twice.
I tried, I really tried to restore the solution to when the min-cost-max-flow algorithm was implemented. But Kawigi Edit's undo limit turned out to be smaller than I needed. I had to reimplement min-cost-max-flow, again, and also using manual compilation and examples because local tester did not work, again.
Mantain your code library, really
It also does not hurt if you left some documentation comments regarding how to actually use your code. Just because you wrote it, it does not mean you won't forget how to use it after 5 years. You should also practice more and make sure to keep your library code clean and to practice using it. After changing your local compiler's version, make sure your personal library of code for contest actually compiles with it.
It does not hurt to try to simplify and minimize the size of your pre-made code. Because when you actually get to use it, and it makes your code look like a Behemoth, it is very embarassing.
Rule #1, again
Smaller issue, I had a failed challenge, which as you may remember from very old blog posts, breaks my topcoder rule #1. Do not challenge. (Rule #2 is DO NOT challenge). The solution I challenged was correct, for some reason It seemed wrong to me. I even tried it mentally and thought that the case I provided would make it case, that was not true. This was a unnecessary risk, if I failed any of my solutions to the problems, I would have gotten a very bad score because of this failed challenge.
0 comments:
Post a Comment