Редакция для Палиндромная последовательность

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

1. Идея

Нужно проверить, совпадает ли последовательность с самой собой при чтении справа налево.

Такая последовательность называется палиндромом. Для этого достаточно сравнивать элементы, стоящие на одинаковом расстоянии от начала и от конца:

первый с последним,
второй с предпоследним,
и так далее.

Если хотя бы одна такая пара различается, ответ сразу NO. Если все пары совпали, ответ YES.

2. Наблюдения

Проверять всю последовательность полностью не нужно дважды. Достаточно пройти только до середины.
Для позиции i симметричная ей позиция с конца имеет индекс n - 1 - i.
Если n нечётно, средний элемент ни с чем сравнивать не нужно: он всегда симметричен сам себе.
Ограничение n <= 2 * 10^5 легко позволяет сделать простой линейный проход.

3. Алгоритм

Считать n.
Считать массив a из n чисел.
Для всех i от 0 до n // 2 - 1:
- сравнить a[i] и a[n - 1 - i];
- если они не равны, вывести NO и завершить программу.
Если цикл завершился без несовпадений, вывести YES.

4. Почему это работает

Последовательность является симметричной тогда и только тогда, когда для каждой позиции слева элемент совпадает с соответствующим элементом справа.

Алгоритм как раз проверяет это условие для всех нужных пар:

a[0] и a[n - 1],
a[1] и a[n - 2],
...
a[i] и a[n - 1 - i].

Если хотя бы для одной пары значения разные, последовательность не может читаться одинаково в обоих направлениях, значит ответ NO.

Если же все такие пары совпали, то левая половина полностью зеркально совпадает с правой, а значит вся последовательность является палиндромом, и ответ YES.

5. Сложность

Время: O(n), потому что делается один проход по половине массива.
Память: O(n) на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n / 2; i++) {
        if (a[i] != a[n - 1 - i]) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

ok = True
for i in range(n // 2):
    if a[i] != a[n - 1 - i]:
        ok = False
        break

print("YES" if ok else "NO")