• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Palindrom OIG

VPS Starter Arubacloud
+1 głos
308 wizyt
pytanie zadane 30 grudnia 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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!
komentarz 30 grudnia 2022 przez Michał Kazula Pasjonat (19,540 p.)
Ale czego nie rozumiesz dokładnie?
komentarz 30 grudnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
W sensie nie mam pomysłu jak to zrobić innaczej niz O(2^n) sprawdzajac kazdy mozliwy fragment
komentarz 30 grudnia 2022 przez Michał Kazula Pasjonat (19,540 p.)
edycja 30 grudnia 2022 przez Michał Kazula
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ść.
komentarz 30 grudnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Nie mozesz przeciez wygenerowac wszystkich palindromów bo ich jest zdecydowanie zawiele dokładnie 2^n, bo n <= 200000
komentarz 30 grudnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@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.

komentarz 30 grudnia 2022 przez Michał Kazula Pasjonat (19,540 p.)
Skąd masz O(2^n)  ?
komentarz 31 grudnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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;
}

1 odpowiedź

+2 głosów
odpowiedź 31 grudnia 2022 przez Whistleroosh Maniak (56,980 p.)
wybrane 17 lutego 2023 przez pasjonat_algorytmiki
 
Najlepsza

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ć.

komentarz 31 grudnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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?
komentarz 31 grudnia 2022 przez Whistleroosh Maniak (56,980 p.)
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
1
komentarz 1 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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ę!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

komentarz 2 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)
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

Podobne pytania

0 głosów
0 odpowiedzi 466 wizyt
pytanie zadane 16 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
2 odpowiedzi 407 wizyt
pytanie zadane 28 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 172 wizyt
pytanie zadane 24 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,775 zapytań

141,702 odpowiedzi

320,553 komentarzy

62,109 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...