Solutii Algoritmiada 2015 Runda 1

Noname3

O sa aplicam o strategie greedy. Initial o sa atribuim primelor N - 1 valori numerele de la 1 la N - 1, iar al N-ulea numar o sa fie ce ramane (adica S - (N - 1) * N / 2). Dupa observam ca putem creste elementele din [1,N-1] cu 1, si sa scadem valoarea elementului N cu (N - 1), cat timp ultimul element ramane mai mare decat penultimul. Nu este nevoie sa iteram acesti pasi, pot iesi dintr-o relatie simpla: conditia este ca V[N] - (N - 1) * K > V[N - 1] + K, unde V[i] reprezinta valoarea initiala a elementului cu indicele i (mai exact V[N - 1] = N - 1 si V[N] = S - N * (N - 1) / 2), iar K reprezinta numarul de pasi pe care trebuie sa ii aflam. De aici putem scoate relatia V[N] - V[N - 1] > N * K, adica (V[N] - V[N - 1]) / N > K. Rezulta K = (V[N] - V[N - 1]) / N cand V[N] - V[N - 1] nu este multiplu de N si K = (V[N] - V[N - 1]) / N - 1 cand e invers ((V[N] - V[N - 1]) / N trebuie sa fie mai mare strict decat K, ca urmare cand este egal trebuie scazut 1).

Din pacate nu am terminat :). De exemplu daca sirul rezultat este 4 5 6 10 (urmatorul ar fi fost 5 6 7 7 care nu e valid), observam ca exista o solutie si mai buna, adica: 4 5 7 9 si dupa 4 6 7 8. Concluzia este ca desi nu mai putem creste toate elementele din intervalul [1, N - 1] cu 1, putem inca sa crestem cateva de la sfarsit. Din moment ce sunt doar N numere, in cazul acesta putem itera (cat timp ultimul element este mai mare decat penultimul, o sa scadem cu 1 ultimul element si o crestem cu 1 ultimul element neactualizat). Cum aveam si in exemplul de mai sus, pentru 4 5 6 10:
10 > 6 => il crestem pe 6 si il scadem pe 10 => sirul nou format este 4 5 7 9
9 > 7 => il crestem pe 5 (ultimul element neactualizat) si il scadem pe 9 => sirul nou format este 4 6 7 8
Daca am contiunua cu inca un pas, ultimul element nu o sa mai fie mai mare strict ca penultimul, deci ne oprim.

In final afisam solutia gasita.

MagicSequence

Pentru aceasta problema solutia este foarte simpla. Daca primul element este mai mare decat ultimul raspunsul e "NO" altfel e "YES".

Pentru a arata asta vom modifica problema. In loc sa pornim de la un sir gol la cara adaugam elemente dupa regula din enunt, vom porni de la sirul final si vom scoate elemente dupa regula inversata, adica vom scoate un element daca este mai mare decat cel din stanga lui sau mai mic decat cel din dreapta lui.

Se observa foarte usor ca cele 2 probleme sunt echivalente. Sa presupunem ca avem un sir S = a1 a2 ... aN. Vom demonstra prin inductie dupa lungimea lui S afirmatia din primul rand.

  • Daca a1 < aN
    Trebuie sa existe neaparat un numar ai cu 1 < i ≤ N si ai-1 < ai altfel ar insemna ca a1 > a2 > ... > aN, ceea ce e fals.
    • Il scoatem pe ai daca i < N
    • Il scoatem pe aN-1 daca i este N
      Dupa ce am scos un numar observam ca primul si ultimul element raman neschimbate si deci obtinem un sir de N-1 elemente pentru care stim ca raspunsul e "YES".
  • Daca a1 > aN atunci vom arata ca orice element am scoate atunci primul element va ramane mai mare decat ultimul.
    • Daca scoatem un element ai cu 1 < i < N atunci primul si ultimul element raman neschimbate.
    • Daca scoatem primul element inseamna ca a1 < a2 (altfel nu l-am fi putut scoate) si deoarece a2 > a1 > aN inseamna ca primul element tot va fi mai mare decat ultimul
    • Daca scoatem ultimul element inseamna ca aN-1 < aN (altfel nu l-am fi putut scoate) si deoarece a1 > aN > aN-1 inseamna ca primul element tot va fi mai mare decat ultimul.

Minesweeper2

Solutie 20 de puncte: Backtracking - verificam toate posibilitatile si numaram cate merg (complexitate O(2^N * N))

Solutie 30 de puncte: Observam ca nu avem -1. Putem aplica o strategie greedy. Daca prima suma este s1 = 0, inseamna ca primele 2 caractere sunt 0. Daca suma este 2, primele 2 caractere sunt 1. Daca suma e 1, avem ori 0 cu 1, ori 1 cu 0. Odata fixate primele 2 elemente, pentru restul avem solutie unica, sau nu avem. Verificam daca avem solutie (ori nu o sa avem si afisam 0, ori avem si afisam 1). Singurul caz special este cand avem N = 2 si 1 1 (aici raspunsul este 2).

Cele 2 solutii combinate de mai sus pot oferi 50 de puncte.

Solutie 100 de puncte. Programare Dinamica: d[i][j] = in cate moduri pot sa pun bombe pe primele i casute, ultimele 2 casute fiind in starea j.
Starea j o putem nota in felul urmator:
0 - ultimile casute sunt 0 si 0 (o sa notam starea 0 cu 00)
1 - ultimile casute sunt 0 si 1 (o sa notam starea 1 cu 01)
2 - ultimile casute sunt 1 si 0 (o sa notam starea 2 cu 10)
3 - ultimile casute sunt 1 si 1 (o sa notam starea 3 cu 11)
O sa facem dinamica in fata. Suntem la pozitia i (stiim d[i][j], cu j de la 0 la 3) si vrem sa calculam toate d[i + 1][j] ($j$ desigur de la 0 la 3).
Ne uitam la valoarea s[i] (cate casute sunt vecine cu casuta de pe linia 1 coloana i) si avem 5 cazuri:

1. s[i] = 0 => Configuratia arata 000, deci d[i + 1]0 = d[i]0 (ultimile 2 de la i + 1 si i sunt 00 deci suntem in starea 0 in ambele)
2. s[i] = 1 => Avem ori 001 ori 010 ori 100, deci d[i + 1]01 = d[i]00, d[i + 1]10 = d[i]01, d[i + 1]00 = d[i + 1]10
3. s[i] = 2, se deduce asemanator cu cazul 2
4. s[i] = 3, asemanator cu cazul 1
5. s[i] = -1. In cazul acesta pentru o configuratie putem veni din alte 2. De exemplu d[i + 1]00 = d[i]00 + d[i]10 (pentru ca putem avea si 000 si 100). Analog scoatem recurenta si pentru celalalte stari. Va las sa va ganditi singuri :)

Initializarea in dinamica se va face in functie de s1 (de exemplu daca s1 = -1, primele 2 elemente se pot afla in orice configuratie; daca e 1, exista doar 2 posibilitati 01 si 10).

Raspunsul se va gasi in d[n][j], unde j este ales in functie de s[n] (daca s[n] = 1, d[n]11 nu face parte dintr-o configuratie valida deoarece are suma ultimelor 2 elemente 2; daca s[n] = -1, putem lua orice configuratie j)

Fenrir

Reformulând, problema cere să se construiască un graf neorientat conex cu 20 de noduri care nu are lanţ hamiltonian, maximizând gradul minim al unui nod. În ciuda formulării destul de încărcate teoretic, problema poate fi abordată cu succes fără un background prea profund în teoria grafurilor.

Majoritatea soluţiilor de punctaj nenul folosesc o construcţie particulară. Menţionăm aici câteva dintre cele mai populare:

- Orice arbore care nu este lanţ asigură 4 puncte.
- Trei cicluri care au exact un nod în comun asigură 9 puncte.
- Extinzând ideea precedentă, se pot construi 3 subgrafuri complete de dimensiuni cât mai apropiate toate având în comun un unic nod. Se pot obţine în acest fel 49 de puncte.
- Observăm că ultimele 2 soluţii se bazează pe un nod "critic" pentru a limita mişcarea în graf şi a garanta lipsa lanţului hamiltonian. Deşi puternică, această construcţie nu ne permite să creştem gradele nodurilor păstrând proprietatea nodului critic. Pentru a obţine un punctaj mai mare vom încerca să impunem o limitare mai subtilă. Observăm că dacă partiţionăm nodurile în 2 mulţimi A şi B astfel încât toate muchiile să aibă un capăt în mulţimea A şi celălalt în mulţimea B, lanţul hamiltonian nu poate avea 2 noduri consecutive din aceeaşi mulţime, deci devine o condiţie necesară ca diferenţa dintre cardinalul mulţimii A şi cardinalul mulţimii B să fie mai mică sau egală cu 1. Putem încălca această condiţie punând 9 noduri în mulţimea A şi 11 noduri în mulţimea B. Observaţi că acum nu mai avem nicio limitare asupra muchiilor. Le putem selecta pe toate cele 99 posibile, astfel obţinând gradul minim egal cu 9 şi 100 de puncte.

De notat că generarea de soluţii non-particulare (aleatoare) cu grad minim ridicat este dificilă. Maximul pe care l-am obţinut noi este 3.

Perioada01

Solutie 1: Complexitate O(p * numar_divizori_de_p)

Observatie: Daca definim o perioada ca o pereche de numere (k,t), unde t este lungimea perioadei si k este de cate ori apare (si evident k * t = n, n fiind lungimea sirului), observam ca desi t poate fi oricat de mare, k trebuie sa fie atat divizor a lui n cat si a lui p (daca sirul are o perioada care apare de k ori si perioada are cel putin un 1, inseamna ca avem cel putin k de 1, deci k <= p si mai mult k|p). Putem fixa k (un divizor a lui p) si verificam in O(p) daca sirul este periodic sau nu (din moment ce sunt p de 1, perioada de lungime t o sa aibe p/k de 1 si verificam daca acestia se afla la distante egale)

Aceasta solutie ar trebui sa obtina 60 de puncte, dar o implementare optimizata poate sa obtina si 100 lejer.

Solutie 2: Complexitate O(Suma_divizorilor_lui_p)

Extindem solutia precedenta. Dupa ce am fixat k, nu o sa verificam in O(p) daca sirul este periodic, o sa facem in O(k). Mai exact o sa hashuim cele p pozitii la inceput si o sa facem sume partiale pe hashuri. Dupa ce am fixat divizorul k, observam ca avem k bucketuri care trebuie sa fie egale. Din moment ce avem sumele partiale pe hashuri, putem verifica bucketul 1 cu bucketul 2, bucketul 2 cu bucketul 3, etc. Cum pentru un divizor k o sa facem O(k) => complexitatea totala este O(Suma_divizorilor_lui_p).

Aceasta solutie ar trebui sa obtina 100 de puncte.

Solutie 3 (solutie participanti): O sa creem vectorul diferentelor si observam ca problema se reduce la aflarea perioadei minime din vectorul de diferente. Perioada minima se poate determina foarte simplu cu KMP (perioada minima este n - phi[n], daca exista). Problema in acest caz este foarte asemanatoare cu problema Perioada2.

Aceasta solutie are complexitate O(p) si ar trebui sa obtina 100 de puncte.

Disconnect

Una din posibilele rezolvări brute este de a reface la fiecare tăiere componentele conexe şi a reticheta nodurile conform componentelor actuale. Acest lucru ar presupune parcurgerea în întregime a unui subarbore (oricare) din cei doi subarbori obţinuţi la fiecare tăiere. Această soluţie are complexitate O(n2 + m), deoarece efectuăm maxim n - 1 tăieri iar fiecare parcurgere poate face O(n) paşi.

Pentru a obţine o soluţie mai eficientă facem următoarea observaţie

Observaţia 1 Dacă am reuşi ca la fiecare tăiere să parcurgem pentru reetichetare subarborele mai mic, atunci complexitatea tăierilor s-ar amortiza la O(n log n).

Pentru a demonstra acest lucru putem număra de câte ori va fi reetichetat în cazul extrem un anumit nod fixat X. Având în vedere că fiecare reetichetare ne spune despre X că se află în subarborele mai mic rezultat din tăiere, iar că acest subarbore are cel mult jumătate din dimensiunea subarborelui original, concluzionăm că dimensiunea componentei în care se află X se injumătăţeşte (cel puţin) la fiecare etichetare a lui X. Acest lucru nu se poate întâmpla de mai mult de O(log N) ori.

Cum ne dăm totuşi seama care este subarborele mai mic în timp util?

Observaţia 2 Dacă la tăierea muchiei X - Y pornim în paralel două parcurgeri din nodul X şi din nodul Y, având grijă să le oprim pe ambele atunci când una din ele se blochează, vom vizita 2 * mărimeaSubarboreluiMaiMic noduri, deci vom menţine complexitatea dorită de O(mărimeaSubarboreluiMaiMic) per tăiere.

Termenul problematic în observaţia de mai sus este "paralel". O opţiune pentru a implementa această idee este de a porni două DFS-uri iterative din fiecare nod, având grijă să înaintăm parcurgerea cu exact o muchie, alternativ, pentru X şi pentru Y.

O altă opţiune, mai uşor de implementat, este să pornim în mod repetat DFS-uri obişnuite din ambele noduri, dar limitând de fiecare dată numărul maxim de noduri pe care-l poate atinge o parcurgere. Setând această limită iniţial la valoarea 1 şi dublând-o succesiv până când una din parcurgeri nu atinge limita de noduri obţinem complexitatea O(mărimeaSubarboreluiMaiMic). Pentru a demonstra acest lucru, ne vom uita la numărul de operaţii făcut în total:

Operaţii = 2 * (1 + 2 + 4 + ... + 2K), unde K este cea mai mică valoare pentru care 2K > mărimeaSubarboreluiMaiMic. Această expresie este echivalentă cu 2 * (2K + 1 - 1), deci limitată de 4 * mărimeaSubarboreluiMaiMic.

Am reuşit astfel să determinăm subarborele mai mic în timp liniar relativ la mărimea sa, ceea ce ne permite să obţinem per total O(n log n + m), complexitatea dorită.

O rezolvare în O(n log n + m log n) care ar fi liniarizat arborele şi ar fi rezolvat query-ul numărând muchiile încă active între cele două noduri folosind un arbore de intervale/arbore indexat binar ar fi luat de-asemenea 100 de puncte. De-altfel aceasta a fost soluţia găsită de majoritatea concurenţilor.

Spectacole

Aceasta problema admitea multe solutii partiale, si o sa incepem cu cateva din ele.

Pentru 20 de puncte Ai = Bi = 0. Cu putina atentie se observa ca asa obtinem probelam spectacolelor clasica unde solutia este greedy, se ordoneaza spectacolele dupa capatul din dreapta si se ia mereu primul spectacol care nu se intersecteaza cu ultimul ales.

Pentru 30 de puncte N si yMaxim erau relativ mici. Putem obtine o solutie in O(N2 * yMaxim) folosind programare dinamica. Astfel facem o dinamica dp[i][j] = cate spectacole putem viziona maxim fiind la momentul i in sala j. Observam ca dp[i][j] = maximul dintre

  • dp[i - 1][j]
  • dp[k][j] + 1 cand exista un spectacol in sala j care incepe la momentul k si se termina la momentul i
  • dp[i - A[k] - B[j]] pentru a schimba din sala k in sala j.

Pentru 50 de puncte se mai poate face o observatie. Pentru a ne muta din sala k in sala j nu trebuie sa luam toate cele N^2 cazuri, putem sa folosim chiar enuntul si sa trecem prin sala centrala, pecare o putem numerota cu 0. Astfel dp[i][ 0 ] este egala cu maximum dintre

  • dp[i - 1][ 0 ]
  • dp[i - A[j]][j] pentru a trece din sala j in sala centrala

iar dp[i][j] cand j > 0 e maximul dintre

  • dp[i - 1][j]
  • dp[k][j] + 1 cand exista un spectacol in sala j care incepe la momentul k si se termina la momentul i
  • dp[i - B[j]]0 pentru a schimba din sala centrata in sala j

De mentionat ca trebuia tratata bine dinamica asta cand Ai si Bi puteai fi 0. Complexitatea acestei solutii este O(N * yMaxim)

Pentru 100 de puncte putem scoate cateva observatii. Sa presupunem ca suntem in sala j la momentul i si am vizionat un spectacol. Atunci ori putem ramane pana la alt spectacol din aceasta sala ori daca vrem sa vedem un spectacol din alta sala putem sa plecam direct in sala centrala si sa asteptam acolo. Daca suntem in sala centrala si vrem sa vedem un spectacol la momentul de timp i' in sala j' atunci putem astepta pana in ultimul moment in sala centrala si sa plecam sa ajungem chiar atunci cand incepe spectacolul in sala lui respectiva.

Astfel observam ca ne intereseaza putine perechi (momente de timp, sala) doar momentele de inceput si de sfarsit la fiecare spectacol + momentele la care am ajunge in sala centrala daca plecam fix dupa ce se termina un spectacol, si momentele la care trebuie sa fim in sala centrala sa ajungem la inceputurile unui spectacol. In total ele pot fi maxim 4 * M perechi. Se poate implementa dinamica de la 50 de puncte cu un graf. Astfel numerotam perechile, iar daca dintr-o pereche (i, j) ajungem la perechea (k, l) vizionand 0 sau 1 spectacole putem trage o muchie intre numerele corespunzatoare perechilor cu valoarea 0 sau 1. Mai trebuie sa tragem muchii de lungime 0 intre orice 2 momente succesive din aceeasi sala, ele reprezinta momentele cand asteptam intr-o sala.
Acum putem doar sa parcurgem graful si sa-i folosim muchiile pentru dinamica si vom obtine o complexitate de O(M * log M).