I am not excessively sure about my problems B and C. They seemed very correct when I coded them though. I just passed A. Let us see if results for my B and C come before I finish explaining A.
Div1 A / Div2 C
So, constraints are large. So, let us try to think of a linear algorithm.
No matter what we do, our only allowed move is to remove last element and place it somewhere else. In fact, the only decision to make is the number of times we will repeat this step.
Let us focus on the number of times we do the step. So, for the first example:
3 2 1 1 2 3
And we repeat the step twice, then we will remove the first two numbers (2 1) and after that, we can just assume we put the two numbers in the best places imaginable. In this, case, (1 2) 3.
The other two examples:
1 2 3 4 5 1 5 2 3 4 1 5 2 3 4 1 2 3 4 5
In the first of them, we remove 5 and only five, after that, we can find a good spot for 5 and we will be ready. In the other case, we remove (2 3 4) , and it is enough.
Let us focus on why is it enough to do these things. Let us say we are just ignoring the removed numbers. The examples look like this after ignoring the numbers we removed:
3 3 1 2 3 4 1 2 3 4 1 5 1 5
So, after removing the last X numbers from the first permutation, the numbers in both permutations must have the same order.
The solution is then to find the maximum Y, such that the first Y numbers of the first permutation are in the same order as they appear in the second permutation. This can be done linearly by using two pointers as the following code:
int solve(int n, int*p1, int*p2)
{
int x = 0;
int y = 0;
while (x < n) {
while ( (y < n) && (p1[x] != p2[y]) ) {
y++;
}
if (y >= n) {
break;
}
x++;
}
return n-x;
}
Div1 B / Div2 D
So, as I finish writing the explanation for A, I learn that I passed B. All great.
I had issues at first because it seemed like most approaches would be difficult to implement fast.
There are things to consider, there may be cycles when finding closest distances, so it is not going to be your standard dynamic programming problem. Most shortest path algorithms can be a bit heavy to repeat 100000 times. It is best to precalculate things. Even precalculating, I think Dijkstra would not work well. So we need some sort of dp.
Note that the constraint for k_i is uselessly large. Every round, you shall need to visit at most n-1 cities, so there is no need to change cars more than n-1 times.
Let us imagine k=0, so we cannot really change cars. We can still pick any car we want to do all the round though. So, first calculate for each pair of cities (i,j) the minimum path between them using a given car. This is Floyd-Warshall's specialty. After that, for each pair (i,j) pick the car that gives the minimum distance travelled. Remember the best distance possible using any car (without changing), for each (i,j).
The any car bit was my savior, because it can simplify things up later. Let us now find F(i,j,K). The number of ways to move from city i to j, switching cars at most K times, and starting with any car and finishing with any car. The dynamic programming trick involves thinking of a city X. Let us say that you do a car change at city X. Then the minimum time would be: F(i,x,0)+F(x,j, K-1). Because, you can make (K-1) more changes between x and j. Since F assumes the starting and finishing car can be anything, it is just the same as performing a change.
Thus we only need a loop of n-1 steps that tries all values for x to precalculate all the values we will ever need of F(i,j,K).
int n,m,r;
int road[60][60][60];
int s[100000];
int t[100000];
int k[100000];
const char BINF = 0x4F; //I do this so I can do memset to
const int INF = 0x4F4F4F4F; // int in INF.
int dist[61][61][61][61];
void solve()
{
assert(INF > 50*1000000);
memset(dist, BINF, sizeof(dist));
// first without changing, floyd warshall.
for (int car=0; car<m; car++) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
dist[i][j][ car ][0] = road[car][i][j];
}
}
for (int x=0; x<n; x++) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) { //O(x^4)
int y= dist[i][x][car][0] + dist[x][j][car][0];
dist[i][j][ car ][0] = min( dist[i][j][car][0], y);
}
}
}
}
//Save optimal ways if you could use any car
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
dist[i][j][m][0] = INF;
for (int car=0; car<m; car++) { //O(x^3)
dist[i][j][m][0] = min(dist[i][j][m][0], dist[i][j][car][0]);
}
}
}
for (int changes = 1; changes <= n-1; changes++) {
//This dp looks a lot like Floyd, doesn't it?
for (int x=0; x<n; x++) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) { //O(x^4)
// So, we first move from i to x using the best car we like.
// Then we move from x to j using the best cars in {changes-1}
int y = dist[i][x][m][0] + dist[x][j][m][changes-1];
dist[i][j][m][changes] = min(dist[i][j][m][changes], y);
}
}
}
}
for (int i=0; i<r; i++) {
int res = dist[s[i]][t[i]][m][ min(k[i], n-1) ];
cout << res<<endl;
}
//O(x^4 + r)
}
Div1 C / Div2 E
So, just as I finished writing B's explanation, I found out I failed C. Well, my solution was a little far-fetched to begin with. I tried something crazy nesting BFS inside a Dijkstra. At this moment I am not sure if I failed because the idea is wrong or because of a mistake in implementing the idea, such is life.
I exceeded the time limit, but then again I could swear I was visiting each road at most once. Hmnn.
Addendum
I had tons of issues when attempting to write this. blogger was ignoring my commands. To tell you it has been 30 minutes since I actually finished the post. It turns out that the lame new blogger interfaces omits syntax error mistakes in small screens. Because mobile computing is too novel for the developers. I almost lost 2/3 of all I wrote. The mountain of suck in the new blogger is really terrible.
No comments :
Post a Comment