IND

palixor

Precalcul: pentru fiecare număr din șir se va forma un număr binar format din 10 cifre, alocând fiecărei cifre de la 0 la 9 o poziție în scrierea binară. Dacă o cifră apare de un număr par de ori în scrierea numărului dat, atunci i se va aloca cifra 0 în scrierea binară, iar dacă apare de un număr impar de ori i se va aloca cifra 1. De exemplu pentru numărul 2307269032, frecvențele cifrelor de la 0 la 9 din scrierea sa sunt 2,0,3,2,0,0,1,1,0,1. Atunci numărul binar alocat va fi 0010001101(2)=141(10). Astfel, numerele dintr-un subșir pot forma cu cifrele lor un palindrom dacă și numai dacă valoarea XOR a tuturor acestor numere este 0 sau o putere a lui 2, deoarece într-un palindrom cifrele ori apar toate de un număr par de ori, ori una singură apare de un număr impar de ori. Pentru un număr a[i] din şirul inițial vom nota cu b[i] numărul binar asociat.

Se poate folosi programarea dinamică. Dacă notăm numărul subşirurilor cu proprietatea dată formate din elementele până la poziţia i care au XOR-ul egal cu j, cu dp[i][j], atunci dp[i][b[i]^j] = dp[i-1][j]+dp[b[i]^j] pentru orice j de la 0 la 1023. Rezultatul va fi dp[n][0] + dp[n][1]+dp[n][2]+dp[n][4] + ... +dp[n][512]. Complexitate O(1024n)

Se formează un sistem liniar cu 10 ecuaţii și n necunoscute, care se va rezolva prin metoda lui Gauss. Pentru fiecare i de la 1 la n vom nota cu x[i] o necunoscută a sistemului care poate fi 0 dacă numărul a[i] nu este luat în subșir şi 1 dacă este luat în subşir. Cei 10 biţi din fiecare număr b[i] vor fi coeficienţii necunoscutei x[i] din cele 10 ecuaţii. Termenii liberi ai sistemului vor fi biţii unuia dintre numerele 0, 1, 2, 4, ..., 512. Complexitate O(45n)

De exemplu, pentru șirul 89, 787, 7997, numerele binare asociate vor fi 3, 2, respectiv 0.

vacanta2020
Metoda 1 (exotica)

Se construiesc k+1 grafuri G0, G1, … , Gk, unde G0 este chiar graful dat în enunţul problemei. Graful Gi va avea nodurile numerotate de la n*i+1 la n*i+n, iar dacă în graful dat G0 avem o muchie de cost c între nodurile u şi v, atunci în fiecare graf Gi vom avea o muchie de cost c între nodurile n*i+u şi n*i+v şi în plus o muchie de cost 0 intre vârful n*i+u din graful Gi şi vârful n*(i+1)+v din graful Gi+1, pentru orice i de la 0 la k-1.
Se aplica apoi algoritmul lui Djikstra pentru graful construit.

Metoda 2

Se aplica algoritmul lui Djikstra combinat cu programare dinamică pentru graful dat. Pentru fiecare nod i se calculează d[i][j] ca fiind distanţa minimă de la nodul 1 la nodul i, folosind j vouchere. Actualizarea lui d[i][j] pentru o muchie (u,i) se face astfel: d[i][j] = min(d[i][j] , d[u][j]+cost[u][i]) , d[i][j+1] = min(d[i][j+1] , d[u][j]).