Zadanie Palindrom OIG

Question

Natknalem sie na zadanie palindrom z finalu OIG-a https://szkopul.edu.pl/problemset/problem/LWN4TDpmrwD5fLos0ajgFyRD/site/?key=statement

Kompletnie nie wiem ja to zrobić. Ma ktoś jakiś pomysł.

Z góry dziękuję za poświęcony czas!

Comments

Ale czego nie rozumiesz dokładnie?

---

W sensie nie mam pomysłu jak to zrobić innaczej niz O(2^n) sprawdzajac kazdy mozliwy fragment

---

2^8 nie da ci 4.

To coś nie tak.

 

A tu nie trzeba napisać algorytm do wyliczenia a w zasadzie do zbudowania palindromy z listy dostępnych cyfr  budujesz wszystkie możliwe palindromy zbierasz w tablicy a potem sprawdzasz który ma największą długość.

---

Nie mozesz przeciez wygenerowac wszystkich palindromów bo ich jest zdecydowanie zawiele dokładnie 2^n, bo n <= 200000

---

@Michał Kazula, 

Jakie 4? w sensie 4pkt? czy ocenę w szkole? Ja robie te zadania, bo przygotowywuję się do OIJ i OI, a nie do szkoły xD Nie wiem czy znajdziesz w polsce szkołę podstawową przygotowywująca do OIJ-a.

---

Skąd masz O(2^n)  ?

---

Z zbioru wejsciowego generujesz kazdy mozliwy podzbior maskami bitowymi lub na kolejce. I tych podzbiorów masz 2^n - 1 i kazdy z nich sprawdzasz czy jest palindromem. Co ciekawe napisałem to teraz i przeszło nawet na 30pkt. Ogólnie zauważyłem, że w zadaniach z generowaniem podzbiorów takie maski bitowe / backtracking czasem daja jakies zazwyczaj 10,20 pkt, wiec podczas zawodow zawsze warto napisac. A nawet było zadanie liczby silne z finalu 15 OIJ-a, gdzie wzorcowka to byly maski bitowe. Podejrzewam, ze tu wchodzi jakis dynamik, tylko nie mam pomyslu jaki. Masz jakiś pomysł? Kod:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n = 0, wczytana_liczba = 0, max_wyn = 0;
bool czy_jest_palindromem = true;
vector<int> liczby;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        liczby.push_back(wczytana_liczba);
    }

    for (int i = 0; i < pow(2,n); ++i)
    {
        vector<int> idx_wziete;
        czy_jest_palindromem = true;
        for (int j = 0; j < n; ++j)
        {
            auto b = (1 << j) & i;
            if (b)
            {
                idx_wziete.push_back(liczby[j]);
            }
        }
        if (idx_wziete.size() % 2 == 0)
        {
            for (int j = 0; j < idx_wziete.size() / 2; ++j)
            {
                if (idx_wziete[j] != idx_wziete[idx_wziete.size()-j-1])
                {
                    czy_jest_palindromem = false;
                    break;
                }
            }
            if (czy_jest_palindromem == true)
            {
                max_wyn = max(max_wyn,(int)idx_wziete.size());
            }
        }
    }

    printf("%d",max_wyn);

    return 0;
}

Answer 1

Można spróbować ulepszyć klasyczny algorytm znajdowania najdłuższego podciągu będącego palindromem. Zobacz że do dp dodajemy 2 wtedy gdy arr[l] == arr[r], inaczej bierzemy maksa z wcześniej policzonych dp. Skorzystajmy z tego, że jest co najwyżej 10 takich samych liczb. Dla każdej liczby rozpatrzmy wszystkie takie pary tej liczby z samą sobą (będzie ich maks ok. 100). Jeśli pierwsza liczba z pary jest na pozycji l, a druga na r to szukamy innej pary l', r' dla której policzyliśy już wcześniej wynik i l < l', r' < r i ze wszystkich takich par (l', r') szukamy takiej dla której długość powstałego palindormu była największa i dodajemy 2. Pytanie w jakiej kolejności przechodzić po tych parach. Wydaje mi się że posortowanie po r i zrobienie na tym drzewa przedziałowego (maks na przedziale) powinno wystarczyć.

Comments

Napisałem na podstawie rozwiązania 3 dynamika w O(n^2 * log n) -> dp[i][j] max wyn na przedziale od i do j. I dp[i][j] = max(dp[i][j-1], dp[idx pierwszego rownego liczby[j] o idx-ie > i oraz < j + 2) i ten idx szukam binarnie. Przeszło na 60pkt.

Nie rozumiem jeszcze do końca o co Ci chodzi. Mówisz o tym rozwiązaniu nr 1?

---

Te wszystkie 3 rozwiazania opisują ten sam pomysł i ja wymysliłem jak ten pomysł przyspieszyć korzystając z tego, że mamy maks 10 takich samych liczb. Ty napisałeś troche inny algorytm, ale też poprawny

---

Dobra przeszło na 100.

Super to wytłumaczyłeś. To wystarcza do O(n log n) Raczej bym tego nie wymyślił. Opiszę teraz jeszcze szczególy implementacyjne.

Tworzymy te pary tych samych jak pisałeś wydaje mi się, że może być ich maksymalnie (1+9) /2*9 = 45. Dla każdego koloru. Sortujemy te pary. Ja posortowałem po początkach (przetwarzam od jak najwiekszy poczatków) I robimy drzewo przedzialowe na końcach. (maksów jak pisałeś). Dzieki temu mamy zagwarantowane, że przetwarzajac l,p nie ma żadnych początków mniejszych, ale są 2 problemy: możemy trafić na inne pary ktore maja ten sam poczatek, lub inne pary, ktore maja wiekszy koniec. Wiekszy koniec latwo obchodzimy majac vector jaki idx w drzewie przedzialowym ma i-ta para. i przesuwamy sie poprostu w lewo (jesli drzewo przedzialowe jest od najmniejszych koncow) i jak znajdziemy mniejszy koniec, to juz wiemy,gdzie robic querry. Jest jeszcze problem, ze w tym przedziale moga wychodzic z tego samego elementu (pary 1 3, 1 2), wiec mam vector na jakich idx-ach w drzewie przedzialowym sa poczatki x i w momencie gdy sprwadzam element l p, to wszystkie elementy o tym samym poczatku ustawiam wartosc na 0, zeby nie zaburzyc maxa na przedziale, po zrobieniu querry dla pary[i], wracam im stare wyniki. W ten sposob mamy zapewnione, ze sprawdzajac l,p nie bedzie l' <= l oraz p' >= p. I na koniec wynik to querry z calego drzewa.

Teraz jescze zlozonnosc. Skonstruowanie par to około co najwyżej 10^6 operacji, bo n <= 2 * 10^5 posortowanie i drzewa przedzialowe dzialają w O(n log n), wiec cale rozwiazanie ma O(n log n)

Zadanie jest bardzo trudne, kod jak ktos by sie kiedys meczyl:

https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OIG/palindrom_100pkt_dynamik.cpp

Whistleroosh Bardzo dziękuję za pomoc!!! Wydawało się kosmiczne na początku a jakoś poszło. Napisalem tez tego dynamika w O(n^2) i okazalo sie ze w tym moim rozwiazaniu O*n^2*log n) ten binary search nie był potrzebny, bo brałem to z max-a z wczesniejszych. Tak jak pisalo na tej stronie w rozwiazaniu 3.

Skorzystam jeszcze z okazji, znasz może jakieś zadania na dynamiki 1d, 2d, bo to O(n^2), bylo zdecydowanie do wymyslenia. 

Jeszcze raz bardzo dziękuję!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

---

Dzięki :) Odnośnie zadania na dynamiki wielowymiarowe. Jeśli nie widziałeś jeszcze to jest jedno fajne zadanie: https://szkopul.edu.pl/problemset/problem/VaX9P0Q-I4UOuOaBDyML-wMK/site/?key=statement