Zadanie Klasy finał OIG

Question

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!

Comments

Nie przychodzi mi na myśł żaden oczywisty algorytm, więc może to zadanie na jakąś obserwację. Np. jesteśmy w stanie ograniczyć długość skoku w zależności od tego ile jest kamyków. I wtedy w zalezności od tej liczby możemy wybrać inny algorytm. Albo jeśli kamyków jest >= sqrt(n) to wynik będzie jakiś bardzo mały. Zdarzało mi się robić zadania tego typu i wtedy przeważnie korzystało się jakoś z pierwiastka

---

1* Ja jeszcze wymyśliłem, coś takiego, że zawsze, niezależnie od K, zaczynamy skakanie, z jakiegoś kamyka -> nie opłaca nam się zacząc z pola pustego.

2* zawsze można wziąć max z sumy kamyków na polach parzystych, i maxa na polach nieparzystych => nie możemy wykonać < niż max z tych 2 sum skoków, dla każdego k != 2

---

3* Zawsze jak bierzemy k != 2, to będziemy skakać kolejno po parzystych, nieparzystych, parzystych, nieparzystych.... (lub odwrotnie, jak zaczniemy od nieparzystych)

---

Zrobiłem mały test i chyba kandydatami na długość skoku jest albo 2 albo odległość między którymiś kolejnymi kamykami

---

Załóżmy, że by tak było, to i tak kandydatów mamy N.

---

A no nie. Właśnie sprawdziłem i jesli pamiętasz dla których odległości już policzyłes i nie liczysz ponownie to przechodzi na 100 :)

---

W sensie? Da się szybciej niż w czasie O(N), sprawdzić kandydata?

---

Nie. Po prostu uruchomiłem to co napisałeś dla kandydatów i przeszło

---

Aha, ok, bo tych odległości będzie mało.

---

Być może testy były kiepskie, kandydatów w najgorzszym wypadku będzie sqrt(n) więc to działa w O(nsqrt(n)). Ale ciekawe czy da się to rozwiązać szybciej

---

Można też próbować rozkładać te odległości na liczby pierwsze i wtedy kandydatami byłyby te liczby pierwsze. To trochę przyspieszy rozwiązanie, ale nie wiem jak bardzo. Chyba że rozkład będzie zajmował za długo, to wtedy spowolni

---

@Whistleroosh, 

Przeszło na 100pkt, a wiesz czemu to działa (w sensie; sprawdzamy kandydatów jedynie o odleglosciach, między kolejnymi kamieniami)?

---

@Whistleroosh, 

Raczej mało prawdopodobne, żeby testy były kiepskie, bo ich tam jest chyba koło 100, a wszędzie przechodzi w co najwyżej około 1/10 czasu.

---

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ą

---

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

---

No trzyma to się całości. Bardzo fajne zdanie, dzięki!

---

*zadanie

---

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

Answer 1

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

Comments

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

---

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.

Answer 2

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.

Comments

fajne rozwiązanie, pierwszy raz spotykam się w zadaniu, z pomysłem, korzystający z losowości.

---

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

---

Skoro istnieje rozwiązanie liniowe, to ciekawe jakie.......