Concurs InfoPro 2020

2 probleme de la InfoPro 2020, luna decembrie

Ca luna trecută, ediția din decembrie a concursului InfoPro a avut probleme interesante care îi pune la încercare și pe cei mai buni. M-am gândit să scriu, înainte de afișarea soluțiilor oficiale, o descriere a rezolvărilor mele la problemele pe care le-am făcut în timpul concursului: Cntsubșirmax și Mex2D.

Cntsubșirmax

Cerință

Se dă un șir s cu n litere mici. Notăm cu L(i, j) lungimea subșirului maxim lexicografic format din elemente ale subsecvenței [i…j]. Calculați, modulo 10^9 + 7, suma numerelor L(i, j) pentru toate subsecvențele [i…j] ale șirului de caractere dat.

Restricții:

pentru 50 de puncte: n <= 1000;
pentru alte 50 de puncte: n <= 10^6.

Descrierea soluției

Ce caracteristici are un șir maxim lexicografic?

Mai întâi, să vedem cum se formează acest subșir maxim lexicografic. Voi lua un exemplu de șir inițial pe care voi construi acest subșir maxim lexicografic, mergând de la stânga la dreapta, începând cu prima literă:

abcbac

Pasul 1: Este pus caracterul ‘a’. Subșirul devine “a“.

Pasul 2: Avem caracterul ‘b’. “b“ este mai mare lexicografic decât “ab“, așa că îl înlăturăm pe ‘a’ și lăsăm doar ‘b’.

Pasul 3: “c“ este mai mare lexicografic decât “bc“, așa că îl ștergem pe ‘b’ și subșirul va fi format doar din litera ‘c’.

Pasul 4: Avem caracterul ‘b’. Dacă am pune ‘b’ în subșir, obținem “cb“, ceea ce e o configurație mai bună decât ce am obține dacă ștergem ‘c’ (subșirul devenind “b“) sau nu punem ‘b’ (subșirul rămânând “c“).

Pasul 5: Analog pasului 4, este optim să îl punem pe ‘a’ în subșir, obținând astfel “cba“.

Pasul 6: Dacă pur și simplu punem ‘c’ la sfârșitul subșirului de dinainte, obținem “cbac“. Totuși, dacă ștergem ‘a’, vom avea “cbc“, care este mai mare lexicografic. Analog, trebuie să ștergem și caracterul ‘b’, obținând în final subșirul “cc“.

Observăm că la fiecare pas litera x șterge toate literele mai mici decât x, din sufixul maximal (adică o cât mai lungă „bucată din dreapta“) al subșirului. În alte cuvinte, ultimele litere din subșir sunt scoase numai dacă întâlnim mai târziu o literă mai mare decât acestea; mai exact, aceaste ultime litere sunt scoase de prima literă mai mare întâlnită. De fapt, acest subșir funcționează exact ca o stivă ce reține maximul la „fund“.

Soluția de 50 de puncte

Pe ideea aceasta se bazează soluția de 50 de puncte: fixăm punctul de la care începem să construim subșirul, apoi folosim un algoritm asemănător celui descris mai sus: la fiecare pas, scoatem toate literele mai mici decât cea curentă de la sfârșitul subșirului, apoi o punem pe cea curentă la finalul subșirului. La sfârșitul fiecărui pas vom avea construit subșirul maxim lexicografic pentru subsecvența determinată de punctul de start și indicele la care am ajuns în acest pas. Așadar, obținem un algoritm în O(n^2), arhisuficient pentru 50 de puncte.

Soluția de 100 de puncte

Problema fundamentală a soluției descrisă mai înainte este că nu există nu mod mai bun decât O(n) să generăm toate subșirurile dintr-un punct de start fixat… pur și simplu nu există un mod mai rapid de a procesa toate subsecvențe, având în vedere că sunt aproximativ n^2 la număr. Având în vedere faptul că de fapt este cerută suma lungimilor și nu subșirurile propriu-zise, nu are rost să încercăm să le generăm (cel puțin nu pe toate).

E nevoie de o abordare un pic diferită… hmmm… lungimea unui subșir e doar numărul de litere din acesta… așadar, în loc să aflăm lungimea fiecărui subșir, am putea încerca să aflăm de câte ori apare fiecare literă în toate aceste subșiruri… aha! Nu e nevoie să generăm nimic, așa că nu mai suntem limitați la o rezolvare în O(n^2).

Ar fi suficient să vedem, pentru fiecare literă (să zicem că se află pe poziția p), pentru câte subsecvențe apare în subșirul maxim lexicografic. E mai ușor decât pare: în primul rând, luăm în calcul numai subsecvențele care conțin poziția p: să notăm capetele din stânga, respectiv dreapta, cu st și dr. Astfel, trebuie doar să numărăm câte valori st și câte valori dr, cu st <= p <= dr, determină subsecvențe ce satisfac condiția.

Când punem caracterul s[p] într-un subșir oarecare, știm sigur că cel puțin la acel pas rămâne litera în subșir, iar mai târziu, va fi scoasă de o literă mai mare (cel mai probabil). În alte cuvinte, nu contează capătul din stânga al secvenței așa de mult, pentru că oricum litera de pe poziția p va fi pusă în cel puțin un subșir, indiferent de st; singura condiție pe care trebuie capătul st să o satisfacă este st <= p.

Din analiza formării subșirului maxim lexicografic, reiese că literele din subșir sunt mereu în ordine descrescătoare: dacă ar fi să mai adăugăm una mai mare decât cele de la sfârșitul subșirului, aceasta ar șterge acele litere mai mici. Asta înseamnă că litera s[p] va ramâne în subșir până ce dăm de o literă mai mare în dreapta. Asta înseamnă că avem ldr-p moduri de a-l alege pe dr, unde ldr este indicele primei litere strict mai mari decât cea cu indicele p.

Răspunsul final va fi așadar ∑(p+1)*(ldr–p), pentru orice p de la 0 la n-1.

Mai e un mic aspect de luat în calcul însă: cum determinăm eficient ldr? Folosim o stivă în care vom reține, în ordine descrescătoare, indicii literelor, litere ce ar forma un șir strict descrescător. Altfel spus, vom reține indicii i, i_1, i_2, …, i_k astfel încât s[i] > s[i_1] > s[i_2] > … > s[i_k], unde indicele i este cel al pasului curent.

Mai multe detalii în privința algoritmului stivei: parcurgem vectorul de la dreapta la stânga și, asemănător literelor din subșirul maxim lexicografic, vom șterge la pasul curent toți indicii literelor mai mici decât cea curentă. Prima poziție găsită în stivă pe care se află o literă mai mare decât cea curentă este ldr.

Mex2D

Cerință

Numim mex-ul a k numere cel mai mic număr natural care nu se regăsește în mulțimea formată de cele k numere (de exemplu, mex({0, 1, 2}) = 3, mex({0, 0, 1, 2, 4, 1}) = 3, mex({1, 2}) = 0). Se da o matrice a cu n linii și m coloane care este indexată de la 0. Construiți matricea b, astfel încât b[i][j] = mex(a[l][c]), cu l de la 0 la i și c de la 0 la j.

Restricții:

n, m <= 2000

a[i][j] <= 4 * 10^6, pentru orice i de la 0 la n-1 și j de la 0 la m-1

Soluție

Problema pare ușoară la început: așa cum la un vector ai menține un vector caracteristic, la fel se poate și aici, nu? Nu chiar. Problema e că într-un vector diferența dintre mulțimile v[1…i] și v[1…i+1] e de doar un număr, în timp ce la matrice această diferență este de O(n), adică vor fi mult mai multe elemente noi când trecem de la o linie la alta.

Abordarea

Pe scurt, noi ar trebui să aflăm, pentru fiecare celulă (i, j), care este cel mai mare x astfel încât toate numerele între 0 și x apar în submatricea cu colțurile în (0, 0) și (i, j). Problema adevărată e cum facem acest lucru eficient.

De aici, sunt două posibile abordări: ori, într-o manieră asemănătoare programării dinamice, încercăm să valorificăm informațiile obținute pentru celulele (i-1, j) și (i, j-1), ori pur și simplu căutăm fără foarte multe informații anterior aflate acel x. E foarte probabil ca prima variantă să pice, pentru că mex-ul nu poate fi aflat folosindu-ne doar de alte mex-uri: de exemplu, dacă reunesc două mulțimi cu mex-urile 3, respectiv 1, sunt mai multe mex-uri ce pot rezulta: 3 (pentru {0, 1, 2} și {0, 2}), 4 (pentru {0, 1, 2} și {0, 2, 3}), etc. Aflarea unui mex implică memorarea aparițiilor tuturor numerelor din (i, j), așa că e, în cel mai bun caz, foarte dificil să găsim o soluție cu prima abordare.

O primă subproblemă

În primul rând, ar ajuta foarte mult dacă am putea afla foarte repede dacă apare elementul y în submatricea (0, 0, i, j), ca după aceea să putem folosi o structură de date mai avansată ca să aflăm x-ul eficient.

Surprinzător, e ușor de aflat apariția lui y: celula (l, c) va apărea în toate submatricile cu colțul (i, j), cu i >= l și j >= c; dacă procesăm numerele matricii de sus în jos și de la stânga la dreapta, odată ce procesăm un element, prima condiție va fi mereu îndeplinită, deci trebuie să luăm în seamă numai coloana pe care se află acel element. Fiindcă a[i][j] <= 4*10^6, reținem într-un tablou (să-l numim cmin)coloana minimă la care am întâlnit fiecare număr, făcând actualizări în timpul parcurgerii matricii dacă e nevoie. Așadar, numărul y se va afla în submatricea (0, 0, i, j) dacă și numai dacă cmin[y] <= j.

A doua subproblemă

Faptul că putem afla în O(1) dacă un număr este inclus în submatricea (0, 0, i, j) și, chiar mai important, că această condiție este extrem de convenabilă (doar o inegalitate), permite folosirea unei structuri de date pentru aflarea lui b[i][j].

Mai exact, trebuie să vedem cea mai mică valoare x astfel încât cmin[x] > j (și atunci mex-ul va fi x-1), dar trebuie și să putem actualiza o valoare din cmin într-un mod eficient. Sunt mai multe moduri de a rezolva această problemă: se poate folosi șmenul lui Batog, prin care am obține o complexitate de O(sqrt(vmax)) (unde vmax este valoarea maximă care poate apărea în matrice), sau arbori de intervale (și cei indexați binar merg) care duc la O(log^2 vmax) sau O(log vmax) per interogare, depinzând de implementare. Voi prezenta soluția cu arbori de intervale.

Reținem în arborele de intervale pentru fiecare nod valoarea maximă din cmin pentru intervalul de poziții corespunzător nodului.

Pentru complexitatea O(log^2 vmax), facem o simplă căutare binară, în care pentru fiecare pas verificăm dacă maximul este mai mare decât j.

Pentru O(log vmax), trebuie să optimizăm un pic această căutare, făcând-o pe însuși arborele de intervale: să zicem că suntem într-un nod nx: dacă maximul corespunzător fiului stâng este mai mare decât j, atunci acolo se află valoarea căutată; însă, dacă maximul din fiul stâng e mai mic sau egal, atunci ne ducem în fiul drept. În orice caz, algoritmul face O(log vmax) pași, ducând la o complexitate finală de O(nm log vmax).