Revizia anterioară Revizia următoare
'Solutia' pentru problema 'Permdist':
Subtaskurile 1-3, 20 puncte:
Putem, pentru fiecare zi, lista birourile vizitate de cei doi în acea zi în doi vectori diferiţi. Răspunsul este numărul de poziţii unde valorile coincid în cei doi vectori.
Subtaskul 4, 36 puncte:
Notăm cu 'd(T, x, y)' (distanţa în T de la x la y) ca numărul de ori necesar de a aplica x = T[x] până când x devine egal cu y. Dacă asta este imposibil, 'd(T, x, y) = -1'.
Să descompunem cele două permutări în cicluri.
Observaţie (1): în ziua x, cei doi se vor întâlni în y dacă şi numai dacă x şi y aparţin aceluiaşi ciclu şi în A, şi în B.
Reformulare (2): Dacă în fiecare ciclu am desemna un reprezentant (aleator), iar pentru fiecare valoare x din ciclul respectiv am nota distanţa acestuia de la reprezentant cu 'DA[x]' pentru permutarea A, respectiv 'DB[x]' pentru permutarea B, iar cu 'LA[x]' şi 'LB[x]' lungimea ciclului căruia aparţine x în A, respectiv în B, atunci în ziua x cei doi se văd în y dacă şi numai dacă aparţin aceluiaşi ciclu în ambele permutări, şi '(DA[y] - DA[x]) mod LA[x] = (DB[y] - DB[x]) mod LB[x]'.
Cum pentru toate numerele 'LA[x] = LB[x] = N', putem asocia fiecărei valori x câte un coeficient 'C[x] = (DA[x] - DB[x]) mod N'. Pentru fiecare x, numărul de y unde cei doi se vor întâlni este egal cu numărul de valori y a.i. 'C[x] = C[y]' cum '(DA[x] - DB[x]) mod N = (DA[y] - DB[y]) mod N <=> (DA[y] - DA[x]) mod N = (DB[y] - DB[x]) mod N', iar din din (2) aceasta este corect. Se poate utiliza un vector de frecvenţă pentru calcularea numărului de valori y care au 'C[y] = C', 'C' fiind variabil după x. Complexitate timp (şi memorie): O(N)
Motivul pentru care o asemenea soluţie nu funcţionează pe cazul general este datorită inabilităţii de a pune valorile care depind de x respectiv y de aceeaşi parte a parantezei aşa cum este formulat în (2), cum cele două părţi ale egalităţii se pot afla sub modulo-uri diferite. Încercări de a lucra peste mulţimea valorilor y care sunt în acelaşi ciclu ca x şi pentru care se fixează o ierarhie între valorile din diferenţe (adică y să respecte că 'DA[x] < DA[y]', 'DB[x] < DB[y]', şi restul de combinaţii de semne), astfel încât ecuaţia de la (2) să aibă ambele părţi ale egalităţii ca ecuaţii în Z pot duce la o soluţie în O(N * log(N)) care ar putea trece pe Subtaskul 5.
Subtaskul 6, 100 puncte:
Să grupăm valorile după ce cicluri aparţin în cele două permutări, şi să luăm o mulţime de astfel de numere, S (care aparţin aceluiaşi ciclu în ambele permutări). Fie 'Cycle(T)' un şir astfel încât scrierea fiecărui ciclu din T ca elemente consecutive din acesta este o subsecvenţă din 'Cycle(A)'. Exemplu: pentru T = [5, 3, 2, 1, 4], 'Cycle(T)' poate fi egal şi cu [5, 4, 1, 3, 2], şi cu [2, 3, 1, 5, 4]. Nu contează valoarea efectivă atâta timp cât se păstrează proprietatea menţionată anterior. Fie o valoare r pentru care vrem să calculăm răspunsul. Pentru fiecare valoare a din S, să considerăm poziţia acesteia din 'Cycle(B)', ca 'I[a]'. Să punem un marker într-un vector paralel cu 'Cycle(B)' pe poziţia 'I[a] - d(A, r, a)' pentru fiecare a. Este clar că numărul de markere de pe poziţia 'I®' include un mare număr de elemente din soluţia noastră. Singura problemă vine de la valorile u care au 'I[u] < I®', 'I[u] + DB[u] - d(A, r, u) = I®' (În termeni mai familiari, 'u' ar ajunge la 'r' "prin spatele ciclului din B"). Pentru a repara această, sugerăm lucrarea pe un vector similar lui 'Cycle(B)', dar care ar repara această problemă. Introducem noţiunea şirului 'Cycle2(B)', a cărui definiţie este similară, doar că scrierea fiecărui ciclu (ca elemente consecutive din parcurgerea acestora) este scrisă de două ori (în aceeaşi ordine de fiecare dată). Exemplu: pentru T = [5, 3, 2, 1, 4], 'Cycle(T)' poate fi egal şi cu [5, 4, 1, 5, 4, 1, 3, 2, 3, 2], şi cu [2, 3, 2, 3, 1, 5, 4, 1, 5, 4]. Din nou, nu contează cu care variantă lucrăm atâta timp cât se păstrează aceste proprietăţi. Continuăm cu noţiunea markerelor, doar că pentru fiecare valoare a din S, punem un marker cu 'd(A, r, a)' poziţii înapoi relativ de fiecare apariţie a acesteia din 'Cycle2(B)'. Acum, este clar că existenţa problematică a unui u menţionat anterior este reparată de apariţia acestuia la cele 'DB[u]' unităţi mai în faţă în şir (într-atât ca (3) se respectă). Acum, structura dată (a markerelor) ne poate răspunde corect la queryuri. Singura problemă este că aceasta este (în momentul de faţă) descrisă ca să poată să răspundă corect (4) doar la queryuri privind pe r. Trebuie să reparam asta. Să presupunem că avem la îndemână un r' care respectă că pentru orice alt a în S, 'a != r', avem că 'd(A, r, a) ≥ d(A, r, r')'. Atunci, poziţiile markerelor se vor schimba (dacă vrem să adaptăm structura noastră de date la a răspunde la queryuri pentru r') asemenea:
Markerele care proveneau de la valoarea r se duc cu 'd(A, r', r)' poziţii în urmă.
Toate celelalte markere se duc cu 'd(A, r, r')' poziţii în faţă.
Pentru a putea acomoda aceste operaţii, putem folosi trucul detaliat mai atent aici: (Un vector de frecvenţă pe care menţinem o variabilă globală de lazy care indică cum trebuie să modificăm celelalte valori cu respect faţă de operaţiile de tipul 2).
