Soluţii ONIS 2014, Runda 1

Pufu

Pentru fiecare test, vom folosi 3 variabile, NSare, NCiocolata si NCascaval, iniţializate iniţial cu 0. Vom citi cele N şiruri de caractere. Dacă primul caracter dintr-un şir este "s", vom incrementa NSare. În caz contrar, dacă al doilea caracter din şir este "i", vom incrementa NCiocolata. Altfel, vom incrementa NCascaval. Rămâne să afişăm NCiocolata, Ncascaval şi Nsare, în această ordine.

Cabana

Pentru fiecare test avem în total N pitici şi K camere. Piticii intrau în ordine, de la 1 la N şi îşi alegeau camera în care urmează să doarmă. Putem gândi problema astfel:

Când intră primul pitic în cabană, sunt exact K camere libere, deci numărul de moduri în care piticul 1 îşi poate alege camera este egal cu K.
Când intră cel de-al doilea pitic în cabană, o cameră conţine 1 pitic, iar restul de K - 1 sunt libere, deci numărul de moduri în care piticul 2 îşi poate alege camera este egal cu K - 1.
.
.
.
Când intră piticul numărul K în cabană, sunt K - 1 camere ce conţin exact 1 pitic şi o cameră liberă. Deci numărul de moduri în care piticul K îşi poate alege camera este egal cu 1.

Procedeul de mai sus se repetă în momentul în care cel de-al K + 1-lea pitic intră în cabană. În acel moment, vom avea K camere care conţin câte un pitic. Deci cel de-al K + 1-lea pitic are din nou, K moduri în care îşi poate alege camera. Vom împărţi astfel cei N pitici în grupuri de câte K, în ordinea intrării în cabană. Numărul de moduri în care se pot aşeza piticii din fiecare grup este egal cu K!. În total, vom avea [N / K] grupuri. Deci numărul de moduri în care primii [N / K] * K pitici se pot aşeza este egal cu K! ^{[N / K]}. Vom forma un grup cu piticii rămaşi, acest grup conţinând N mod K pitici. Repetând procedeul de mai sus, primul pitic din acest grup va avea K moduri în care îşi poate alege camera, cel de-al doilea va avea K - 1 moduri în care se poate aşeza, etc. Astfel, numărul de moduri în care pot fi aşezaţi piticii din acest grup este egal cu K * (K - 1) * (K - 2) * ... * (K - N mod K + 1). Deci, răspunsul pentru fiecare test va fi egal cu:

K! ^{[N / K]} * K * (K - 1) * (K - 2) * ... * (K - N mod K + 1)

Dacă rescriem această formulă, obţinem:

K! ^{[N / K]} * $\frac{\ K!}{(K - N mod K)!}$$

Având în vedere că K ≤ 1.000.000, putem pregenera toate factorialele mai mici sau egale decât K. Cum operaţia MODULO nu este distributivă faţă de înmulţire, va trebui să folosim inversul modular al lui 1000000007. Cum acesta este un număr prim, inversul său modular este 1000000007 - 2 şi anume 1000000005.

Astfel, răspunsul final va fi egal cu:

K! ^{[N / K] + 1} * (K - N mod K)! ^1000000005

Pentru ridicarea la putere vom folosi Ridicare la putere in timp logaritmic.

Cifre4

Vom folosi un algoritm asemănător cu cel al parcurgerii în lăţime. Vom folosi o coadă cu ajutorul căreia vom genera toate numerele care conţin doar cifrele 2, 3, 5, 7. Pentru fiecare număr din coadă, ne interesează restul împărţirii sale la P şi valoarea sa adevarată. De asemenea, vom avea grijă să nu adaugăm în coadă două numere care dau acelaşi rest la împărţirea cu P. Acest lucru se poate face uşor folosind un vector caracteristic. Vom rezolva problema cu ajutorul acestei cozi astfel:

Introducem valoarea 0 în coadă.
Pentru fiecare număr x aflat primul în coadă, vom construi patru numere: x * 10 + 2, x * 10 + 3, x * 10 + 5, x * 10 + 7. Adaugăm în coadă în ordine crescătoare, doar numerele a căror resturi nu au mai fost adăugate, urmând să le marcăm şi pe acestea ca adăugate.
În momentul în care adăugăm în coadă un număr ce are restul N la împărţirea cu P, datorită metodei de construcţie a cozii, ştim că acest număr este primul cu această proprietate, deci îl vom afişa.
Dacă nu mai avem elemente în coadă, înseamna că nu am dat peste nici un număr cu această proprietate, deci vom afişa -1.

Carte

Vom folosi notaţia i -> j pentru secvenţa i, i+1, ..., j.
Pentru rezolvarea problemei, ne vom folosi de metoda programării dinamice. Vom construi următorul vector auxiliar:

d[i] = suma minimă a cuvintelor care nu există în dicţionar după o separare convenabilă, în secvenţa 1 -> i

Astfel, răspunsul pentru fiecare test se va găsi în d[len_book], unde len_book este numărul de litere din carte. Pentru a actualiza optim răspunsurile în acest vector, vom "potrivi" fiecare cuvânt aflat din dicţionar în şirul de caractere ale cărţii folosind un algoritm de tip Potrivirea Sirurilor/KMP. Cu ajutorul acestui algoritm, vom construi o nouă matrice caracteristică (cu valori 0 sau 1), cu următoarea semnificaţie:

match[i][j] = 1, dacă al j-lea cuvânt din dicţionar apare în conţinutul cărţii şi una dintre apariţiile sale se termină exact pe poziţia i din carte
match[i][j] = 0, dacă nu se respectă condiţia de mai sus

În continuare, ne vom folosi de această matrice pentru a actualiza dinamica noastră. Pentru fiecare poziţie i din carte, vom căuta un cuvânt în dicţionar care se termină pe i. Dacă notăm lungimea cuvântului găsit cu L, atunci ştim că acest cuvânt apare în secvenţa i-L+1 -> i. Deci, suma minimă a cuvintelor care nu există în dicţionar în secvenţa 1 -> i este egală cu suma minimă a cuvintelor care nu există în dicţionar în secvenţa 1 -> i-L.

for ( i = 1; i <= len_book; ++i ) { // Parcurgem toate caracterele din carte
    d[i] = d[i - 1] + 1; // Initializam dinamica, ca si cand nu am gasi nici o potrivire de cuvinte din dictionar
    for ( int j = 0; j < n; ++j ) // Parcurgem toate cuvintele din dictionar
        if ( match[i][j] ) // Daca am gasit o potrivire intre cuvantul din dictionar si pozitia pe care am ajuns
            d[i] = min( d[i], d[i - len[j]] ); // Actualizam dinamica
}

Easygraph

Problema ne cerea subsecvenţa de sumă maximă dintr-un lanţ al grafului. Pentru acest lucru, vom construi un vector auxiliar cu următoarea semnificaţie:

d[i] = suma maximă care se poate obţine într-o subsecvenţă ce se termină cu nodul i

Pentru a actualiza valorile acestui vector auxiliar, vom avea grijă să parcurgem mai întâi nodurile cu gradul de intrare 0, cu ajutorul unui algoritm asemănător cu Sortarea topologică. Astfel, vom avea siguranţa că de fiecare dată când vom actualiza dinamica pentru un nod, toate nodurile care au muchie către acel nod sunt actualizate deja şi conţin valoarea maximă posibilă. Prin urmare, după ce ne setăm această parcurgere, de fiecare dată când vizităm un nod x, ne vom uita la toate nodurile y care au muchie directă către nodul x, vom lua maximul dintre sumele obţinute pentru aceste noduri y şi vom actualiza suma în x în funcţie de ele. Asemănător cu algoritmul Subsecvenţei de sumă maximă, nu ne vor interesa valorile negative cu care venim din nodurile y. Răspunsul se va găsi în max(d[i]), 1 ≤ i ≤ N.

Frumusete

Dându-se un număr N în baza 2, putem genera toate numerele mai mici decât acesta astfel:

Luăm bitul de 1 cel mai semnificativ din număr şi îl transformăm în 0. Se poate observa că oricum am modifica biţii din dreapta bitului deja setat, vom obţine un număr mai mic.
Revenim la bitul setat şi îl transformăm înapoi în 1. Căutăm următorul bit de 1 la dreapta lui şi repetăm procedeul.

Vom construi o dinamică având următoarea semnificaţie:

d[i][j][k] = numărul de subşiruri în baza 2, de lungime i, care au frumuseţe j şi primul bit k

Recurenţa acestei dinamici este următoarea:

d[i][j][ 0 ] = d[i-1][j][ 0 ] + d[i-1][j][ 1 ]
d[i][j][ 1 ] = d[i-1][j][ 0 ] + d[i-1][j-1][ 1 ]

Vom parcurge biţii lui N începând cu cel mai semnificativ, reţinând la fiecare pas i frumuseţea subsecvenţei 1 -> i-1, pe care o vom nota cu frum. Având pregenerată dinamica de mai sus, de fiecare dată când dăm peste un bit de 1 aflat pe o poziţie i, ştim că putem transforma acest bit în 0, pentru a obţine numere mai mici decât numărul N. Astfel, vom adăuga la răspuns numărul de subşiruri care au lungime len-i+1, frumuseţe K-frum şi încep cu un bit de 0, adică d[len-i+1][K-frum][ 0 ].

Brazi

Având în vedere că arborii sunt binari, aceştia au o rădăcină. Putem determina rădăcina căutând nodul care nu este fiul nimănui. Vom parcurge apoi în adâncime arborele, începând cu rădăcina. Cu ajutorul acestei parcurgeri, pentru fiecare arbore vom genera un cod astfel:

Când intrăm într-un fiu stâng, vom adăuga cifra 0 în cod.
Când intrăm într-un fiu drept, vom adăuga cifra 1 în cod.
Când ieşim dintr-un nod, vom adăuga cifra 2 în cod.

Doi arbori sunt asemenea dacă cele două coduri asociate lor sunt egale. Vom reţine toate aceste coduri într-o tabelă hash, împreună cu numărul de apariţii al fiecărui cod. După ce generăm codul unui arbore, afişăm numărul de apariţii ale acestuia în tabela hash. Urmează să adăugăm codul arborelui în hash şi să continuăm procedeul.

Imunitate

O abordare directă ar fi să introducem iniţial toţi deputaţii în cameră. La fiecare pas, urmează să alegem un deputat care este influenţat negativ de mai mult de jumătate dintre colegii săi şi să îl eliminăm. Pentru acest lucru, vom folosi o parcurgere în adâncime, trecând dintr-o stare cu i candidaţi, într-o stare cu i-1 candidaţi. Dacă nu putem elimina nici un candidat, înseamnă că am obţinut o cameră care nu este penală, deci vom incrementa răspunsul.

Vom reţine aceste stări bazându-ne pe puterile lui 2. Dacă avem în total N candidaţi, o stare reprezintă un şir de N biţi din baza 2, astfel încât dacă bitul i este 1, înseamnă că al i-lea candidat este încă în cameră în starea curentă. De exemplu: Dacă avem 5 candidaţi în total, starea în care mai avem doar candidaţii cu numerele 1, 3 şi 4 va fi codificată cu numărul 01101 în baza 2, adică 13 în baza 10.

Vom optimiza acum soluţia descrisă mai sus. Pentru fiecare deputat, vom reţine un şir de N biţi în baza 2, astfel: pentru candidatul i, dacă bitul j este 1, vom considera că al i-lea candidat este influenţat negativ de candidatul j. De asemenea, vom pregenera un vector cu următoarea semnificaţie:

nrbits[i] = numărul de biţi de 1 din scrierea lui i în baza 2.

Astfel, starea iniţială va fi 2^N-1. Pentru fiecare stare, vom parcurge biţii acesteia, iar pentru fiecare bit de 1, având generate toate cele de mai sus, putem verifica în timp constant dacă acel bit trebuie eliminat sau nu.

Progresie

Dacă ne uităm atent, observăm că block-ul K începe la K * (K - 1) + 1 şi se termină la K * K. Atunci putem să ne dăm seama dacă un număr se află sau nu în şirul nostru, printr-o extragere a radicalului.

Dacă avem o secvenţă de lungime N şi de raţie R atunci sigur un răspuns bun este M * (M - 1) + 1, cu M = (N - 1) * R + 1, acesta fiind block-ul M care conţine în întregime secvenţa cerută.

Dar se observă că răspunsul de mai sus, care este o margine superioară, nu este niciodată folosit când N este mult mai mic decât R. Atunci ideea este să parcurgem block-urile în ordine, cu prima valoare start-ul block-ului, şi să vedem în O(N) dacă numerele aparţin sau nu şirului.

Triangulare

Trebuie să împărţim poligonul în triunghiuri folosind N - 3 segmente care să se afle în înteriorul poligonului şi să nu se intersecteze între ele, şi nici cu laturile poligonului, în afară de punctele lor comune.

Limitele problemei ne lasă să luăm o abordare brute force, şi anume, încercăm de fiecare dată să adăugăm segmentul minim lexicografic la soluţie. Un segment este bun în soluţia noastră dacă el nu se intersectează cu niciun alt segment şi nicio altă latură a poligonului şi este înăuntrul poligonului.

Trebuie deci să verificăm intersecţia cu laturile poligonului şi cu segmentele adăugate anterior la soluţie. Dacă nu se intersectează cu acestea, trebuie să vedem că segmentul este înăuntru. Pentru a vedea asta testăm dacă un punct de pe segment se află în interiorul poligonului. Este suficient să testam un singur punct deoarece segmentul se află total în interiorul sau în exteriorul poligonului.

Split2

Se observă că se poate căuta binar costul minim. Presupunem că avem fixat un cost C. Trebuie să verificăm dacă putem să obţinem o împărţire în subsecvenţe care să aibă costul mai mic sau egal cu C. Pentru asta, puteam construi o dinamică astfel:

dp[i][j] = 1, dacă putem să împărţim primele i numere în j subsecvenţe şi 0 în caz contrar.

Recurenţa este simplă, fixând ultima subsecvenţă. Se obţine astfel o complexitate O(N^3). Pentru a o reduce, trebuie făcuta următoarea observaţie: Dacă există o împărţire cu costul mai mic sau egal cu C în j subsecvenţe, atunci există şi una în j + 2, împărţind o subsecvenţă i, i+1, i+2, ..., j-1, j în 3, astfel:

i, i+1
i+2, ..., j-2
j-1, j

Astfel încercăm să calculăm următoarea dinamică:

dp[ i ][ 0 ] = nr minim de subsecvenţe în care putem să împarţim primele i numere într-un nr par de subsecvenţe
dp[ i ][ 1 ] = nr minim de subsecvenţe în care putem să împarţim primele i numere într-un nr impar de subsecvenţe

Recurenţa este:

dp[i][j] = dp[k-1][1-j], dacă subseventa k, ..., i are costul mai mic sau egal cu C

În final, dacă dp[n][m%2] <= m, atunci există o împărţire în m subsecvenţe.