Solutia problemei PWCA

Mai întâi trebuie să facem câteva observaţii legate de transformare:

Observaţia 1:

Fie două şiruri A şi B astfel încât A poate deveni B. Să presupunem că Bi ≠ Bi+1 pentru un anumit i. Atunci Ai = Bi şi Ai+1 = Bi+1 (Ai ≠ Ai+1). Această proprietate se demonstrează astfel:

  • Dacă Ai = Ai+1 atunci acestea nu pot deveni diferite.
  • Dacă Ai ≠ Bi şi Ai+1 ≠ Bi+1 atunci ambele valori vor trebui modificate pe parcursul transformării. Cele două modificări se vor face în mod evident pe rând, iar după prima dintre ele, cele două valori vor deveni egale. Aşa cum am văzut şi mai sus, dacă două valori vecine devin egale, atunci nu vor mai putea fi diferite (aşa cum vor trebui să fie la final).

Observaţia 2:

Folosind observaţia 1, ne dăm seama că putem rezolva secvenţele maximale ale lui B independent. Astfel, problema se reduce la a găsi numărul de şiruri A care pot fi transformate într-un şir de valori egale cu 0 sau 1 de o anumită lungime (cele două cazuri sunt identice).

Greedy:

Acum putem veni cu un algoritm greedy care verifică dacă un şir iniţial A poate fi transformat într-unul plin de 1. Ideea de la care plcăm este cea de a transforma subsecvenţele de 0 în 1 de fiecare dată când avem ocazia. Astfel, putem porni cu o stivă de la stânga la dreapta în care introducem pe rând secvenţele de valori egale din A. Acum, vom urmări două cazuri:

  • În vârful stivei se află o secvenţă de 0 mai mică sau egală cu cea precedentă. O transformăm într-una de 1 şi actualizăm stiva.
  • În vârful stivei se află o secvenţă de 1 care permite secvenţei precedente (de 0) să se transforme. Efectuăm transformarea şi actualizăm stiva.

Mereu după ce actualizăm stiva verificăm din nou cele două cazuri. Acest algoritm are complexitatea O(|A|).

Subtask 1 (10 puncte)

Pentru acest subtask vom considera toate şirurile iniţiale A posibile. Pentru a verifica un şir iniţial, împărţim şirul B în subsecvenţe de valori egale şi aplicăm algoritmul greedy de mai sus pentru secvenţele din A corespunzătoare celor din B. Complexitatea timp este O(2|B| ⋅ |B|).

Subtask 2 (20 de puncte)

Putem îmbunătăţii soluţia precedentă precalculând pentru fiecare l de la 1 la VMAX numărul de şiruri iniţiale A pentru care se poate ajunge la un şir de valori egale cu 0 sau 1 de lungime l. Complexitate timp O(2VMAX ⋅ VMAX + N).

Subtask 3 (30 de puncte)

Pentru a continua avem nevoie de o soluţie total diferită. Să considerăm că vrem să transformăm şirul A într-un şir de valori egale cu 1. Fie S secvenţa de lungime maximă din A. Avem două cazuri:

  • S este formată din valori de 1. În acest caz, ştim că toate secvenţele de 0 nu sunt mai lungi decât S. Iniţial, S va avea câte o secvenţă de 0 la stânga şi la dreapta (sau nu, dacă este lângă margine). Deoarece aceste secvenţe nu sunt mai lungi decât S, ele pot fi transformate în 1. Astfel, vom extinde S la stânga şi la dreapta. În acelaşi timp, secvenţele de 1 care erau vecine cu cele de 0 se vor alipi şi ele. Acum S este mai mare şi se poate extinde din nou în acelaşi mod. Am demonstrat că în acest caz şirul A poate fi transformat.
  • S este formată din valori de 0. Acest caz este mai greu deoarece vom vrea ca la un moment dat să îl transformăm pe S în 1 cu ajutorul unei secvenţe mai mari de 1. Această secvenţă T se poate forma la stânga sau la dreapta de S. Acum vom demonstra că dacă această secvenţă se poate forma, atunci poate continua până când umple tot spaţiul de la stânga lui S. Ştim că odată formată, T este mai mare decât S, şi în acelaşi timp mai mare decât toate restul secvenţelor de 0 deoarece acestea nu vor creşte niciodată faţă de lungimea iniţială (pentru că nu este optim). Ştiind asta, putem considera că T poate transforma tot spaţiul de la stânga lui S în 1. Odată ce set întâmplă asta, S se transformă în 1 (fiind lângă T) şi începe să se extindă în direcţia opusă ca în subtask-ul anterior.

Aşadar, în cazul al doilea ne-am dat seama că fie tot ce este la stânga de S, fie tot ce este la dreapta se va transforma în 1. Acum vom construi o soluţie folosind programare dinamică:

  • cntAll[len][k][lval][rval] = numărul de şiruri de lungime len, cu secvenţa maximă de lungime k, cu primul element lval şi ultimul element rval (lval şi rval sunt valori binare).
  • cntFull[len][k][lval][rval] = numărul de şiruri de lungime len, cu secvenţa maximă de lungime k, cu primul element lval şi ultimul element rval (lval şi rval sunt valori binare) care se pot transforma într-un şir plin de 1.
  • cntAllPref[len][k][lval][rval] = numărul de şiruri de lungime len, cu secvenţa maximă de lungime maxim k, cu primul element lval şi ultimul element rval (lval şi rval sunt valori binare).
  • cntFullPref[len][k][lval][rval] = numărul de şiruri de lungime len, cu secvenţa maximă de lungime maxim k, cu primul element lval şi ultimul element rval (lval şi rval sunt valori binare) care se pot transforma într-un şir plin de 1.

cntAllPref şi cntFullPref sunt uşor de calculat fiind doar sume pe prefixe (ale parametrului k) pentru dinamicile principale (cntAll şi cntFull).

Pentru recurenţe va trebui să fixăm poziţia secvenţei maximale (de lungime k). Pentru fiecare poziţie de început pos avem următoarea recurenţă (vom folosi notaţiile lLen = pos - 1 şi rLen = len - (pos+k-1)):

  • Pentru cazul în care ce mai lungă secvenţă este de 0:
    • cntAll[len][k][lval][rval] += cntAllPref[lLen][k-1][lval][1] ⋅ cntAllPref[rLen][k][1][rval]
    • cntFull[len][k][lval][rval] += cntFullPref[lLen][k-1][lval][1] ⋅ cntAllPref[rLen][k][1][rval], dacă lLen ≥ len
    • cntFull[len][k][lval][rval] += cntAllPref[lLen][k-1][lval][1] ⋅ cntFullPref[rLen][k][1][rval], dacă rLen ≥ len
    • cntFull[len][k][lval][rval] += cntFullPref[lLen][k-1][lval][1] ⋅ cntFullPref[rLen][k][1][rval], dacă lLen ≥ len şi rLen ≥ len
  • Pentru cazul în care ce mai lungă secvenţă este de 1:
    • cntAll[len][k][lval][rval] += cntAllPref[lLen][k-1][lval][0] ⋅ cntAllPref[rLen][k][0][rval]
    • cntFull[len][k][lval][rval] += cntAllPref[lLen][k-1][lval][0] ⋅ cntAllPref[rLen][k][0][rval]

Pentru a număra şirurile A care pot fi transformate în şiruri de valori egale cu 1 sau 0 vom avea complexitatea O(|A|3). Cum N = 1, asta înseamnă O(VMAX3).

Subtask 4 (40 de puncte)

Pentru acest subtask se va folosi soluţia anterioară pentru a precalcula răspunsul pentru toate lungimile l de la 1 la VMAX (asemănător cu subtask-ul 2). Complexitate timp O(VMAX3).

Soluţia de 100 de puncte se găseşte aici.