Editorial for Moćni Niza


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: milisav

Primetimo, prvo, da je optimalno da moć našeg niza ima 29 bit ukoliko je to moguće, zato što čak i kad bi moć imala sve ostale, manje bitove, oni bi se sumirali u 2^{29}-1. Potom treba da proverimo da li moć može da ima i 29 i 28 bit. Ukoliko to nije moguće, 28 bit možemo da ignorišemo i nastavimo dalje, a ukoliko jeste, zahtevaćemo da u rešenju uvek postoje ta dva bita. Dakle, možemo da nastavimo sa ovom procedurom, pohlepnog dodavanja bitova. Neophodno je da proverimo da li možemo da nađemo podelu u K segmenata, tako da moć niza sadrži neki podskup bitova S, tj. da li možemo da podelimo niz u K segmenata, tako da svaki segment sadrži bitove iz skupa S. Neka su pozicije numerisane od 0. Pronađimo za svaku poziciju i najmanje j, takvo da OR (cikličnog) segmenta [i,(i+j-1) mod N] sadrži sve bitove iz skupa S. Ovakvo j možemo pronaći binarnom pretragom. Neka je b[i] = j. Želeli bi da pronađemo da li je moguće napraviti podelu u segmente, tako da svaki segment sadrži bitove iz skupa S i tako da jedan segment počinje na poziciji i. Tada će jedan segment početi na poziciji i, naredni na poziciji (i+j) mod N itd. Ovo je moguće postići tehnikom binarnog stepenovanja (eng. binary lifting). Za svaku poziciju pronađemo vrednost s[i][j] - najmanja vrednost tako da ciklični segment [i,(i+s[i][j]-1) mod N] možemo podeliti na bar 2^j segmenata, tako da OR svakog segmenta sadrži sve bitove iz skupa S. Tada:

  • s[i][0] = b[i]
  • s[i][j] = s[i][j-1]+s[(i+s[i][j-1]) mod N][j-1] , j \geq 1

Kada pronađemo ove vrednosti, neophodno je da pronađemo za svako i najmanje l, tako da ciklični segment [i,(i+l-1)%n] možemo podeliti na K segmenata tako da OR svakog segmenta sadrži sve bitove iz skupa S. To možemo pronaći na sličan način kao i vrednosti matrice s. Ukoliko postoji i, takvo da je l \leq N, tada je moguće napraviti podelu na K segmenata tako da OR svakog segmenta sadrži sve bitove iz skupa S. Složenost opisanog algoritma je O(N \cdot log (max A_{i}) \cdot log N). Zadatak je preuzet sa \texttt{Moscow} \texttt{Autumn} \texttt{Workshop} \texttt{2019} \texttt{Day} \texttt{1}, takmičenje \texttt{Welcome} \texttt{Contest} \texttt{from} \texttt{Asia}.


Comments


  • 4
    Pajaraja  commented on April 5, 2020, 11:20 p.m.

    Miki samo nastavljaš da me oduševljavaš!