Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию

в 7:51, , рубрики: Блог компании Яндекс, Занимательные задачки, конкурсы, конкурсы разработчиков, математика, машинное обучение, многорукие бандиты, рекомендательные системы, Спортивное программирование, Яндекс.Блиц

Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию - 1

Мы продолжаем публиковать разборы задач, которые предлагались на недавнем чемпионате. На очереди — задачи, взятые из квалификационного раунда для специалистов по машинному обучению. Это третий трек из четырёх (бэкенд, фронтенд, 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 строках содержатся возможные замены в формате &lt«правильная» последовательность букв&gt<пробел><«ошибочная» последовательность букв>. Последовательности имеют длину не более 6 символов.

Формат вывода

Требуется вывести одно число — минимальное количество ошибок, которое мог совершить пользователь. Если это количество превышает 4 или же из одного слова невозможно получить другое, следует вывести –1.

Пример

Ввод Вывод
mlax
drum
50
l r
mlax gtwt
m d
mlax ujoc
ml pq
m f
ml bf
mlax aruq
mlax nqdd
mlax fglm
mlax bfit
mlax mziq
mla hlb
a u
mlax vmpa
m w
a w
ax ok
mla kqf
m e
x x
ml if
ml gk
l e
mla xrh
m j
a c
a b
m q
ax fr
ml sb
mlax gxxx
x m
mlax hczx
l q
la sv
l g
ax eh
lax mjh
la ec
la pv
ml iq
a q
lax jrs
la qn
lax bjo
l o
a z
l n
a c
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 выбирается из дискретного распределения:

Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию - 2.

Здесь μs, σs — параметры распределения, а αs — нормировочный коэффициент, выбираемый так, чтобы Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию - 3.

3. [0-1] Вставка предложения

С вероятностью pi приписываем в перевод одно предложение. В оригинал не приписываем ничего. Длина предложения на языке перевода L ≥ 1 выбирается из дискретного распределения:

Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию - 4.

Здесь μt, σt — параметры распределения, а αt — нормировочный коэффициент, выбираемый так, чтобы Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию - 5.

4. Перевод

С вероятностью (1 – pd – pi – ph) берём длину предложения на языке оригинала Ls ≥ 1 из распределения ps (с округлением вверх). Далее генерируем длину предложения на языке перевода Lt ≥ 1 из условного дискретного распределения:

Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию - 6.

Здесь α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
1 1
4
20
1 1
0.975037457809

Пример 2

Ввод Вывод
0.1 0.2 0.3 0.25 0.3 1 0.3 3 0.5
2 1
3 4
20
2 1
0.247705779810

Пример 3

Ввод Вывод
0.2 0.2 0.2 0.3 0.3 3 0.3 1 1
5 3
16 35 24 19 23
5 6 7
2 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 закончить генерацию.

Вероятность этого события равна
Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию - 7.

В итоге ответ рассчитывается как Жадный подход и игровые автоматы. Разбор задач ML-трека чемпионата по программированию - 8.

Решение

Задача является частным случаем выравнивания с помощью скрытых марковских моделей (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. Релевантность списка вычисляется по формуле $sum_{j=0}^{k-1} 2_{-j}r(a_{i_j})$. Вам нужно найти максимальный по релевантности список среди всех допустимых.

Форматы ввода/вывода и примеры

Формат ввода

На первой строке через пробел записаны числа 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
0

Пример 2

Ввод Вывод
2 2
1
1
0

Пример 3

Ввод Вывод
10 2
1
1
1
0
0
1
0
1
1
1
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
a
a
aa
a
aaa
a
aaaaaa
aa
a
a
a
aaa
a
a
aaa
aa
aaaa
aaa
a
aaaaa
aa
a
aaaa
a
a
a
a
a
a
aa
aaaa
aaa
a
aa
aaaa
a
a
a
a
a
a
a
a
a
a
aa
aaa
aaa
a
a
bbb
bb
bb
bbbbbbb
bb
bbb
b
bbbbbbb
bbbb
bbb
bb
bbb
bb
bb
bbb
bbbbbb
bbb
b
bbbbbb
b
bbbbb
b
b
bb
b
bb
bb
b
b
b
b
bb
bb
bb
b
b
b
bb
b
bbb
bb
b
bbbbbb
b
bb
bb
bb
b
bb
bbb
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Примечания

Замечание к тесту из условия: в нём первые 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()


Вот разборы задач по бэкенду и фронтенду.

Автор: Леонид Клюев

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js