Конкурс параллельного программирования Acceler8 2011: Задача

Создать новую статью

10.09.2011 12:00


Конкурс параллельного программирования Acceler8 2011
Главная
Регистрация
Задача
Правила
Победители
Форум

Задача конкурса Acceler8 2011

Внимание! Решение задачи принимается до 23:00 по Московскому времени до вторника, 15 ноября по электронной почте (подробнее — в официальных правилах конкурса).

Внимание! Конкурс продлен. Решение задачи принимается до 23:00 по Московскому времени до воскресенья, 20 ноября по электронной почте. Подробности в официальном форуме конкурса.

Поиск максимальной подматрицы

Коротко о задаче

Дана двумерная матрица значений, нужно найти в ней прямоугольную подматрицу с максимальной суммой элементов в ней среди всех подматриц.

Очевидно, что если все элементы матрицы положительны, то ответом является вся матрица. В связи с этим, чтобы задача была задачей, во входной матрице должны быть как положительные, так и нулевые и отрицательные элементы. Чтобы не читать матрицу из файла, вам нужно будет ее сгенерировать псевдослучайным алгоритмом, описанным ниже.

Генерация матрицы

Каждый элемент прямоугольной матрицы размером N столбцов и M строк (индексация строк и столбцов начинается с нуля) должен генерироваться по следующему алгоритму:

int seed = seed0;
size_t dstSize = M * N;
long long sum = 0;
int mean, remainder;

/* initialize the destination array */
for (i = 0; i < dstSize; i += 1)
{
	seed = PRNG(seed, a, b, m);
	A[i] = seed;

	/* make a sum of all elements */
	sum += seed;
}

/* calculate the mean value. Avoid float logic when making rounding. */

mean = (int) (sum / (long long) dstSize); /* updated line */
remainder = (int) (sum % (long long) dstSize); /* updated line */
mean += (remainder * 2 > (signed) dstSize) ? (1) : (0); /* updated line */

/* correct the array to make sum of all elements near to zero */
for (i = 0; i < dstSize; i += 1)
{
	A[i] -= mean;
}


Параметры a, b и seed0 даются программе на вход, как и размер генерируемой матрицы.

Функция PRNG выглядит так:

PRNG(seed, a, b, m)
{
  return (a * seed + b) % m;
}

В коде выше первый цикл заполняет матрицу неотрицательными значениями, а второй цикл вычитает из всех элементов округленное среднее значение всех ее элементов. В результате этого в матрице появляются нулевые и отрицательные элементы.

Референсный код, заполняющий матрицу можно скачать здесь.

Внимание! Обновленный референсный код, заполняющий матрицу можно скачать здесь.

 

Формулировка задачи

Написать параллельную программу для генерации матрицы целых значений и найти прямоугольную подматрицу с максимальной суммой элементов в ней. На вход программе дается один текстовый файл, содержащий размерность матрицы и параметры псевдослучайного алгоритма. Программа должны вывести в выходной файл координаты двух противоположных углов подматрицы с максимальной суммой элементов в ней.

Описание входных данных

Первый параметр командной строки — имя входного файла, второй параметр — имя выходного файла.

Во входном файле содержится несколько тестов. На первой строке входного файла дано число C — количество тестов, которые нужно решить. Далее описываются C тестов. Для каждого из них в файле дана одна строка, содержащая 6 целых чисел через пробел.

Первые два числа (M и N) — количество строк и столбцов в матрице, соответственно. Четыре следующих числа — параметры псевдослучайного алгоритма seed0, a, b и m соответственно.

Ограничения для входных параметров:

1 ≤ C ≤ 1000
1 ≤ M, N, a, b, m, seed0 ≤ 20000

Входные параметры таковы, что сумма элементов в любой подматрице исходной матрицы убирается в int32.

Описание выходного файла

Для каждого теста в выходной файл нужно вывести строку "Case #x: ", за которой следуют 6 целых чисел (через пробел) и символ переноса строки.

Первые 4 числа — две пары координат, задающих подматрицу с максимальной суммой элементов (в первой паре оба числа должны быть меньше или равны соответственным числам во второй паре, т.е. сначала описывается координаты левого верхнего, а потом правого нижнего угла). В каждой паре первое число — номер строки, а второе число — номер столбца (нумерация начинается с нуля). Если вы нашли несколько подматриц с одинаковой максимальной суммой элементов, выведите координаты любой из них.

Последние 2 числа — сумма элементов в найденной подматрице и площадь этой подматрицы соответственно.

Весь вывод должен идти в выходной файл, имя которого задается вторым параметром командной строки.

Пример вызова вашей программы

./msp input.txt output.txt

Пример входного файла (input.txt):

2
4 3 10 3 4 17
14 31 11 4 5 18

Пример выходного файла (output.txt):

Case #1: 0 2 3 2 17 4
Case #2: 0 4 5 9 18 36

Объяснение вывода по первому тесткейсу:

Сгенерирована матрица размером 4x3:

-8 -4  8 
-7 -1  0
 3 -5  5
 1  6  4


Координаты подматрицы с максимальной суммой элементов: [0][2] .. [3][2] (в этом примере это последний столбец исходной матрицы).

Сумма элементов подматрицы = 17
Площадь этой подматрицы = 4

Время выполнения

Для измерения производительности приложения будет использовано общее время выполнения, т.е. время, включающие файловые операции ввода-вывода. Для более аккуратных результатов измерения допускается вывод таймингов в stdout, в противном случае будет использован внешний таймер.

Удачи в решении! Решение задачи принимается до 23:00 по Московскому времени до вторника, 15 ноября по электронной почте (подробнее — в официальных правилах конкурса).