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

Zadanie Klasy finał OIG

VPS Starter Arubacloud
0 głosów
521 wizyt
pytanie zadane 18 lutego 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/qnmBwED8E2cCDmRfeyDun104/site/?key=statement

Napisałem bruta na 30pkt, zauważając, żę kandydat na dlugośc skoku, musi być liczbą pierwszą, więc dla każdego kandydata, w czasie liniowym liczę jaki jest wynik. Niestety pesymistyczna złożonność to O(N^2), bo liczb pierwszych do N, jest baardzo dużo.

Kod:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, max_wyn = 0, wyn = 0;
string ciag;
vector<bool> sito;
vector<int> F;
vector<int> P;
vector<int> idxy_jedynek;

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

    cin >> n >> ciag;
    sito.assign(n+1,false);
    for (int i = 0; i < n; ++i)
    {
        if (ciag[i] == '#')
            idxy_jedynek.push_back(i);
    }
    if (idxy_jedynek.size() == 0)
    {
        printf("0");
        return 0;
    }
    if (idxy_jedynek.size() == 1)
    {
        printf("1");
        return 0;
    }
    for (int i = 2; i <= n; ++i)
    {
        if (sito[i] == false)
        {
            P.push_back(i);
            for (int j = i * i; j <= n; j += i)
                sito[j] = true;
        }
    }
    for (int i = 0; i < P.size(); ++i)
    {
        wyn = 0;
        vector<int> stat(P[i],0);
        for (int j = 0; j < idxy_jedynek.size(); ++j)
        {
            stat[idxy_jedynek[j] % P[i]]++;
            wyn = max(wyn,stat[idxy_jedynek[j] % P[i]]);
        }
        max_wyn = max(max_wyn,wyn);
    }
    printf("%d",max(1,max_wyn));
    return 0;
}

Ma ktoś pomysł jak to przyśpieszyć?

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

1
komentarz 18 lutego 2023 przez Whistleroosh Maniak (56,980 p.)
A w sumie racja, źle policzyłem złożonosć. Im więcej różnych kandydatów na skok tym mniej kamyków, więc to będzie miało złożoność około-liniową
1
komentarz 18 lutego 2023 przez Whistleroosh Maniak (56,980 p.)
To że to działa wynika z Twojej obserwacji, że dla k!=2 będziemy kolejno na polach o różnej parzystości. Załóżmy że istnieje takie k > 2, że przy skokach długości k odwiedzamy najwięcej kamyków, ale nie istnieją takie 2 kamyki, że odległośc między nimi wynosi k. Załózmy że skaczemy po polach 0, k, 2*k itd. oraz na kazdym z tych polu był kamyk (trzeba jakoś rozszerzyć ten dowód na przypadki gdy nie było kamyka). Z założenia wynika, ze w (1, k), (k, 2*k) itd. jest co najmniej jeden kamyk. Po wykonaniu wszystkich skoków odwiedziliśmy p kamyków na polach parzystych i n na nieparzystych. mamy |p-n| <= 1 Tak samo liczba kamyków nad którymi "przeskoczyliśmy" to co najmniej n + p - 1. No i teraz trzeba zauważyć że tych kamyków nad którymi przeskoczyliśmy (powiedzmy że jest ich n2 na polach nieparzystych i p2 na polach parzystych) jest na tyle dużo że zamiast skakać co k, możemy albo skakać po wszystkich nieparzystych polach albo parzystych i wetdy odwiedzimy p + p2 lub n + n2 kamyków i to nie jest mniejsze niż n + p
1
komentarz 18 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
No trzyma to się całości. Bardzo fajne zdanie, dzięki!
komentarz 19 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
*zadanie
komentarz 5 marca 2023 przez dominikwaw Użytkownik (560 p.)

@Whistleroosh, nie jest to prawda, że kandydatami na długość skoku są 2 oraz odległości pomiędzy sąsiednimi kamieniami. Np. dla testu
13
##.#........#

optymalna długość skoku to 3, co z pewnością nie jest ani dwójką, ani odległością pomiędzy sąsiednimi kamieniami.

2 odpowiedzi

+1 głos
odpowiedź 6 marca 2023 przez dominikwaw Użytkownik (560 p.)
wybrane 6 marca 2023 przez pasjonat_algorytmiki
 
Najlepsza

Przypomniałem sobie wspomniane wcześniej liniowe rozwiązanie.

Niech k będzie łączną liczbą kamieni. Okazuje się, że jednego kandydata na skok można sprawdzić w czasie O(k) (sprawdzić, czyli policzyć ile najwięcej kamieni da się zebrać wykonując daną długość skoku). Wystarczy przeiterować się po pozycjach kamieni, jeśli kamień jest na pozycji i, to zwiększamy w tablicy do zliczania komórki o indeksie i % d, gdzie d jest długością aktualnego skoku.

Przydatna będzie możliwość czyszczenia tej tablicy w czasie stałym. Jest to dosyć znana sztuczka, która polega na tym, aby w każdej komórce oprócz jej wartości, trzymać jeszcze jakieś id, które będzie świadczyło o tym czy komórka ta jest aktualna. Wtedy żeby wyczyścić tablicę wystarczy zwiększyć ostatnie id.
 

template<typename T>
class count_table {
private:
	uint32_t last_id;
	std::vector<T> value;
	std::vector<uint32_t> id;
	
public:
	count_table() : last_id(0), value(), id() {}
	
	count_table(uint32_t n) : last_id(0), value(n), id(n) {}
	
	T & operator [] (uint32_t i) {
		if (id[i] != last_id) {
			value[i] = 0;
			id[i] = last_id;
		}
		return value[i];
	}
	
	void clear() {
		last_id++;
	}
};


No dobrze, ale kandydatów dalej jest potencjalnie O(n), więc łącznie mielibyśmy złożoność O(nk)... Otóż nie, okazuje się że kandydatów jest jedynie O(n / k)! Przypuśćmy, że pewne d jest kandydatem na długość skoku. Wtedy po pierwszym skoku będziemy co najmniej na pozycji d, po drugim co najmniej na pozycji 2d, po trzecim co najmniej na pozycji 3d, itd.

Przypomnę że wynik wynosi co najmniej k / 2 (wykonując skok długości 2), zatem żeby go poprawić, musielibyśmy skoczyć co najmniej k / 2 razy, a bylibyśmy wtedy gdzieś na pozycji kd / 2 lub dalej. Naturalne jest więc że zachodzi kd / 2 <= n, co prowadzi do wniosku d <= 2n / k, czyli mamy jedynie 2n / k = O(n / k) kandydatów do sprawdzenia! Każdego sprawdzamy w czasie O(k), zatem łączna złożoność to O(k · n / k) = O(n).

komentarz 6 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Super rozwiązanie, czyli poprostu wzięcie, tego co napisałem na samym początku w O(N*K), i zredukowanie kandydatów tym spostrzerzeniem wsm jak się teraz na to popatrzyłem, to to spostrzerzenie wydaje się być banalne.....

Co ciekawe, bez tego triku z pamiętaniem co było wcześniej(w sensie z clearowaniem vectora stat z modulo), wchodzi na 50pkt. A z przyśpieszeniem na 100 z ponad 10 krotnym zapasem.

Takie zadania lubię najbardziej. Bardzo trudno wymyśleć pomysł, a jak się wymyśli, to się zdaje sprawę, że był banalny......
komentarz 6 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Ale niewątpliwie testy są słabo dobrane do tego zadania, jak jest ich dużo i nie wychwyciły błędu w tym algorytmie pierwszym.
+3 głosów
odpowiedź 5 marca 2023 przez dominikwaw Użytkownik (560 p.)
Z czasów gdy sam startowałem w tej olimpiadzie pamiętam, że ktoś mówił o liniowym rozwiązaniu tego zadania. Niestety nie mogę go sobie przypomnieć.

Rozwiązanie, które wymyśliłem jest następujące:

Oznaczmy pozycje, na których znajdują się kamienie przez a_1, a_2, ..., a_k. Zauważmy, że odpowiedź wynosi co najmniej k/2 i możemy ją uzyskać przy długości skoku 2. Wynika z tego, że jeśli weźmiemy losowy kamień, to prawdopodobieństwo, że jest on zebrany w optymalnym rozwiązaniu wynosi co najmniej 50%.

Powtórzmy więc kilkanaście razy następującą procedurę (będziemy wtedy mogli z dużą pewnością stwierdzić, że choć raz trafiliśmy na kamień z optymalnego rozwiązania):

Niech i będzie losową liczbą ze zbioru {1, 2, ..., k}. Chcemy znaleźć maksymalne rozwiązanie zawierające i-ty kamień. Niech d_j = |a_i - a_j| będzie odległością pomiędzy i-tym a j-tym kamieniem.Interesuje nas znalezenie takiej długości skoku p (łatwo zauważyć, że długość ta może być pierwsza), aby jak najwięcej spośród, d_1, d_2, ..., d_k było podzielne przez p.

Dla każdej d_j oraz każdego jej czynnika pierwszego q chcemy zwiększyć liczność liczb podzielnych przez q o 1, co możemy zrealizować zwyczajnie inkrementując komórkę tablicy do zliczania o indeksie q. Pytanie jak takie czynniki pierwsze wyznaczyć? Można to zrobić np. wykorzystując Sita Eratostenesa.

Łączna złożoność to będzie O(n · log(n) · liczba_prób). Limity na tym zadaniu są dosyć ciasne, ale mi akurat liczba_prób = 10 wystarczyła.
komentarz 5 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
fajne rozwiązanie, pierwszy raz spotykam się w zadaniu, z pomysłem, korzystający z losowości.
komentarz 5 marca 2023 przez Whistleroosh Maniak (56,980 p.)
Ciekawe rozwiązanie. Nie spodziewałem się że zadanie z OIG będzie korzystać z prawdopodobieństwa do wzorcówki. Dotychczas tylko na OI takie zadania widziałem
komentarz 5 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Skoro istnieje rozwiązanie liniowe, to ciekawe jakie.......

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,703 odpowiedzi

320,557 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!

...