Отборочные соревнования Marathon24: ДНК-TLE

Я повторяю это постановку задачи, теперь, когда конкурс завершен (так что это не обман или что-то в этом роде, просто хочу узнать, так как ответы не публикуются, только правильный вывод для заданных входных файлов тестового примера).

Имеется 10 заданных входных данных тестового примера, для которых должны быть представлены соответствующие выходные файлы. Моя первоначальная заявка была реализацией наивного вложенного цикла for пар (начало, конец), отвечающего на вопрос: какова мера волатильности подстроки, начинающейся с индекса start (отсчитываемой от 0) и заканчивающейся end (включительно).

Ясно, что для максимальных проблемных пределов 106, O(N2) невыполнимо, поэтому я правильно выполнил только 5/10 тестовых случаев (первый - а попроще - 5, конечно).

Таким образом, я пишу здесь, чтобы узнать мнение толпы о том, как я могу улучшить свой алгоритм, а именно, я подозреваю, что вложенные циклы for (начало, конец) являются основным узким местом для оптимизации (конечно!). пошли по пути попытки сформулировать это как динамическое программирование (DP) для проблемы строк/подстрок, но без особого успеха в придумывании представления состояния и битов перехода, чтобы можно было реализовать DP.

Для простоты справки и чтобы показать, что это не домашнее задание, и я честно старался, моя исходная работа доступна здесь .

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


algorithm
person evandrix    schedule 22.10.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Пробовали разделять и властвовать?

Если я правильно понимаю задачу, то для цепочки ДНК S длины n мы делим S на две половины, S_left и S_right, где S_left состоит из S[i], где 0 ‹= i ‹ n/2, а S_right состоит из S [j] где (n/2)+1 ‹= j ‹ n. Наиболее изменчивый фрагмент либо полностью находится в пределах S_left, либо полностью находится в пределах S_right, либо пересекает границу S_left и S_right.

Чтобы найти наиболее изменчивый фрагмент S_left и S_right, мы просто используем рекурсию. Хитрость заключается в том, чтобы найти меру волатильности фрагмента, который пересекает границу S_left и S_right. Здесь есть математическое свойство положительной целочисленной дроби: данные четыре положительных (ненулевых) целых числа a, b, c и d, (a + c) / (b + d) никогда не больше, чем оба (a / б) и (в/г). Здесь a и b — совокупное количество пуринов и пиримидинов в S_left, начиная с границы, а c и d — совокупное количество пуринов и пиримидинов в S_right, начиная с границы. Это математическое свойство означает, что нам не нужно проверять меру волатильности фрагмента пересечения за пределами a = 0 или c = 0, потому что она гарантированно будет меньше максимальной волатильности S_left или S_right. Временная сложность такого поиска может составлять O(n) для фрагмента пересечения и O(n lg n) для всего алгоритма.

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

person Jason L    schedule 24.10.2013
comment
Спасибо, попробую в ближайшее время, когда у меня будет такая возможность. Я прикреплю комментарии, полученные от моего аналогичного поста в другом месте, например. Codeforces, Codechef, Topcoder и т. д. для справки и информации - person evandrix; 29.10.2013
comment
# 1: данные тестового набора являются особыми, количество «T» или «C» в каждом случае невелико и может быть обработано методом перебора, за исключением одного случая, который содержит 1000000 символов «T» или «C» и не содержит «A» или «G». ' характер, который, очевидно, может быть решен вручную. - person evandrix; 29.10.2013
comment
№ 2: 1. Если мы хотим максимизировать только соотношение, а не длину, мы можем рассматривать подстроки только с одной неправильной буквой. 2. Если учитывать еще и длину, то нужно дополнительно проверить, существует ли подстрока вида 0000110000 (k нулей, 2 единицы и k нулей), где k — наилучшее соотношение. P.S. В начале соотношение T и C к A и G было близко к 1. Позже, чтобы лучше сжимать входные данные, это соотношение было сильно снижено. - person evandrix; 29.10.2013