1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <deque>

#define REP(i, n) for (int i = 0; i < (n); ++i) 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i) 

//#define LOCAL 1

#ifndef LOCAL
#include "message.h"
#endif

using namespace std;

const int MAX_LEN = 110000;
const int SPLIT_MIN = 50;
//const int SPLIT_MIN = 3;

const int MAX_FROM_SHARD = MAX_LEN / 1000 + 5;
#ifndef LOCAL
const int MAX_TO_SHARD = MAX_LEN / 10 + 5;
#else
const int MAX_TO_SHARD = MAX_LEN + 5;
#endif
const int MAX = 1000000003;

struct T {
    int cost, bad_swaps;
    T(int x = 0, int y = 0) : cost(x), bad_swaps(y) {}

    bool operator<(const T& x) const {
        if (cost != x.cost) return cost < x.cost;
        return bad_swaps < x.bad_swaps;
    }
};

int from_len, to_len;
char from[MAX_LEN], to[MAX_LEN];
T d[MAX_FROM_SHARD][MAX_TO_SHARD];
int num_from_shards, num_to_shards;

int NumNodes() {
#ifndef LOCAL
    return NumberOfNodes();
#endif
    return 10;
}

void licz_komorke(int x, int y, int dx, int dy) {
    const int px = x - dx;
    const int py = y - dy;

    if (x == 0 and y == 0) {
        d[px][py] = T(0, 0);
        return;
    }

    T res = min(d[px-1][py], d[px][py-1]);
    res.cost += 1;

    if (x > 0 and y > 0) {
        T alt = d[px-1][py-1];
        if (from[x-1] == to[y-1]) {
            // pass
        } else if (from[x-1] < to[y-1]) {
            alt.cost += 1;
            alt.bad_swaps += 1;
        } else {
            alt.cost += 1;
        }

        if (alt < res) res = alt;
    }
    
    d[px][py] = res;
}

void print_d(int x_size, int y_size) {
    REP(i, x_size+1) {
        REP(j, y_size+1) {
            printf("(%2d, %2d) ", d[i][j].cost == MAX ? -1 : d[i][j].cost, d[i][j].bad_swaps == MAX ? -1 : d[i][j].bad_swaps);
        }
        printf("\n");
    }
}

int shard_x_size(int num) {
    int len = (from_len + 1) / num_from_shards;
    if (num < (from_len + 1) % num_from_shards) {
        len += 1;
    }
    return len;
}

int shard_y_size(int num) {
    int len = (to_len + 1) / num_to_shards;
    if (num < (to_len + 1) % num_to_shards) {
        len += 1;
    }
    return len;
}

int shard_dx(int num) {
    int res = num * ((from_len + 1) / num_from_shards);
    res += min(num, ((from_len + 1) % num_from_shards));
    res -= 1;
    return res;
}

int shard_dy(int num) {
    int res = num * ((to_len + 1) / num_to_shards);
    res += min(num, ((to_len + 1) % num_to_shards));
    res -= 1;
    return res;
}

#ifndef LOCAL
void get(int size) {
    int target = MyNodeId() - 1;
    Receive(target);
    FOR(i, 0, size+1) {
        d[i][0].cost = GetInt(target);
        d[i][0].bad_swaps = GetInt(target);
    }
}

void send(int size, int top) {
    int target = MyNodeId() + 1;
    FOR(i, 0, size+1) {
        PutInt(target, d[i][top].cost);
        PutInt(target, d[i][top].bad_swaps);
    }
    Send(target);
}

#else
deque< vector<T> > saved;
void get(int size) {
    vector<T> x = saved.front();
    saved.pop_front();
    FOR(i, 0, size+1) {
        d[i][0] = x[i-1];
    }
}

void send(int size, int top) {
    vector<T> tbs;
    FOR(i, 0, size+1) {
        tbs.push_back(d[i][top]);
    }
    saved.push_back(tbs);
}
#endif

void do_shard(int from_shard, int to_shard) {
    int x_size = shard_x_size(from_shard);
    int y_size = shard_y_size(to_shard);
    int dx = shard_dx(from_shard);
    int dy = shard_dy(to_shard);
//    printf("do_shard %d %d: x_size = %d, y_size = %d, dx = %d, dy = %d\n", from_shard, to_shard, x_size, y_size, dx, dy);

    d[0][0] = T(MAX, MAX);
    if (to_shard == 0) {
        REP(i, MAX_FROM_SHARD) d[i][0] = T(MAX, MAX);
    } else {
        // Copy from another instance.
        get(x_size);
    }

    if (from_shard == 0) {
        REP(i, MAX_TO_SHARD) d[0][i] = T(MAX, MAX);
    } else {
        // Copy from previous run
        int g = shard_x_size(from_shard-1);
        FOR(i, 1, MAX_TO_SHARD) d[0][i] = d[g][i];
    }

    FOR(x, 1, x_size+1) FOR(y, 1, y_size+1) {
        licz_komorke(x+dx, y+dy, dx, dy);
    }

//    print_d(x_size, y_size);

    if (from_shard == num_from_shards - 1 and to_shard == num_to_shards - 1) {
        printf("%d %d\n", d[x_size][y_size].cost, d[x_size][y_size].bad_swaps);
    } else if (to_shard + 1 < num_to_shards) {
        send(x_size, y_size);
    }
}

int div_ceil(int x, int y) {
    int res = x / y;
    if (x % y) res += 1;
    return res;
}

int main() {
    scanf("%d %d", &from_len, &to_len);
    REP(i, from_len) scanf(" %c", &from[i]);
    REP(i, to_len) scanf(" %c", &to[i]);

    num_from_shards = min(1000, div_ceil(from_len+1, SPLIT_MIN));
    num_to_shards = min(NumNodes(), div_ceil(to_len+1, SPLIT_MIN));
//    printf("num_from_shard = %d, num_to_shards = %d\n", num_from_shards, num_to_shards);

#ifndef LOCAL
    if (MyNodeId() >= num_to_shards) return 0;
    REP(i, num_from_shards) do_shard(i, MyNodeId());
#else
    REP(j, num_to_shards) REP(i, num_from_shards) do_shard(i, j);
#endif

    return 0;
}