|
|
| (не показано 14 промежуточных версий 2 участников) |
| Строка 4: |
Строка 4: |
| | </latex> | | </latex> |
| | | | |
| − | [[Category:На проверку]]
| + | |
| | <!--Вообще-то, решения уже есть--> | | <!--Вообще-то, решения уже есть--> |
| | | | |
| − | ===Стенина Мария, группа 974===
| + | [[Категория:Решенные задачи]] |
| − | | + | [[Категория:Теоретические задачи]] |
| − | <latex>
| + | |
| − | Организуем вычисления следующим образом. После получения решения задачи линейной релаксации $(p_1, \ldots, p_n)$ заполним две таблицы. Первую назовем $C$, она будет содержать $m$ строк и $n$ столбцов. Каждая строка будет соответствовать одной скобке. В ячейке $(j, k)$ будет записана 1, если в $j$-тую скобку входит $x_k$, 0, если в $j$-тую скобку входит $\bar{x}_k$, и "-", если $k$-тая переменная не входит в $j$-тую скобку. Заполнение такой таблицы, очевидно, займет время $O(nm)$. Вторую таблицу назовем $P$, она будет содержать один столбец длины $m$. В каждой ячейке будет записана $P_j$, которую вычислим по формуле
| + | |
| − | $$
| + | |
| − | P_j = \prod_{k:C_{jk}=1} (1-p_k) \prod_{k:C_{jk}=0} p_k.
| + | |
| − | $$
| + | |
| − | Заполнение этой таблицы тоже займет время не более $O(nm)$.
| + | |
| − | | + | |
| − | Далее на каждой итерации будем производить следующие действия. Обозначим номер итерации $k$.
| + | |
| − | $$
| + | |
| − | P^0 = P;
| + | |
| − | $$
| + | |
| − | для всех $j = 1, \ldots, m$
| + | |
| − | $$
| + | |
| − | \text{если } C_{jk} = 0, \text{то } P^0_j = 0;
| + | |
| − | $$
| + | |
| − | $$
| + | |
| − | \text{если } C_{jk} = 1, \text{то } P^0_j = P^0_j / p_k;
| + | |
| − | $$
| + | |
| − | $$
| + | |
| − | P^1 = P;
| + | |
| − | $$
| + | |
| − | для всех $j = 1, \ldots, m$
| + | |
| − | $$
| + | |
| − | \text{если } C_{jk} = 1, \text{то } P^0_j = 0;
| + | |
| − | $$
| + | |
| − | $$
| + | |
| − | \text{если } C_{jk} = 0, \text{то } P^0_j = P^0_j / p_k;
| + | |
| − | $$
| + | |
| − | Все эти манипуляции занимают время $O(m)$. Далее
| + | |
| − | $$
| + | |
| − | f_0 = \sum_{j=1}^m P^0_j, \quad f_1 = \sum_{j=1}^m P^1_j.
| + | |
| − | $$
| + | |
| − | Это тоже $O(m)$. Ну и наконец, если $f_0 < f_1$, то $P = P^0$, иначе $P = P^1$. Это можно реализовать за $O(1)$.
| + | |
| − | | + | |
| − | Итого имеем заполнение двух таблиц за $O(nm)$ и $n$ итераций по $O(m)$, значит всего $O(nm)$, что и требовалось.
| + | |
| − | </latex>
| + | |