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
#include <algorithm>
#include <iostream>
#include "message.h"
using namespace std;

#define PART_SIZE 110

int work(int n, int m, char* firstWord, char* secondWord, int startY, int endY, int& numberOfShocks)
{
	// Init previous and current column
	int sizeY = endY - startY + 1;
	int* previousColumn = new int[sizeY + 1]; // +1 because "header"
	int* currentColumn = new int[sizeY + 1];
	int* row = new int[PART_SIZE];
	numberOfShocks = 0;

	previousColumn[0] = 0;
	for (int i = 1; i <= sizeY; i++)
	{
		previousColumn[i] = startY + i;
	}

	// Count number of parts
	int numberOfParts = 1 + ((n - 1) / PART_SIZE);
	int startX, endX, widthX;
	for (int part = 0; part < numberOfParts; part++)
	{
		startX = part * PART_SIZE;
		endX = min(startX + PART_SIZE - 1, n - 1);
		widthX = endX - startX + 1;
		if (MyNodeId() == 0)
		{
			// First machine - init row with letterrs
			for (int i = 0; i < widthX; i++)
			{
				row[i] = startX + i;
			}
		}
		else
		{
			// second, third, fourth... machine - get results from above ;)
			int aboveNode = MyNodeId() - 1;
			Receive(aboveNode);
			for (int i = 0; i < widthX; i++)
			{
				row[i] = GetInt(aboveNode);
			}
		}

		// Do Levenshtein
		for (int i = 0; i < widthX; i++)
		{
			currentColumn[0] = row[i];
			for (int j = 1; j < sizeY + 1; j++)
			{
				int change = previousColumn[j - 1];
				if (firstWord[startX + i] != secondWord[j - 1])
					change++;
				int left = previousColumn[j] + 1;
				int above = currentColumn[j - 1] + 1;
				if (change < left && change < above)
				{
					if (firstWord[startX + i] < secondWord[j - 1])
					{
						numberOfShocks++;
					}
					currentColumn[j] = change;
				}
				else
				{
					currentColumn[j] = min(left, above);
				}
			}
			row[i] = currentColumn[sizeY];
			previousColumn = currentColumn;
		}

		// Send to below
		if (MyNodeId() < NumberOfNodes() - 1)
		{
			for (int i = 0; i < widthX; i++)
				PutInt(MyNodeId() + 1, row[i]);
			Send(MyNodeId() + 1);
		}
	}

	return currentColumn[sizeY];
}

int main() {

	int n, m;
	cin >> n;
	cin >> m;

	int numberOfNodes = NumberOfNodes();
	if (numberOfNodes > m)
	{
		numberOfNodes = m;
	}

	if (MyNodeId() > numberOfNodes - 1)
	{
		return 0;
	}

	// Count intervals for this node
	int startM = MyNodeId() * m / numberOfNodes;
	int endM = (MyNodeId() + 1) * m / numberOfNodes - 1;
	int secondSize = endM - startM + 1;

	// Read input
	char* firstWord = new char[n];
	char* secondWord = new char[secondSize];
	for (int i = 0; i < n; i++)
	{
		cin >> firstWord[i];
	}

	char unusedChar;
	for (int i = 0; i < startM; i++)
	{
		cin >> unusedChar;
	}
	for (int i = 0; i < secondSize; i++)
	{
		cin >> secondWord[i];
	}

	int numberOfShocks = 0;
	int result = work(n, m, firstWord, secondWord, startM, endM, numberOfShocks);

	if (MyNodeId() == numberOfNodes - 1)
	{
		for (int node = 0; node < numberOfNodes - 1; node++)
		{
			Receive(node);
			numberOfShocks += GetInt(node);
		}
		cout << result << " " << numberOfShocks;
	}
	else
	{
		PutInt(numberOfNodes - 1, numberOfShocks);
		Send(numberOfNodes - 1);
	}


	return 0;
}