Soluţii Algoritmiada 2014 Runda 3

• Lista de probleme
• Perioada2
• Progresii2
• Sliding Window
• Potriveala
• Reborn
• Marsmusic

Perioada2

Presupunem ca sirul este indexat de la 1. Calculam Functia de prefix pe sirul nostru. Astfel, π[n] = k ⇔ s₁s₂...s_k = s_n-k+1s_n-k+2...s_n. (adica primele k caractere sunt egale cu ultimele k). In consecinta, perioada "minima" a sirului are lungime n - k. Deci rezultatul nostru reprezinta numarul de numere naturale x astfel incat n este divizibil cu (n - k) * x. Este suficienta o simpla iterare de la 1 la sqrt(n) pentru a gasi numarul lor.

Complexitate: O(sqrt(N)).

Progresii2

Sliding Window

Potriveala

Din păcate, la această problemă se pot obţine destul de multe puncte folosind soluţii care nu garantează întotdeauna răspunsul corect (vezi aici). Cu ocazia aceasta, reamintim utilizatorilor infoarena că fiecare contribuţie este importantă şi binevenită, printre altele îmbunătăţirea testelor din arhivă.

Soluţie 1 (60-70 puncte):

Se observă că răspunsul este dat de o funcţie monotonă descrescătore şi trebuie găsit maximul acesteia (dacă răspunsul este o subsecvenţă de lungime L atunci şi una de lungime L-1 constituie un candidat).

Aşadar, căutăm binar răspunsul (fie el L). Rămâne de văzut cum se poate face verificarea în O(N + M):
O variantă este obţinerea codurilor hash celor N-L subsecvenţe de lungime L din şirul A şi inserarea lor intr-o structură de date ce permite căutarea elementelor într-un timp constant (vezi unodered_map ), fie ea H. După acest pas, se generează codurile hash de lungime L şi pentru şirul B (primele subsecvenţe de lungime L: B₀...B_L-1, B₁..B_L, B₂...B_L+1, etc) iar dacă s-a găsit vreun cod în structura H atunci există cu siguranţă o subsecvenţă periodică de lungime L comună şirurilor A şi B.

Complexitate finală: O((N + M) * log N)

Soluţie 2 (100 puncte):

În caz că nu sunteţi familiari cu algoritmul Z recomandăm înţelegerea articolului prezent pe Codeforces. Algoritmul Z oferă în timp liniar pentru fiecare poziţie i dintr-un şir S lungimea maximă a prefixului S₀ egal cu prefixul ce începe de la poziţia i din S.
Ca exerciţiu, încercaţi să rezolvaţi problema folosindu-vă de ieşirea algoritmului Z pe sufixul lui B, prefixul lui B, legându-vă în acelaşi timp şi de şirul A

Din cauza restricţiei din enunţ, garantându-se obţinerea unei subsecvenţe comune de lungime cel puţin M, răspunsul poate fi scris ca: (sufix al lui B) + B + B + ... + B + (prefix al lui B). În continuare concatenăm şirul B cu el însuşi până când obţinem un şir de lungime cel puţin N.
Cu ajutorul algoritmului Z, putem calcula prefixul de lungime maximă a noului şir B care se potriveşte cu sufixul i a lui A, respectiv sufixul de lungime maximă a lui B (prefix_i, sufix_i).
Răspunsul la problemă va fi max(sufix[i] + prefix[i+sufix[i]]).

Complexitate finală: O(N + M)

Marsmusic

Reborn

Problema cere să se determine pentru o mulţime de puncte a, b, numărul minim de intervale parcurse din punctul a pentru a ajunge în punctul b.
Pentru început se poate preprocesa pentru fiecare punct P ( 1 ≤ P ≤ N ) cel mai din dreapta punct pentru care se parcurge un singur interval (să-l numim next[P]). Acest lucru poate fi uşor de realizat prin folosirea unui set : menţinând la fiecare pas i intervalele care au capătul din dreapta Y[j] >= X[i].

Având pentru fiecare punct P, next[P] construim un tabel semnificând punctul cel mai din dreapta, parcurgând 2^j intervale. Iniţial, =next[P], relaţia de recurenţă fiind asemanătoare cu cea de la problema RMQ .

Un query de tipul a,b cu a ≤ b se poate rezolva căutând binar răspunsul răspunsul (vezi problema strămoşi) încercând la fiecare pas determinarea celui mai semnificativ bit pentru care maxPoint[a][j] <= b.

Complexitatea algoritmului:
Timp: O(M log M + N log M + Q * log N), Memorie: O(N log N) .

Despre articol

Acest articol a fost scris de Dragos-Alin Rotaru •mathboy inspirat din forum postul lui Heidelbacher Andrei •a_h1926. în principiu, este o descriere mai detaliată a soluţiilor oficiale, oferind şi câteva indicaţii alternative.