Оптимизация медленного алгоритма

Question

Необходимо решить на с++ следующую задачу: можно ли отсортировать массив Аrr (по возрастанию), выполнив переворот ровно одного подотрезка (части массива) Аrr? Если да, вывести "yes" и индексы начала подотрезка.
В противном случае вывести "no". Подробнее https://codeforces.com/problemset/problem/451/B.

Мною был создан следующий алгоритм: Во вложенном цикле создаётся частично перевернутый по индексам переворота i и j(которые и перебираются во вложенном цикле) массив. При совпадении полученного таким способом массива Q и заранее отсортированного массива В выводятся индексы i и j. Ниже приведена функция переворота части массива.

Далный алгоритм работает правильно, но на одном из тестов (70+к размер массива) тестировщик выводит превышение лимита времени. Как значительно оптимизировать перебор индексов или функцию переворота части массива для уменьшения времени работы программы?
Функция переворота части массива:

vector<int> reverse(int l, int r, vector<int> A){
for(int i = l;i<=(l+r)/2;i++)
{
    swap(A[i],A[l-i+r]);
}
return A;
}

Если существенная оптимизация невозможна прошу привести более быстрый способ решения задачи.

c++алгоритм оптимизация

S.H. · Accepted Answer

Возможна следющая оптимизация.
Для того, чтобы вывести ответ, не нужно переворачивать массив.
Нужно просто пройтись по нему, и посчитать, сколько раз происходит смена "убывания-возрастания" значений. Это делается сравнением соседних элементов массива.
Тогда если такое изменение происходит 0, 1 или 2 раза - то "да", есть монотонный кусок массива, перевернув который Вы МОЖЕТЕ получить монотонно отсортированный массив. Если таких смен возрастания-убывания больше - уже не сможете.
Но при этом надо проверить дополнительное условие: что внутри мнотонного подотрезка все значения не меньше значений в одной строне от него и не больше значений в другой стороне.
Я надеюсь, что объяснил достаточно понятно.
Если не поможет - напишите в комментариях, я напишу код

tym32167 · Answer

Алгоритм простой.

Найти начало перевернутого участка
Найти конец перевернутого участка
Перевернуть
Проверить стал ли массив сортированным

Код будет примерно такой (C#)

    private static void Solve(int[] numbers)
    {
        int start = 0;
        int end = numbers.Length - 1;

        while (start < numbers.Length - 1 && numbers[start] < numbers[start + 1])
            start++;
        while (start > 0 && numbers[start] < numbers[start - 1])
            start--;

        while (end > 0 && numbers[end] > numbers[end - 1])
            end--;
        while (end < numbers.Length - 1 && numbers[end] > numbers[end + 1])
            end++;

        if (end < start) end = start;

        swap(numbers, start, end);

        for (int i = 0; i < numbers.Length - 1; i++)
        {
            if (numbers[i] > numbers[i + 1])
            {
                Console.WriteLine("no");
                return;
            }
        }

        Console.WriteLine("yes");
        Console.WriteLine("{0} {1}", start + 1, end + 1);
    }

Функция переворачивания

    private static void swap(int[] arr, int start, int end)
    {
        while (start < end)
        {
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
    }

Заодно отправил решение.

Оптимизация медленного алгоритма

2 Answers

Add your own answers!

Ask a Question