Определите, какие элементы последовательности A можно использовать для создания данной последовательности B за линейное время
Допустим, у нас есть последовательность A и подпоследовательность A, называемая B. Мне нужно определить, какие элементы последовательности A потенциально могут быть использованы для построения подпоследовательности B.
Например, предположим, что A = [1, 3, 2, 1, 2, 3, 1, 3, 2] и B = [1, 3, 1, 2].
Чтобы построить B из A, мы могли бы использовать элементы по индексам:
- 1, 2, 4, 5
- 1, 2, 4, 9
- 1, 2, 7, 9
- 1, 6, 7, 9
Таким образом, наш ответ должен выглядеть как [true, true, false, true, true, true, true, false, true], где true означает, что возможно, что элемент с индексом i-th использовался для построения подпоследовательности B.
Это было бы легко решить с временной сложностью O(2^N * M) (сгенерировать все подпоследовательности A и сравнить их с B). Но мне нужно решение, которое работает примерно так: O(NlogN).
Я нашел решение, которое работает, когда все элементы A (а также B) уникальны.
Я перебираю A и для каждого элемента i-th проверяю:
A[i]существует вB, иначе мы можем отбросить этотi-thэлемент- Допустим,
jравен индексу, в которомA[i]был найден вB. Проверяем, есть лиi >= j, иначе мы можем отбросить этот элементi-th, потому что еслиj > i, то наша подпоследовательность не будет поддерживать порядок. - Мы проверяем, находится ли какой-либо сосед
B[j], то естьB[j - 1]илиB[j + 1], справа отA[i](все элементы, индексы которых большеi). Теперь, поскольку элементы уникальны, мы можем сказать, что этот конкретный элементA[i]должен был использоваться в какой-то позицииB[j], потому что всегда будет одна подпоследовательностьA, равнаяB.
Вот как это может выглядеть в коде:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool val_exists(const vector<pair<int, int>>& A_val_sorted, int val, int min_idx) {
if (val == -1) {
return true;
}
if (min_idx == A_val_sorted.size())
return false;
int l = 0;
int r = A_val_sorted.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (A_val_sorted[mid].first == val) {
if (A_val_sorted[mid].second >= min_idx)
return true;
l = mid + 1;
}
else if (A_val_sorted[mid].first < val) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
return false;
}
int main()
{
int n, m;
cin >> n >> m;
// val, original index
vector<pair<int, int>> A_val_sorted(n);
vector<pair<int, int>> B_val_sorted(m);
vector<int> A(m);
for (int i = 0; i < n; ++i) {
cin >> A_val_sorted[i].first;
A_val_sorted[i].second = i;
}
for (int i = 0; i < m; ++i) {
cin >> B_val_sorted[i].first;
B_val_sorted[i].second = i;
A[i] = B_val_sorted[i].first;
}
sort(A_val_sorted.begin(), A_val_sorted.end());
sort(B_val_sorted.begin(), B_val_sorted.end());
vector<int> result(n);
for (const pair<int, int>& b : A_val_sorted) {
int val = b.first;
int idx = b.second;
int l = 0;
int r = m - 1;
bool valid = false;
while (l <= r) {
int mid = (l + r) / 2;
if (B_val_sorted[mid].first == val) {
int right_ngbr_idx = B_val_sorted[mid].second + 1;
if (B_val_sorted[mid].second <= idx && val_exists(A_val_sorted, (right_ngbr_idx < A.size() ? A[right_ngbr_idx] : -1), idx + 1)) {
valid = true;
break;
}
r = mid - 1;
}
else if (B_val_sorted[mid].first < val) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
result[idx] = valid;
}
for (int i = 0; i < n; ++i)
std::cout << result[i] << ' ';
}
Я знаю, что в случае, когда элементы уникальны, это можно сделать гораздо проще. Но этот подход дает представление о том, как решить эту проблему, когда элементы неуникальны.
Вместо проверки одного из соседних часов мы можем просто проверить всю левую и правую часть от B[j]. Допустим, N = A.size() и M = B.size(). Это решение приводит к O(NlogN + MlogM + N*M*logM), потому что мы можем сортировать подпоследовательности, сохранять исходные индексы и т. д. и использовать двоичный поиск, чтобы найти A[i] в B.
Это слишком медленно. Как я могу решить эту проблему для больших последовательностей, например N = 10^5?
@TylerH Я думаю, что это больше вопрос программирования, чем информатики. Это простая задача по программированию с Польской олимпиады по информатике (первый этап), я просто перевел и перефразировал ее, чтобы она была более общей и лучше соответствовала SO, поскольку она представляет собой реальную алгоритмическую задачу, а не вопрос о решении конкретной задачи CP.
@beaker B является подпоследовательностью A (поэтому B.size() <= A.size() и все элементы B также находятся в A), поэтому элементов всегда достаточно.
@beaker Никогда не будет такого ввода, потому что теперь B не является подпоследовательностью A.
@beaker Я этого не вижу. Я слишком много думаю или что.
@TylerH Это проблема динамического программирования. Это вполне соответствует тегу алгоритма. Это не подходит ни для CS, ни для математики.
Да, изменение, сделавшее его специфичным для C++, превратило его скорее в вопрос программирования. Но до тех пор это не было специфичным для программирования, а просто математическим вопросом. Алгоритмы — это математическая концепция, а не программная. Stack Overflow предназначен для вопросов по программированию, а не по математике, а алгоритмы точно соответствуют теме (и популярны) как на math.SE, так и на CS.SE.
@TylerH Второй пункт в справочном центре — это «программный алгоритм», верно?
int mid = (l + r) / 2; -- Это целочисленное переполнение, если l + r превышает то, что может содержать int. Кроме того, вместо того, чтобы писать свой собственный (с ошибками) двоичный поиск, используйте std::lower_bound и/или std::upper_bound.
@TylerH Я только что ответил. Это совершенно очевидно программный ответ. Это не исследование CS. Это также не математика.
Хэш-карта для этого не подходит.
@beaker Да, программный алгоритм, а не просто алгоритм; оно должно быть специфичным для программного обеспечения, то есть языка программирования. Проще говоря, «Как сложить 2 + 2» — это математическая задача (не подходит для переполнения стека), тогда как «Как сложить 2 + 2 в C++» — это проблема программирования (ОК для переполнения стека) ).
@btilly Не глупите, определение алгоритма — это набор операций, которые необходимо выполнить в определенном порядке/при определенных условиях, обычно при вычислениях. Это по своей сути математика. Смотрите мой комментарий к стакану выше. Здесь можно целый день спрашивать о реализации алгоритмов в коде! Но если они просто спрашивают об алгоритме, а не о его реализации в коде, им нужно задать свой вопрос в другом месте.
@btilly Что касается вашего ответа, похоже, что вы спорите с ситуацией, которая больше не актуальна/не соответствует действительности с тех пор, как OP добавил свой код на C++.
@TylerH Значит, тега [алгоритм] быть не должно?
@Unmitigated Кто это сказал?
@TylerH Вы буквально только что сказали, что если кто-то говорит об алгоритме, а не о его реализации в коде, его следует использовать в другом месте. Но тег [algorithm] посвящен алгоритмам, часто без привязки к языку. Итак, ваш аргумент подразумевает, что тег [алгоритм] должен принадлежать где-то еще, например, математическому сайту.
Тем не менее, алгоритмы преподаются на курсах информатики, а не на курсах математики. И этот тип алгоритмических задач чаще всего проявляется на соревнованиях по программированию, собеседованиях с программистами, а иногда и в программировании. Шансы найти ответ на математическом сайте близки к 0. Независимо от вашего мнения, на самом деле именно здесь с наибольшей вероятностью можно будет получить ответ на вопрос.
@btilly Вы почему-то не понимаете, как теги можно использовать совместно с другими. В этом случае тег алгоритма в настоящее время используется вместе с тегом C++. Вопрос о реализации алгоритма на C++ касается как C++, так и алгоритмов, и здесь он полностью соответствует теме. Если бы все вопросы об алгоритмах касались только самих алгоритмов, а не языков программирования, и вопросы могли бы иметь только один тег, то да, тег алгоритма, вероятно, не принадлежал бы сюда, но очень немногие из них были бы, поскольку это была бы довольно глупая система.
@btilly Ваш второй комментарий, опять же, не имеет значения, поскольку он аргументирует позицию, которая больше не актуальна с тех пор, как ОП отредактировал свой вопрос. Пожалуйста, посмотрите на вопрос и убедитесь, что он был отредактирован с добавлением тега C++ и кода C++. Вы можете перестать спорить о том, уместен ли вопрос о реализации алгоритма на C++; здесь никто никогда не предлагал иного. Ваш комментарий также неверен; Алгоритмы преподаются почти на каждом уроке математики после начальной школы (многие формулы являются алгоритмами). Вы можете изучать и использовать алгоритмы (читай: в математике), даже не написав ни строчки кода.
@TylerH Ваши взгляды категорически противоречат моему опыту. У меня есть высшее математическое образование. Ни на одном уроке математики никогда не упоминались общие термины алгоритмов, такие как «жадный алгоритм», «динамическое программирование» или «большое О». Но их знает каждый приличный программист. Это подсказывает мне, кому следует задавать такие вопросы. Тем не менее, вы можете верить во что хотите, и я не буду дискутировать с вами дальше.
Ответы 1
Есть несколько способов сделать это.
Самый простой заключается в следующем.
Используйте жадный алгоритм с начала, чтобы выяснить, какой возможный индекс является самым ранним из возможных мест, куда может попасть каждая позиция в B.
Используйте жадный алгоритм сзади, чтобы выяснить, какой возможный индекс является последним возможным местом, куда может переместиться каждая позиция в B.
Затем в псевдокоде:
create an array of False values
for each position in B
for each place in A with that value from earliest to latest this position in B can go
mark it True
Оптимизация. Создайте словарь, сопоставляющий каждое значение со всеми местами в A, где оно находится. Места перечислены по порядку. Это позволяет ускорить поиск.
Вторая оптимизация. Поскольку данная позиция помечена как True, удалите ее и все позиции перед ней с тем же значением из словаря местоположений. (Либо они уже помечены как «Истина», либо никакая более поздняя позиция в B не может привести к тому, что они будут помечены как «Истина».)
С этими оптимизациями это становится O(n). И поэтому с 10^5 элементами у вас не возникнет проблем.
Спасибо! Могу ли я узнать, каков был ваш ход мыслей? Я начал с примера наблюдения и на основе наблюдений попытался обобщить условия, которые должны удовлетворяться для каждого A[i]. При таком подходе у меня никогда не возникнет идея, подобная вашей. Как ты начал?
@Szyszka947 Szyszka947 Я начал изучать прием динамического программирования для создания структуры данных, которая может реконструировать решения. См. stackoverflow.com/questions/78498209/… для этого. Затем я понял, что вам не нужен весь шаблон соответствия — просто то, что может идти куда. Потом я понял, что самое раннее-позднее подойдет. Затем я начал думать об оптимизации этого.
Подумайте об этом на math.stackexchange.com или Computerscience.stackexchange.com - здесь это не совсем по теме, поскольку это не вопрос программирования, а скорее вопрос математических/теоретических концепций.