Мы продолжаем публиковать разборы задач, которые предлагались на недавнем чемпионате. На очереди — задачи, взятые из квалификационного раунда для специалистов по машинному обучению. Это третий трек из четырёх (бэкенд, фронтенд, ML, аналитика). Участникам нужно было сделать модель исправления опечаток в текстах, предложить стратегию игры на игровых автоматах, довести до ума систему рекомендаций контента и составить ещё несколько программ.
A. Опечатки
Условие
| Все языки | python2.7+numpy | python3.5+numpy | |
| Ограничение времени | 1 с | 5 с | 5 с |
| Ограничение памяти | 64 МБ | 256 МБ | 256 МБ |
| Ввод | стандартный ввод или input.txt | ||
| Вывод | стандартный вывод или output.txt | ||
(эпиграф)(с одного форума)
— Кто сочинил эту чушь?
— Астрофизики. Они тоже люди.
— Вы 10 ошибок в слове «журналисты» сделали.
Многие пользователи делают ошибки при наборе, некоторые — из-за попаданий мимо клавиш, некоторые — из-за своей неграмотности. Мы хотим проверить, мог ли пользователь на самом деле иметь в виду некоторое другое слово, чем то, которое он набрал.
Более формально, предположим, что имеет место следующая модель ошибок: пользователь начинает с некоторого слова, которое он хочет написать, и дальше последовательно делает в нём некоторое количество ошибок. Каждая ошибка представляет собой замену некоторой подстроки слова на другую подстроку. Одна ошибка соответствует замене только в одной позиции (то есть если пользователь захочет сделать единственную ошибку по правилу «abc»→«cba», то из строки «abcabc» он может получить либо «cbaabc», либо «abccba»). После каждой ошибки процесс повторяется. Одно и то же правило могло использоваться несколько раз в различных шагах (так, в вышеприведённом примере за два шага могло получиться «cbacba»).
Требуется определить, какое минимальное количество ошибок пользователь мог совершить, если он имел в виду одно заданное слово, а написал другое.
Формат ввода
В первой строке содержится слово, которое, по нашему предположению, пользователь имел в виду (оно состоит из букв латинского алфавита в нижнем регистре, длина не превышает 20).
Во второй строке содержится слово, которое он на самом деле написал (оно также состоит из букв латинского алфавита в нижнем регистре, длина не превышает 20).
В третьей строке содержится единственное число N (N < 50) — количество замен, описывающих различные ошибки.
В следующих N строках содержатся возможные замены в формате <«правильная» последовательность букв><пробел><«ошибочная» последовательность букв>. Последовательности имеют длину не более 6 символов.
Формат вывода
Требуется вывести одно число — минимальное количество ошибок, которое мог совершить пользователь. Если это количество превышает 4 или же из одного слова невозможно получить другое, следует вывести –1.
Пример
| Ввод | Вывод |
mlax |
4 |
Решение
Попробуем сгенерировать из правильного написания все возможные слова не более чем с 4 ошибками. Их в худшем случае может быть O((L﹒N)4). В ограничениях задачи это довольно большое число, поэтому нужно придумать, как уменьшить сложность. Можно вместо этого воспользоваться алгоритмом meet-in-the-middle: сгенерировать слова не более чем c 2 ошибками, а также слова, из которых можно получить написанное пользователем слово, сделав не более 2 ошибок. Заметим, что размер каждого из этих множеств не будет превышать 106. Если количество сделанных пользователем ошибок не превосходит 4, то эти множества будут пересекаться. Аналогично можно проверить, что число ошибок не превосходит 3, 2 и 1.
struct FromTo {
std::string from;
std::string to;
};
std::pair<size_t, std::string> applyRule(const std::string& word, const FromTo &fromTo, int pos) {
while(true) {
int from = word.find(fromTo.from, pos);
if (from == std::string::npos) {
return {std::string::npos, {}};
}
int to = from + fromTo.from.size();
auto cpy = word;
for (int i = from; i < to; i++) {
cpy[i] = fromTo.to[i - from];
}
return {from, std::move(cpy)};
}
}
void inverseRules(std::vector<FromTo> &rules) {
for (auto& rule: rules) {
std::swap(rule.from, rule.to);
}
}
int solve(std::string& wordOrig, std::string& wordMissprinted, std::vector<FromTo>& replaces) {
std::unordered_map<std::string, int> mapping;
std::unordered_map<int, std::string> mappingInverse;
mapping.emplace(wordOrig, 0);
mappingInverse.emplace(0, wordOrig);
mapping.emplace(wordMissprinted, 1);
mappingInverse.emplace(1, wordMissprinted);
std::unordered_map<int, std::unordered_set<int>> edges;
auto buildGraph = [&edges, &mapping, &mappingInverse](int startId, const std::vector<FromTo>& replaces, bool dir) {
std::unordered_set<int> mappingLayer0;
mappingLayer0 = {startId};
for (int i = 0; i < 2; i++) {
std::unordered_set<int> mappingLayer1;
for (const auto& v: mappingLayer0) {
auto& word = mappingInverse.at(v);
for (auto& fromTo: replaces) {
size_t from = 0;
while (true) {
auto [tmp, wordCpy] = applyRule(word, fromTo, from);
if (tmp == std::string::npos) {
break;
}
from = tmp + 1;
{
int w = mapping.size();
mapping.emplace(wordCpy, w);
w = mapping.at(wordCpy);
mappingInverse.emplace(w, std::move(wordCpy));
if (dir) {
edges[v].emplace(w);
} else {
edges[w].emplace(v);
}
mappingLayer1.emplace(w);
}
}
}
}
mappingLayer0 = std::move(mappingLayer1);
}
};
buildGraph(0, replaces, true);
inverseRules(replaces);
buildGraph(1, replaces, false);
{
std::queue<std::pair<int, int>> q;
q.emplace(0, 0);
std::vector<bool> mask(mapping.size(), false);
int level{0};
while (q.size()) {
auto [w, level] = q.front();
q.pop();
if (mask[w]) {
continue;
}
mask[w] = true;
if (mappingInverse.at(w) == wordMissprinted) {
return level;
}
for (auto& v: edges[w]) {
q.emplace(v, level + 1);
}
}
}
return -1;
}B. Многорукий бандит
Условие
| Ограничение времени | 2 с |
| Ограничение памяти | 64 МБ |
| Ввод | стандартный ввод |
| Вывод | стандартный вывод |
Это интерактивная задача.
Вы сами не знаете как так вышло, но вы обнаружили себя в зале с игровыми автоматами с целым мешком жетонов. К сожалению, в кассе жетоны назад принимать отказываются, и вы решили испытать свою удачу. В зале есть много автоматов, в которые вы можете играть. Для одной игры с автоматом вы используете один жетон. В случае выигрыша автомат даёт вам один доллар, в случае проигрыша — ничего. У каждого автомата есть фиксированная вероятность выигрыша (которую вы не знаете), но у разных автоматов она разная. Изучив сайт производителя этих автоматов, вы выяснили, что вероятность выигрыша у каждого автомата выбирается случайно на этапе изготовления из бета-распределения с определёнными параметрами.
Вам хочется максимизировать свой ожидаемый выигрыш.
Формат ввода
Одно исполнение может состоять из нескольких тестов.
Каждый тест начинается с того, что вашей программе в одной строке подаются два целых числа, разделённые пробелом: число N — количество жетонов в вашем мешке, и M — количество автоматов в зале (N ≤ 104, M ≤ min(N, 100)). В следующей строке содержатся два вещественных числа α и β (1 ≤ α, β ≤ 10) — параметры бета-распределения вероятности выигрыша.
Протокол общения с проверяющей системой такой: вы делаете ровно N запросов. На каждый запрос выведите в отдельную строку номер автомата, в который вы будете играть (от 1 до M включительно). В качестве ответа в отдельной строке будет стоять либо «0», либо «1», означающие соответственно проигрыш и выигрыш в игре с запрошенным автоматом.
После последнего теста вместо чисел N и M будут стоять два нуля.
Формат вывода
Задача будет считаться сданной, если ваше решение не сильно хуже решения жюри. Если ваше решение будет значительно хуже решения жюри, вы получите вердикт «неправильный ответ».
Гарантируется, что если ваше решение не хуже, чем решение жюри, то вероятность получить вердикт «неправильный ответ» не превосходит 10–6.
Примечания
Пример взаимодействия:
____________________
stdin stdout
____________________
____________________
5 2
2 2
2
1
1
0
1
1
2
1
2
1Решение
Эта задача достаточно известна, её можно было решать по-разному. Основное решение жюри реализовывало стратегию Thompson sampling, но поскольку число шагов было известно в начале работы программы, существуют и более оптимальные стратегии (например, UCB1). Более того, можно было даже обойтись epsilon-greedy-стратегией: с некоторой вероятностью ε играть в случайный автомат и с вероятностью (1 – ε) играть в автомат, у которого статистика побед лучше всего.
class SolverFromStdIn(object):
def __init__(self):
self.regrets = [0.]
self.total_win = [0.]
self.moves = []
class ThompsonSampling(SolverFromStdIn):
def __init__(self, bandits_total, init_a=1, init_b=1):
"""
init_a (int): initial value of a in Beta(a, b).
init_b (int): initial value of b in Beta(a, b).
"""
SolverFromStdIn.__init__(self)
self.n = bandits_total
self.alpha = init_a
self.beta = init_b
self._as = [init_a] * self.n # [random.betavariate(self.alpha, self.beta) for _ in range(self.n)]
self._bs = [init_b] * self.n # [random.betavariate(self.alpha, self.beta) for _ in range(self.n)]
self.last_move = -1
random.seed(int(time.time()))
def move(self):
samples = [random.betavariate(self._as[x], self._bs[x]) for x in range(self.n)]
self.last_move = max(range(self.n), key=lambda x: samples[x])
self.moves.append(self.last_move)
return self.last_move
def set_reward(self, reward):
i = self.last_move
r = reward
self._as[i] += r
self._bs[i] += (1 - r)
return i, r
while True:
n, m = map(int, sys.stdin.readline().split())
if n == 0 and m == 0:
break
alpha, beta = map(float, sys.stdin.readline().split())
solver = ThompsonSampling(m)
for _ in range(n):
print >> sys.stdout, solver.move() + 1
sys.stdout.flush()
reward = int(sys.stdin.readline())
solver.set_reward(reward)C. Выравнивание предложений
Условие
| Ограничение времени | 2 с |
| Ограничение памяти | 64 МБ |
| Ввод | стандартный ввод или input.txt |
| Вывод | стандартный вывод или output.txt |
Одна из важнейших задач для обучения хорошей модели машинного перевода — хороший корпус параллельных предложений. Обычно источником для параллельных предложений являются параллельные документы. Оказывается, часто для того, чтобы построить некоторый корпус параллельных предложений, не нужно знать ничего, кроме их длин. В частности, можно заметить, что чем длинее предложение на исходном языке, тем длинее, скорее всего, будет его перевод. Некоторая сложность состоит в том, что при переводе количество предложений в тексте может поменяться: иногда два соседних предложения при переводе могут быть объединены в одно, или наоборот — одно предложение могло быть разделено на два. В отдельных редких случаях предложения могут целиком пропускаться в переводе, или в переводе может появиться предложение, которого не было в оригинале.
Более формально, предположим, что верна следующая генеративная модель для параллельных корпусов. На каждом шаге мы совершаем одно из следующих действий:
1. Остановка
С вероятностью ph генерация корпусов заканчивается.
2. [1-0] Пропуск предложения
С вероятностью pd приписываем в оригинальный текст одно предложение. В перевод не приписываем ничего. Длина предложения на языке оригинала L ≥ 1 выбирается из дискретного распределения:
.
Здесь μs, σs — параметры распределения, а αs — нормировочный коэффициент, выбираемый так, чтобы 
.
3. [0-1] Вставка предложения
С вероятностью pi приписываем в перевод одно предложение. В оригинал не приписываем ничего. Длина предложения на языке перевода L ≥ 1 выбирается из дискретного распределения:
.
Здесь μt, σt — параметры распределения, а αt — нормировочный коэффициент, выбираемый так, чтобы 
.
4. Перевод
С вероятностью (1 – pd – pi – ph) берём длину предложения на языке оригинала Ls ≥ 1 из распределения ps (с округлением вверх). Далее генерируем длину предложения на языке перевода Lt ≥ 1 из условного дискретного распределения:
.
Здесь αst — нормировочный коэффициент, а остальные параметры описаны в предыдущих пунктах.
Далее происходит ещё один шаг:
1. [2-1] С вероятностью psplit s сгенерированное предложение на языке оригинала распадается на два непустых, так, чтобы суммарное количество слов увеличилось ровно на один. Вероятность того, что предложение длины Ls распадётся на части длиной L1 и L2 (то есть L1 + L2 = Ls + 1), пропорциональна Ps(L1) ⋅ Ps(L2).
2. [1-2] С вероятностью psplit t сгенерированное предложение на языке перевода распадается на два непустых, так, чтобы суммарное количество слов увеличилось ровно на один. Вероятность того, что предложение длины Lt распадётся на части длиной L1 и L2 (то есть L1 + L2 = Lt + 1), пропорциональна Pt(L1) ⋅ Pt(L2).
3. 3. [1-1] С вероятностью (1 – psplit s – psplit t) ни одно из пары сгенерированных предложений не распадётся.
Формат ввода
В первой строке файла записаны параметры распределений: ph, pd, pi, psplit s, psplit t, μs, σs, μt, σt. 0,1 ≤ σs < σt ≤ 3. 0 ≤ μs, μt ≤ 5.
В следующей строке стоят числа Ns и Nt — количество предложений в корпусе на языке оригинала и на языке перевода соответственно (1 ≤ Ns, Nt ≤ 1000).
В следующей строке находятся Ns целых чисел — длины предложений на языке оригинала. В следующей строке находятся Nt целых чисел — длины предложений на языке перевода.
В следующей строке находятся два числа: j и k (1 ≤ j ≤ Ns, 1 ≤ k ≤ Nt).
Формат вывода
Требуется вывести вероятность того, что предложения с индексами j и k в текстах соответственно являются параллельными (то есть что они сгенерированы на одном шаге алгоритма и ни одно из них не является результатом распада).
Ваш ответ будет принят, если абсолютная погрешность не превосходит 10–4.
Пример 1
| Ввод | Вывод |
0.05 0.08 0.07 0.15 0.1 1 0.3 3 0.5 |
0.975037457809 |
Пример 2
| Ввод | Вывод |
0.1 0.2 0.3 0.25 0.3 1 0.3 3 0.5 |
0.247705779810 |
Пример 3
| Ввод | Вывод |
0.2 0.2 0.2 0.3 0.3 3 0.3 1 1 |
0.200961101684 |
Примечания
В первом примере исходную последовательность чисел можно получить тремя способами:
• Сначала с вероятностью pd дописать одно предложение в оригинальный текст, затем с вероятностью pi дописать одно предложение в перевод, потом с вероятностью ph закончить генерацию.
Вероятность этого события равна P1 = pd * Ps(4) * pi * Pt(20) * ph.
• Сначала с вероятностью pd дописать одно предложение в оригинальный текст, затем с вероятностью pi дописать одно предложение в перевод, потом с вероятностью ph закончить генерацию.
Вероятность этого события равна P2 = pi * Pt(20) * pd * Ps(4) * ph.
• C вероятностью (1 – ph – pd – pi) сгенерировать два предложения, затем с вероятностью (1 – psplit s – psplit t) оставить всё как есть (то есть не разбивать на два предложения ни оригинал, ни перевод) и после этого с вероятностью ph закончить генерацию.
Вероятность этого события равна
.
В итоге ответ рассчитывается как 
.
Решение
Задача является частным случаем выравнивания с помощью скрытых марковских моделей (HMM alignment). Основная идея состоит в том, что можно вычислить вероятность генерации конкретной пары документов с помощью этой модели и алгоритма forward: в данном случае состоянием является пара префиксов документов. Соответственно, требуемую вероятность выравнивания конкретной пары параллельных предложений можно вычислить алгоритмом forward-backward.
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
double p_h, p_d, p_i, p_tr, p_ss, p_st, mu_s, sigma_s, mu_t, sigma_t;
double lognorm_cdf(double x, double mu, double sigma) {
if (x < 1e-9)
return 0.0;
double res = std::log(x) - mu;
res /= std::sqrt(2.0) * sigma;
res = 0.5 * (1 + std::erf(res));
return res;
}
double length_probability(int l, double mu, double sigma) {
return lognorm_cdf(l, mu, sigma) - lognorm_cdf(l - 1, mu, sigma);
}
double translation_probability(int ls, int lt) {
double res = length_probability(ls, mu_s, sigma_s);
double mu = mu_t - mu_s + std::log(ls);
double sigma = std::sqrt(sigma_t * sigma_t - sigma_s * sigma_s);
res *= length_probability(lt, mu, sigma);
return res;
}
double split_probability(int l1, int l2, double mu, double sigma) {
int l_sum = l1 + l2;
double total_prob = 0.0;
for (int i = 1; i < l_sum; ++i) {
total_prob += length_probability(i, mu, sigma) * length_probability(l_sum - i, mu, sigma);
}
return length_probability(l1, mu, sigma) * length_probability(l2, mu, sigma) / total_prob;
}
double log_prob10(int ls) {
return std::log(p_d * length_probability(ls, mu_s, sigma_s));
}
double log_prob01(int lt) {
return std::log(p_i * length_probability(lt, mu_t, sigma_t));
}
double log_prob11(int ls, int lt) {
return std::log(p_tr * (1 - p_ss - p_st) * translation_probability(ls, lt));
}
double log_prob21(int ls1, int ls2, int lt) {
return std::log(p_tr * p_ss * split_probability(ls1, ls2, mu_s, sigma_s) * translation_probability(ls1 + ls2 - 1, lt));
}
double log_prob12(int ls, int lt1, int lt2) {
return std::log(p_tr * p_st * split_probability(lt1, lt2, mu_t, sigma_t) * translation_probability(ls, lt1 + lt2 - 1));
}
double logsum(double v1, double v2) {
double res = std::max(v1, v2);
v1 -= res;
v2 -= res;
v1 = std::min(v1, v2);
if (v1 < -30) {
return res;
}
return res + std::log(std::exp(v1) + 1.0);
}
double loginc(double* to, double from) {
*to = logsum(*to, from);
}
constexpr double INF = 1e25;
int main(void) {
using std::cin;
using std::cout;
cin >> p_h >> p_d >> p_i >> p_ss >> p_st >> mu_s >> sigma_s >> mu_t >> sigma_t;
p_tr = 1.0 - p_h - p_d - p_i;
int Ns, Nt;
cin >> Ns >> Nt;
using std::vector;
vector<int> ls(Ns), lt(Nt);
for (int i = 0; i < Ns; ++i)
cin >> ls[i];
for (int i = 0; i < Nt; ++i)
cin >> lt[i];
vector< vector< double> > fwd(Ns + 1, vector<double>(Nt + 1, -INF)), bwd = fwd;
fwd[0][0] = 0;
bwd[Ns][Nt] = 0;
for (int i = 0; i <= Ns; ++i) {
for (int j = 0; j <= Nt; ++j) {
if (i >= 1) {
loginc(&fwd[i][j], fwd[i - 1][j] + log_prob10(ls[i - 1]));
loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j] + log_prob10(ls[Ns - i]));
}
if (j >= 1) {
loginc(&fwd[i][j], fwd[i][j - 1] + log_prob01(lt[j - 1]));
loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i][Nt - j + 1] + log_prob01(lt[Nt - j]));
}
if (i >= 1 && j >= 1) {
loginc(&fwd[i][j], fwd[i - 1][j - 1] + log_prob11(ls[i - 1], lt[j - 1]));
loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j + 1] + log_prob11(ls[Ns - i], lt[Nt - j]));
}
if (i >= 2 && j >= 1) {
loginc(&fwd[i][j], fwd[i - 2][j - 1] + log_prob21(ls[i - 1], ls[i - 2], lt[j - 1]));
loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i + 2][Nt - j + 1] + log_prob21(ls[Ns - i], ls[Ns - i + 1], lt[Nt - j]));
}
if (i >= 1 && j >= 2) {
loginc(&fwd[i][j], fwd[i - 1][j - 2] + log_prob12(ls[i - 1], lt[j - 1], lt[j - 2]));
loginc(&bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j + 2] + log_prob12(ls[Ns - i], lt[Nt - j], lt[Nt - j + 1]));
}
}
}
int j, k;
cin >> j >> k;
double rlog = fwd[j - 1][k - 1] + bwd[j][k] + log_prob11(ls[j - 1], lt[k - 1]) - bwd[0][0];
cout << std::fixed << std::setprecision(12) << std::exp(rlog) << std::endl;
}D. Лента рекомендаций
Условие
| Ограничение времени | 2 с |
| Ограничение памяти | 64 МБ |
| Ввод | стандартный ввод или input.txt |
| Вывод | стандартный вывод или output.txt |
Рассмотрим ленту рекомендаций разнородного контента. В ней смешаны объекты разного типа (картинки, видео, новости и т. д.). Эти объекты обычно упорядочиваются по релевантности пользователю: чем релевантнее (интереснее) объект пользователю, тем он ближе к началу списка рекомендаций. Однако при таком упорядочивании часто возникают ситуации, в которых в списке рекомендаций встречаются несколько объектов подряд одного типа. Это сильно ухудшает внешнее разнообразие наших рекомендаций и поэтому не нравится пользователям. Необходимо реализовать алгоритм, который по списку рекомендаций составит новый список, который будет лишен этой проблемы и будет наиболее релевантным.
Пусть задан исходный список рекомендаций a = [a0, a1,…, an − 1] длины n > 0. Объект под номером i имеет тип с номером bi ∈ {0,…, m − 1}. Кроме того, объект под номер i имеет релевантность r(ai) = 2−i. Рассмотрим список, который получается из исходного выбором подмножества объектов и их перестановкой: x = [ai0, ai1,…,aik−1] длины k (0 ≤ k ≤ n). Список называется допустимым, если никакие два подряд идущих объекта в нём не совпадают по типу, т. е. bij ≠ bij + 1 для всех j = 0,…, k−2. Релевантность списка вычисляется по формуле 
. Вам нужно найти максимальный по релевантности список среди всех допустимых.
Формат ввода
На первой строке через пробел записаны числа n и m (1 ≤ n ≤ 100000, 1 ≤ m ≤ n). На следующих n строках записаны числа bi для i = 0,…, n − 1 (0 ≤ bi ≤ m − 1).
Формат вывода
Выпишите через пробел номера объектов итогового списка: i0, i1,…, ik−1.
Пример 1
| Ввод | Вывод |
1 1 |
0 |
Пример 2
| Ввод | Вывод |
2 2 |
0 |
Пример 3
| Ввод | Вывод |
10 2 |
0 3 1 4 2 6 5 |
Решение
Путем несложных математических выкладок можно показать, что задача может быть решена «жадным» подходом, т. е. в оптимальном списке рекомендаций на каждой позиции стоит самый релевантный объект из всех, которые допустимы при том же начале списка. Имплементация этого подхода простая: берём объекты подряд и добавляем их в ответ, если это возможно. Когда встречается недопустимый объект (тип которого совпадает с типом предыдущего), то откладываем его в отдельную очередь, из которой вставляем в ответ при первой же возможности. Заметим, что в каждый момент времени у всех объектов в этой очереди будет совпадающий тип. В конце в очереди могут остаться несколько объектов, они уже не войдут в ответ.
std::vector<int> blend(int n, int m, const std::vector<int>& types) {
std::vector<int> result;
std::queue<int> repeated;
for (int i = 0; i < n; ++i) {
if (result.empty() || types[result.back()] != types[i]) {
result.push_back(i);
if (!repeated.empty() && types[repeated.front()] != types[result.back()]) {
result.push_back(repeated.front());
repeated.pop();
}
} else {
repeated.push(i);
}
}
return result;
}D. Кластеризация символьных последовательностей
| Все языки | python2.7+numpy | python3.5+numpy | |
| Ограничение времени | 1 с | 6 с | 6 с |
| Ограничение памяти | 64 МБ | 64 МБ | 64 МБ |
| Ввод | стандартный ввод или input.txt | ||
| Вывод | стандартный вывод или output.txt | ||
Имеется конечный алфавит A = {a1, a2,…, aK−1, aK = S}, ai ∈ {a, b,…, z}, S — конец строки.
Рассмотрим следующий способ генерации случайных строк над алфавитом A:
1. Первый символ x1 — случайная величина с распределением P(x1 = ai) = qi (известно, что qK = 0).
2. Каждый следующий символ генерируется на основе предыдущего в соответствии с условным распределением P(xi = aj || xi – 1 = al) = pjl.
3. Если xi = S, генерация прекращается и результатом является x1x2...xi−1.
Даётся набор строк, сгенерированных из смеси двух описанных моделей с различными параметрами. Необходимо для каждой строки дать индекс цепи, из которой она была сгенерирована.
Формат ввода
В первой строке записано два числа 1000 ≤ N ≤ 2000 и 3 ≤ K ≤ 27 — число строк и размер алфавита соответственно.
Во второй строке записана строка, состоящая из K−1 различных строчных букв латинского алфавита, обознающая первые K−1 элементов алфавита.
Каждая из следующих N строк сгенерирована по описанному в условии алгоритму.
Формат вывода
N строк, в i-й строке содержится номер кластера (0/1) для последовательности на i+1-й строке входного файла. Совпадение с истинным ответом должно быть не менее 80%.
Пример
| Ввод | Вывод |
100 3 |
0 |
Примечания
Замечание к тесту из условия: в нём первые 50 строк сгенерированы из распределения
P(xi = a | xi−1 = a) = 0.5, P(xi = S | xi−1 = a) = 0.5, P(x1 = a) = 1; вторые 50 — из распределения
P(xi = b | xi−1 = b) = 0.5, P(xi = S | xi−1 = b) = 0.5, P(x1 = b) = 1.
Решение
Задача решается с помощью EM-алгоритма: предполагается, что представленная выборка сгенерирована из смеси двух марковских цепей, параметры которых восстанавливаются в процессе итераций. Ограничение в 80% правильных ответов сделано, чтобы на правильность решения не влияли примеры, у которых высокая вероятность в обеих цепях. Эти примеры, таким образом, при правильном восстановлении могут быть отнесены к цепи, неверной с точки зрения сгенерированного ответа.
import random
import math
EPS = 1e-9
def empty_row(size):
return [0] * size
def empty_matrix(rows, cols):
return [empty_row(cols) for _ in range(rows)]
def normalized_row(row):
row_sum = sum(row) + EPS
return [x / row_sum for x in row]
def normalized_matrix(mtx):
return [normalized_row(r) for r in mtx]
def restore_params(alphabet, string_samples):
n_tokens = len(alphabet)
n_samples = len(string_samples)
samples = [tuple([alphabet.index(token) for token in s] + [n_tokens - 1, n_tokens - 1]) for s in string_samples]
probs = [random.random() for _ in range(n_samples)]
for _ in range(200):
old_probs = [x for x in probs]
# probs fixed
p0, A = empty_row(n_tokens), empty_matrix(n_tokens, n_tokens)
q0, B = empty_row(n_tokens), empty_matrix(n_tokens, n_tokens)
for prob, sample in zip(probs, samples):
p0[sample[0]] += prob
q0[sample[0]] += 1 - prob
for t1, t2 in zip(sample[:-1], sample[1:]):
A[t1][t2] += prob
B[t1][t2] += 1 - prob
A, p0 = normalized_matrix(A), normalized_row(p0)
B, q0 = normalized_matrix(B), normalized_row(q0)
trans_log_diff = [
[math.log(b + EPS) - math.log(a + EPS) for b, a in zip(B_r, A_r)]
for B_r, A_r in zip(B, A)
]
# A, p0, B, q0 fixed
probs = empty_row(n_samples)
for i, sample in enumerate(samples):
value = math.log(q0[sample[0]] + EPS) - math.log(p0[sample[0]] + EPS)
for t1, t2 in zip(sample[:-1], sample[1:]):
value += trans_log_diff[t1][t2]
probs[i] = 1.0 / (1.0 + math.exp(value))
if max(abs(x - y) for x, y in zip(probs, old_probs)) < 1e-9:
break
return [int(x > 0.5) for x in probs]
def main():
N, K = list(map(int, input().split()))
string_samples = []
alphabet = list(input().strip()) + ['']
for _ in range(N):
string_samples.append(input().rstrip())
result = restore_params(alphabet, string_samples)
for r in result:
print(r)
if __name__ == '__main__':
main()Вот разборы задач по бэкенду и фронтенду.
Автор: Леонид Клюев
