Solutii FMI No Stress 2010

Nc

Se va citi textul linie cu linie si se va parsa in functie de semnele de punctuatie. Daca exista o litera urmata de un caracter diferit de litera inseamna ca tocmai s-a terminat un cuvant si se incrementeaza numarul de cuvinte din fraza curenta.

Qtri

Fie (A, B, C) un triunghi si D un punct in plan. Punctul D se afla in interiorul triunghiului (A, B, C), daca si numai daca aria triunghiului este egala cu suma ariilor triunghiurilor formate din cate doua puncte adiacente din triunghi si punctul D. Doua puncte sunt adiacente, daca exista o latura care le uneste. Complexitate finala O(Q).

Grarb

Un arbore este un graf conex cu N-1 muchii. Astfel, daca graful G este format din X componente conexe, pentru ca G sa devina conex trebuie adaugate minim X-1 muchii, iar pentru a ramane cu N-1 muchii trebuie eliminate M+X-N muchii.

Kbiti

Se observa foarte usor ca solutia pentru orice sir format doar din valorile 0 si 1 reprezinta de fapt numarul asociat acestuia in baza 10, la care se mai adauga valoarea 1 (sirul format doar din valoarea 0 este primul in ordine lexicografica). Deci, putem raspunde pentru fiecare query in parte in O(L), de unde rezulta complexitatea O(T * L).

Difprim

Solutia 1: Se parcurge intregul interval [A, B]. Pentru fiecare numar N din intervalul respectiv se verifica in O(sqrt N) daca acesta este prim sau nu. Se retine diferenta maxima dintre oricare doua numere prime consecutive si cele doua numere. Complexitatea este O((B - A) sqrt B). Aceasta solutie obtine 50 de puncte.

Solutia 2: Se genereaza cu ajutorul ciurului lui Erathostene toate numerele prime X <= B. Se retine diferenta maxima dintre oricare doua numere prime consecutive care se afla in intervalul [A, B] si cele 2 numere. Complexitatea este O(B log log B). Aceasta solutie obtine 100 de puncte.

Trebuie in ambele solutii tratat cazul in care nu exista cel putin doua numere prime in interval ( pentru aceasta afisam -1 ).

Rk

Solutia 1 : timp: O(N + Q*N) memorie: O(N) - 20 puncte
Pentru fiecare intrebare se parcurg toate numerele si se verifica daca restul corespunde.

Solutia 2 : timp: O(K*N + Q) memorie: O(K*2K) - 50 puncte
Tinem intr-o matrice A[i][j] = cate numere dau restul j la impartirea prin 2i, astfel pentru fiecare numar X citit incrementam A[i][X % 2i]. Solutia pentru fiecare query se va afla in A[k][R]. Aceasta solutie foloseste insa limiteaza valoarea maxima a lui K pentru ca se foloseste prea multa memorie, si va obtine in jur de 50 de puncte.

Solutia 3 : timp: O(N*K + Q*K), memorie: O(N*K) - 100 puncte
Cand calculam restul impartirii unui numar X la 2K de fapt retinem ultimii K biti ai lui X. Vom construi un arbore binar si vom introduce numerele citite in arbore astfel: pentru fiecare din ultimii K biti, daca bitul curent este 0 mergem in nodul din stanga, altfel in nodul din dreapta, si pentru fiecare nod parcurs retinem de cate ori am ajuns in el. Pentru a raspunde intrebarilor vom parcurge arborele in mod similar considerand reprezentarea binara a lui R si vom returna valoarea retinuta in nodul in care am ajuns.

Solutia 4 : spatarelDan-Constantin Spatarel •spatarel - 100 puncte

  1. Consideri toti cei 32 de biti ai unui numar din sirul dat si il oglindesti in baza 2.
  2. Sortezi vectorul obtinut anterior.
  3. Pentru un query (R, K), il consideri pe R in baza 2 si il oglidesti normal. Adaugi 0 la finalul numarului pana cand acesta are K biti. Cauti folosind o cautare binara cate valori exista intre numarul obtinut anterior completat cu 0 pana 32 de biti si numarul obtinut anterior completat cu 1 pana la 32 de biti, si afisezi numarul valorilor.

Palalila2

Notam cu N lungimea sirului.

Solutia 1. timp O(N2), memorie O(N) - 50 puncte
Tinem doi vectori:

  • A[i] = lungimea maxima a unui subsir zig-zag care se termina pe pozitia i si ultimele doua caractere sunt in ordine ascendenta
  • B[i] = lungimea maxima a unui subsir zig-zag care se termina pe pozitia i si ultimele doua caractere sunt in ordine descendenta

Pentru doua pozitii 1 ≤ i < j ≤ N

  • Daca S[i] < S[j] atunci A[i] = max(A[i], B[j] + 1)
  • Daca S[i] > S[j] atunci B[i] = max(B[i], A[j] + 1)

Solutia va fi valoarea maxima obtinuta in cei doi vectori.

Solutia 2. timp O(N * SIGMA), memorie O(N * SIGMA) - 70 puncte
Solutia foloseste programare dinamica. Tinem doua matrice:

  • A[i][j] = lungimea maxima a unui subsir care se termina cel mult pe pozitia i, cu caracterul j si ultimele doua caractere sunt in ordine ascendenta
  • B[i][j] = lungimea maxima a unui subsir care se termina cel mult pe pozitia i, cu caracterul j si ultimele doua caractere sunt in ordine descendenta

Obtinem relatia de recurenta :

  • A[i][ S[i] ] = max( B[i - 1][ k < S[i] ] + 1 )
  • B[i][ S[i] ] = max( A[i - 1][ k > S[i] ] + 1 )

Solutia 3. timp O(N * SIGMA), memorie O(SIGMA) - 100 puncte
Plecand de la solutia anterioara observam ca la pasul i se modifica doar valorile din A[i][ S[i] ], respectiv B[i][ S[i] ], iar calculul acestor valori implica doar ultima linie din matrice, deci putem reduce memoria folosita la un singur vector de dimensiunea alfabetului.

Solutia 4. timp O(N), memorie O(N) - 100 puncte spatarelDan-Constantin Spatarel •spatarel
Sa presupunem ca avem sirul inital V, trebuie parcursi repetitiv urmatorii pasi :

  1. Se parcurge sirul atata timp cat V[ i ] ≥ V[ i + 1 ] sau se termina.
  2. Se parcurge sirul atata timp cat V[ i ] ≤ V[ i + 1 ] sau se termina.
  3. Se revine la pasul 1.

Solutia se incrementeaza la primii doi pasi.

Aceasta solutie poate fi imbunatatita ca si memorie, folosindu-se un singur caracter, doar ca aceasta citire este mai costisitoare ca si timp.

Joculet

Problema se rezolva cu ajutorul programarii dinamice. Se construieste o matrice D[i][j] - diferenta maxima pe care o poate obtine jucatorul aflat la mutare. Recurenta se obtine destul de usor, si anume:

  • D[i][i] = V[i], 1 ≤ i ≤ N
  • D[i][i + 1] = max(V[i] - V[j], V[j] - V[i], V[i] + V[j]), 1 ≤ i ≤ N - 1
  • D[i][j] = max(D[i][j], V[i] + V[j] - D[i + 1][j - 1]), 1 ≤ i ≤ j ≤ N, j - i ≥ 2

Solutia se va afla in D[1][N].
Pentru a obtine insa 100 de puncte nu trebuie retinuta intreaga matrice, ci doar ultimele doua-trei diagonale. Complexitate finala O(N2).

Knumere

In primul rand se observa ca cele K numere care trebuie eliminate la fiecare pas se afla la unul dintre cele doua capete. Daca am extrage un numar care nu se afla la unul dintre cele doua capate, atunci s-ar maximiza diferenta dintre numarul anterior si cel imediat dupa, deoarece numerele sunt ordonate crescator.

Solutie 1: Se parcurg toate secventele de dimensiune N - K din vectorul initial. Pentru fiecare secventa se calculeaza diferenta maxima intre oricare doua numere consecutive si se retine aceasta diferenta. La sfarsit se va afisa minimul dintre aceste diferente maxime. Complexitatea este O(N2). Aceasta solutie obtine doar 40 de puncte.

Solutie 2: Un vector de dimensiune N din care se extrag K valori va contine la sfarsit exact L = N - K numere. Vom construi in cele ce urmeaza un nou vector V, unde in V[i] vom retine diferenta dintre numerele aflate pe pozitia i + 1 si i, pentru 1 ≤ i < N. Nu ne mai ramane decat sa luam toate secventele de dimensiune L - 1 din vectorul V, sa aflam diferenta maxima pentru oricare secventa si sa afisam minimul dintre acestea. Acest lucru il putem determina foarte usor folosind un deque. Complexitatea este O(N). Aceasta solutie obtine 100 de puncte.

Solutia 3 : spatarelDan-Constantin Spatarel •spatarel - 100 puncte
Se cauta binar solutia. In acest sens, trebuie implementata o functie prin care sa se verifice daca pentru un numar D exista o subsecventa a sirului de intrare de lungime cel putin N - K, in care oricare doua elemente consecutive au diferenta <= D.

Solutia are o complexitate de O(N log D), unde D = 2 * 109, diferenta maxima dintre doua numere consecutive. Solutia poate obtine totusi 100 de puncte deoarece nu se foloseste niciun fel de structura de date.

Sabotaj

Problema este echivalenta cu determinarea unei taieturi minime intr-un graf neorientat. Rezolvarea se poate face cu flux sau cu algoritmul descris aici.