Ответы на задачи от компании ABBYY и награждение победителя

Свершилось! Аркадий Дьяконов darkaha@mail.ru победил задачи, поставленные перед нашими читателями экспертами компании ABBYY, за что и был награжден сертификатом на FineReader. Слава ему!

Правильные ответы

Задача 1

Дан массив из целых чисел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.

Решение

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

Одно из решений задачи:

// Далее считаем, что массив, в котором ищем подмассив, именуется как array.
// Его размер же именуется как arraySize
int maxSum = array[0];
int maxStartIdx = 0;
int maxEndIdx = 0;
int currentSum = 0;
int currentStartIdx = 0;
for( int i = 0; i < arraySize; i++ ) {
    currentSum += array[i];
    if( currentSum > maxSum ) {
        maxSum = currentSum;
        maxStartIdx = currentStartIdx;
        maxEndIdx = i;
    } else if( currentSum < 0 ) {
        currentSum = 0;
        currentStart = i + 1;
    }
}

Задача 2

Дан текст, состоящий из N слов, длина которых не превосходит некоторой небольшой константы. Предложите хотя бы два способа вывести частоты вхождения слов в текст за субквадратичное время, объясните их преимущества и недостатки.

Решение

1. Префиксное дерево (оно же бор). Строится за O(length(Text)k), где k — размер алфавита. Можно сделать log(k), если при построении в узлах дерева хранить какое-то сбалансированное дерево, чтобы искать символ за логарифм. Для решения задачи нужно при построении в листьях хранить счетчик. Когда при построении дерева прошли слово и добавили новый лист, нужно поставить 1 или сделать +1 (если лист уже существовал). Построение бора есть тут.
2. Нам понадобится хеш-функция для строки и какая-нибудь хеш-таблица для этих же строк. Каждый раз через хеш добавляем строку в таблицу. Если строка была, то делаем +1 к счетчику, иначе заводим новый, равный 1 (используем готовый контейнер CHashTable<CString, int>). Проходим по таблице и проверяем счетчики для вывода статистики.

Задача 3

Даны числительные языка хауса:

đari bakwai da hamsin da shidda — 756
sitta da đari bakwai da biyar — 6705
saba’a da đari biyar da sittin — 7560

Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda.
Запишите на хауса: 67 и 5605.

Решение

saba’in da biyar — 75
đari shidda da sittin da shidda — 666
67 — sittin da biyar
5605 — hama’a da dari shidda da biyar

Задача 4

Есть генератор случайных чисел, который с равной вероятностью генерирует дискретные значения 1, 2, 3, 4 и 5. Как, имея этот генератор, получить генератор, который бы равновероятно выдавал дискретные значения 1, 2, 3, 4, 5, 6 и 7?

Решение

Сгенерируем пять чисел x1, x2, x3, x4, х5.
Их сумма Х = x1 + x2 + x3 + x4 + х5, принимает значение 5 <= X <= 25, то есть ровно 21 значение.

Далее Х % 7 + 1 и будет равновероятно выдавать нам числа от 1 до 7. Может потребоваться несколько выполнений цикла.