Soluţia problemei Shopping

Avem nevoie de două observaţii:

• Putem afla maximul dintre p[i] şi p[j] făcând un query între două stringuri A şi B unde B este plin de 'a'-uri, iar A este plin de 'a'-uri înafară de poziţiile i şi j care vor avea 'b'. Costul acestei operaţii va fi 2.
• Nu putem distinge în permutare elementele 1 şi 2. Totuşi, dacă aflăm celelalte elemente, atunci putem să spunem pe ce poziţie se află 1 şi pe ce poziţie se află 2.

Nota: De acum încolo, ne vom orienta după numărul de operaţii descrise mai sus, nu după suma costurilor stringurilor. De asemenea, definim funcţia queryMax(a, b) = max(p[i], p[j])

Subtaskul 1

La acest subtask merge orice soluţie de tip backtracking. Putem să facem nişte operaţii random ca după să încercăm să facem toate permutările şi să vedem care permutare corespunde cu operaţiile generate.

Subtaskul 2

La acest subtask putem să generăm maximul între oricare pereche de numere într-o matrice A[i][j] = max(P[i], P[j]). Ca să aflăm pe ce poziţie se află elementul maxim, trebuie să găsim linia sau coloana care este plină de maximul respectiv. După ce deducem că maximul se află pe poziţia i, excludem linia şi coloana i din matrice şi continuăm până când ajungem la o matrice 2×2.

Subtaskul 3

La această soluţie putem încerca orice soluţie ce foloseşte căutarea binară. Să zicem că noi am aflat pe poziţiile de la 1 până la x toate elementele şi ştim şi în ce ordine sunt. Pentru elementul x + 1 putem afla între care dintre elemente se află făcând comparaţii, astfel obţinem o soluţie cu O(N * logN) operaţii.

Subtaskul 4

Să zicem că avem două poziţii a şi b pentru care cunoaştem maximul şi, folosindu-ne de aceste informaţii, vrem să aflăm elementul de pe poziţia c, sau măcar să aflăm un element dintre a, b şi c. Putem să facem două query-uri ca să aflăm maximele între oricare două elemente. Vom avea 3 cazuri:

• queryMax(a, c) = queryMax(b, c) = x => pe poziţia c se află valoarea x. De acuma putem să îl ignorăm pe c şi să continuăm cu celelalte elemente.
• queryMax(a, b) = queryMax(a, c) = x => pe poziţia a se află valoarea x. De acuma putem să îl ignorăm pe a şi să continuăm cu celelalte elemente, numai că elementele pe care nu le ştim, dar le cunoaştem maximul vor fi b şi c.
• queryMax(a, b) = queryMax(b, c) = x => pe poziţia b se află valoarea x. Cazul acesta este analog cu cel anterior.

Astfel vom folosi exact 2 * N query-uri dacă avem grijă să nu facem operaţii care se repetă.

Subtask 5

În soluţia de mai sus, valorile de poziţiile a şi b vor deveni din ce în ce mai mici pe măsură ce se modifică a şi b. În particular, dacă am procesat toate elementele de pe poziţiile de la 1 pana la i, atunci a şi b se vor referi la cele mai mici două valori din permutare de pe prefixul respectiv.

Putem modifica soluţia de mai sus pentru a aplica query-uri într-un mod eficient.

• Dacă queryMax(a, b) < queryMax(b, c) = x => pe poziţia c se află elementul x, putem să îl ignorăm şi să continuăm cu celelalte elemente.
• Dacă queryMax(a, b) == queryMax(b, c) = x => pe poziţia b se află elementul x. Putem de acuma să îl ignorăm şi să continuăm cu celelalte elemente folosind a şi c. În cazul acesta va trebui să facem un query în plus pentru a afla queryMax(a, c)
• Dacă queryMax(a, b) > queryMax(b, c) = x => pe poziţia a se află elementul x. Putem de acuma să îl ignorăm şi să continuăm cu celelalte elemente folosind b şi c. În acest caz nu va trebui să facem un query în plus pentru a afla queryMax(b, c), deoarece îl cunoaştem deja, dar pentru a fi mai clar ce urmează, o să facem acel query, chiar dacă este degeaba.

Cum a şi b se vor schimba şi se vor referi la cele mai mici două elemente de pe prefix, cumva putem vedea că primul caz se va întâmpla din ce în ce mai mult. Dacă folosim această soluţie cu random_shuffle, numărul de operaţii folosite va fi pe medie N + 10, ceea ce se încadrează în limită şi va lua 100 de puncte.

Demonstraţie

Numărul de query-uri folosite va fi N + T unde T va fi numărul de dăţi în care schimbăm pe a şi b, care va fi defapt numărul de dăţi in care, dacă parcurgem o permutare de la stânga la dreapta, se schimbă cele mai mici două elemente.

Definim Exp[N] = numărul de dăţi în care se schimbă cele două minime dacă parcurgem permutarea de la stânga la dreapta pe medie. Astfel T va fi defapt Exp[N]. Ca să calculăm relaţia de recurenţă, trebuie să analizăm modul de construcţie al permutărilor. La o permutare de mărime N - 1 vom adăuga la sfârşit un element x, iar toate elementele din vechea permutare care sunt mai mari sau egale cu x vor creşte cu 1. Dacă x este 1, atunci numărul de dăţi în care cele două minime se schimbă va creşte cu 1 pe lângă numărul de dăţi pe care îl aveam în cadrul permutărilor de lungime 1. Dacă elementul adăugat va fi 2, atunci numărul de dăţi va creşte iarăşi cu 1 faţă de cele din permutările de lungime N - 1. Dacă elementul adăugat e de la 3 până la N, atunci numărul de schimbări ale celor două minime nu se schimbă. Astfel, relaţia de recurenţă va fi:

Exp[N] = (Exp[N - 1] + 1) * 1 / N + (Exp[N - 1] + 1) * 1 / N + Exp[N - 1] * (N - 2) / N <=>
Exp[N] = Exp[N - 1] + 2 / N

Dacă desfacem formula, vom obţine Exp[N] = 2 / 1 + 2 / 2 + ... + 2 / N = 2 * (1 / 1 + 1 / 2 + ... + 1 / N).
Suma 1 / 1 + 1 / 2 + ... + 1 / N poate fi la rândul ei aproximată cu logN. Aşadar, numărul de operaţii folosit va fi pe medie N + 2 * logN.