Калиндром

Калиндром и его решение

Xaydarov Zafar AlamovichPRO 19 Oktabr 2026 · 3 daqiqa o‘qish 6 2

# Разбор задачи 1610B (Codeforces)

Что же, сегодня пройдем и решим задачу 1610B.
Задачка на two pointer ([https://codeforces.com/contest/1610/problem/B](https://codeforces.com/contest/1610/problem/B))

---

Первые мысли

В начале я пытался написать код через temp:

пройтись по массиву;
если s[l] != s[r], то сохранить их индексы в temp и проходить через цикл, выбрав r как target и l как target.

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

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

---

Наблюдение 1: «Некоторые» равносильно «Все»

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

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

Следовательно, задача сводится к вопросу: существует ли такое число x, что после удаления всех его вхождений массив становится палиндромом?

---

Наблюдение 2: Кандидатов на x всего два

Запустим два указателя с краёв массива: l = 0 и r = n - 1.
Пока a[l] == a[r], сдвигаем l вправо, а r влево.

Если l \ge r, то массив изначально является палиндромом \rightarrow ответ YES.
Если мы нашли первое несовпадение a[l] \ne a[r], то число x обязано быть либо a[l], либо a[r].

Доказательство: До этого момента префикс и суффикс были зеркально равны. Если мы выберем число x, отличное и от a[l], и от a[r], то ни a[l], ни a[r] удалены не будут, и они встретятся на симметричных позициях в результирующем массиве, нарушив палиндромность.

---

Реализация (Код)

Поняв это, мы можем смело писать код.

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(map(int, input().split()))
    l = 0
    r = n - 1
    ans = []
    
    if s == s[::-1]:
        print("YES")
    else:
        while l < r:
            if s[l] == s[r]:
                l += 1
                r -= 1
            else:
                # Пробуем удалить все вхождения s[r]
                ans = [s[i] for i in range(n) if s[i] != s[r]]
                if ans == ans[::-1]:
                    print("YES")
                    break
                else:
                    ans.clear()
                    # Пробуем удалить все вхождения s[l]
                    ans = [s[i] for i in range(n) if s[i] != s[l]]
                    
                if ans == ans[::-1]:
                    print("YES")
                    break
                else:
                    print("NO")
                    break