Blog infoarena

Problema saptamanii - Scorpion

Cosmin
Cosmin Negruseri
28 septembrie 2010

Continuam cu o problema clasica de teoria grafurilor:

Spunem ca un graf neorientat cu n noduri ca e de tip scorpion daca are trei noduri speciale pe care le numim acul, coada si corpul. Acul are gradul 1 si este legat de coada. Coada are gradul doi si e legata de ac si de corp. Corpul are gradul n - 2 si e legat la toate nodurile din graf cu exceptia acului. Celelalte noduri pot fi conectate oricum intre ele. Se cere sa se determine in O(n) intrebari de genul "Sunt nodurile i si j vecine?" daca graful este scorpion sau nu.

Puteti trimite solutii pe adresa cosminn at gmail.com

 Comentarii (5)

Categorii: potw

Problema saptamanii - Minim local

Cosmin
Cosmin Negruseri
12 septembrie 2010

Saptamana aceasta avem o problema ce vroiam sa o folosim ca problema simpla in una din zile la Olimpiada Europei Centrale de Informatica (CEOI 2009). Ea s-a dovedit a fi destul de cunoscuta fiind deja folosita in alte doua concursuri la care participasera unii dintre concurenti.

Se da o matrice A de 1000×1000 de numere intregi distincte. Putem pune intrebari de tipul "care este valoarea elementului A[x][y]". Dati un algoritm ce gaseste un minim local in aceasta matrice folosind cel mult 3100 de intrebari. Un element este minim local daca este mai mic decat cele patru elemente vecine ortogonal in matrice.

Puteti trimite solutii la adresa cosminn at gmail.com

 Comentarii (4)

Categorii: potw

Problema saptamanii - Initializare (Solutie)

Cosmin
Cosmin Negruseri
03 septembrie 2010

Problema saptamanii curente a fost rezolvata de 13 cititori. Ea nu e asa dificila ca si problemele anterioare, dar e singura de vara asta care are o aplicatie practica.

Rezolvitori:

Andrei Grigorean, Radu Berinde, Andrei-Marius Teodorescu, Delia David, Andrei Dragus, Adrian Carcu, Ovidiu Gheorghioiu, Adrian Vladu, George Nachman, Laura Draghici, Paul Dan Baltescu, Mihai Feier si Mihai Calancea.

Solutie:
Notam umem sirul de U pozitii cu memoria neinitializata. Cum avem nevoie de operatii in timp constant am putea tine 1 sau 0 pe pozitia v din umem daca elementul v este in set sau nu. Din pacate memoria nu este initializata si astfel pot exista deja 0 si 1 prin sir care sa ne pacaleasca.

Pentru a scapa de problemele generate de memoria neinitializata folosim un al doilea sir, nmem, de lungime N ce il initializam pentru a verifica daca umem spune adevarul. La adaugarea unui nou element v in set, dupa ce au fost deja adaugate max elemente, il adaugam in nmem la final si pe pozitia v din umem punem valoarea max. Astfel putem testa daca un element este intradevar in set folosind conditia nmem[umem[v]] == v. Trucul e ca realizam o legatura bidirectionala care este reala pentru ca noi controlam sirul nmem.

Aveti aici niste cod in Python scris de George Nachman pe aceasta idee:

umem = newarray(U)
nmem = newarray(N)
max = 0

def contains(v):
  if v >= U:
    return False
  i = umem[v]
  if i >= max:
    return False
  return nmem[i] == v

def add(v):
  if contains(v):
    return
  umem[v] = max
  nmem[max] = v
  max += 1

 Comentarii (7)

Categorii: potw

Problema saptamanii - Initializare

Cosmin
Cosmin Negruseri
30 august 2010

Initializarea memoriei ajunge, in cazul unor algoritmi eficienti, sa incetineasca timpul total de executie. Saptamana asta incercam sa gasim o metoda ce evita aceasta problema.

Gasiti o structura de date ce reprezinta o submultime a multimii {0, 1, ... , U - 1}. Operatiile de initializare, adaugare si verificare a incluziunii trebuie sa se execute in timp constant in cazul cel mai nefavorabil (daca am cere timp constant pe cazul mediu, o solutie este sa folosim un hash table). Aveti la dispozitie o zona de memorie continua in care incap U intregi ce nu e initializata, deci contine valori oarecare. Puteti folosi memorie suplimentara O(N), unde N este numarul de intregi ce vor fi adaugati in multime.

Ca de obicei puteti trimite solutii sau propuneri de probleme pe adresa cosminn at gmail.com

 Comentarii (0)

Categorii: potw

Problema saptamanii - Segmente (Solutie)

Cosmin
Cosmin Negruseri
29 august 2010

Saptamana asta am avut o problema de matematica, dar care avea nevoie de cunostinte elementare.

Rezolvitori:
Dumitru Daniliuc, Andrei Dragus, Mihai Damaschin, Adrian Vladu si Andrei Marius Teodorescu.

Solutie:
Proiectam segmentele pe Ox si pe Oy. Suma lungimilor proiectiilor va fi mai mare sau egala cu 18. Asta inseamna ca cel putin una dintre cele doua sume a lungimilor proiectiilor verticale sau a lungimilor proiectiilor orizontale va fi mai mare sau egala cu 9. Presupunem fara a restrange suma aceasta este realizata pe axa Ox.

In cazul in care o suma este strict mai mare decat 9, vom avea un punct pe Ox unde au fost proiectate puncte de pe 10 sau mai multe segmente si putem astfel duce prin acel punct o dreapta paralela cu Oy ce va intersecta cel putin 10 segmente.

In cazul in care ambele sume sunt egale cu 9 si nu exista nici un punct pe o axa cu cel putin 10 puncte proiectate in el, rezulta ca avem doar segmente verticale si orizontale, iar fiecare in fiecare punct de pe axe sunt proiectate exact noua segmente paralele cu axa respectiva. Astfel, alegem orice dreapta suport a unui segment vertical si acesta va intersecta exact 9 segmente orizontale.

 Comentarii (0)

Categorii: potw

Problema saptamanii - Segmente

Cosmin
Cosmin Negruseri
23 august 2010

Daca stiti probleme interesante care s-ar potrivi la "Problema saptamanii" va rog sa mi le trimiteti pe email. Problema saptamanii ar trebui sa nu fie foarte cunoscuta, sa aiba o rezolvare ingenioasa dar care nu are multi pasi si prefer sa fie legata cat de cat cu programarea, dar poate fi si de matematica.

Continuam cu urmatoarea problema:

Patratul [0, 1] x [0, 1] contine niste segmente cu suma lungimilor egala cu 18. Sa se demonstreze ca exista o dreapta ce intersecteaza cel putin 10 din aceste segmente.

Puteti trimite solutii sau propuneri de probleme la adresa cosminn at gmail.com

 Comentarii (2)

Categorii: potw

Problema saptamanii Duplicate - Solutie

Cosmin
Cosmin Negruseri
20 august 2010

Am aflat problema anul trecut de la Mihai Patrascu. Ea e pe stilul multor intrebari din interviuri de joburi de programare. Are aplicatii in multe contexte cum ar fi in baze de date unde vrem sa detectam obiecte duplicate, pentru motoare de cautare unde vrem sa detectam pagini ce se repeta in index sau la monitorizarea traficului pe retele unde se incearca detectarea de anomalii. Ea a fost abordabila, fiind solutionata de 16 cititori.

Rezolvitori:
Dumitru Daniliuc, Andrei Grigorean, Tiberiu Savin, Andrei Dragus, Alex Mosoi, Marius Pungaru, Adrian Vladu, Marius Andrei, Daniel Dumitran, Marius Dragus, Andrei Marius Teodorescu, Laura Draghici, Delia David, Adrian Airinei, Armand Rotaru si Stefan Istrate.

Solutie:
Fie x = [sqrt n]. Tinem un sir de x pozitii F[i] cu frecventele elementelor pe intervalul [i * x + 1, (i + 1) * x]. Din principiul cutiei rezulta ca un interval va avea mai mult de x elemente in el. Prin o parcurgere al sirului aflam un astfel de interval. Cu o a doua parcurgere aflam frecventele exacte ale elementelor din intervalul respectiv folosind un sir de dimensiune x. Am determinat astfel un element duplicat folosind doua parcurgeri si memorie O(sqrt(n) log n) biti.

Daca facem k parcurgeri putem folosi memorie O(n^(1/k) * log n) biti.

Probleme inrudite:

Pentru probleme pe acelasi stil cu nivel de dificultate bun pentru interviuri tehnice pentru programatori puteti citi articolul Probleme cu numere lipsa si nu numai. Doua exemple:

1. Un sir de lungime n contine numere intregi din multimea {1, 2, ..., n-1}. Folosind Principiul lui Dirichlet deducem ca cel putin un element se repeta. Gasiti un algoritm liniar care afiseaza o valoare ce se repeta, folosind memorie suplimentara constanta si nemodificand la nici un pas vreun element din sir.

2. Se dau n numere de la 1 la n. Unul din ele apare in sir de doua ori, iar restul sunt distincte. Evident ca un numar nu va aparea niciodata. Sa se dea un algoritm cat mai eficient care sa determine numarul lipsa si numarul ce apare de doua ori.

Literatura:

Problema a fost studiata recent.

Finding duplicates in a data stream, P Gopalan, J Radhakrishnan - … of the Nineteenth Annual ACM-SIAM …, 2009 Aici se arata un algoritm randomizat ce foloseste o parcurgere si O(log^3(n)) memorie.

Finding a duplicate and a missing item in a stream, J Tarui - Proceedings of the 4th international conference on …, 2007 Aici se demonstreaza ca pentru algoritmi deterministi la k parcurgeri trebuie folosita cel putin O(n^(1/(2k - 1)) spatiu, iar pentru algoritmi ce folosesc doar O(log n) spatiu e nevoie de cel putin O(log n/log log n) parcurgeri.

 Comentarii (2)

Categorii: potw

Problema saptamanii - Duplicate

Cosmin
Cosmin Negruseri
14 august 2010

Continuam cu alta problema ceva mai simpla.

Se da un stream pe care il putem citi de un numar constant de ori. El contine n + 1 numere intregi de la 1 la n. Evident unul sau mai multe elemente apar de mai multe ori. Se cere sa se gaseasca un algoritm care gaseste un element duplicat in stream, parcurgand streamul de un numar constant de ori si folosind memorie mai mica decat O(n) biti. Un stream are metodele bool hasNext() si int getNext(), si e o abstractizare a unui set de date ce poate fi citit secvential.

Puteti trimite solutiile pe adresa cosminn at gmail.com

 Comentarii (2)

Categorii: potw

Problema saptamanii - Interclasare (Solutie)

Cosmin
Cosmin Negruseri
14 august 2010

Problema Interclasare a dat ceva bataie de cap membrilor comunitatii infoarena. Ma asteptam sa stie lumea ceva mai bine ce inseamna sortare stabila sau memorie suplimentara.

Solutie:

O abordare ar fi sa folosim metoda divide and conquer. Pentru a rezolva subproblema curenta, putem gasi in timp cel mult liniar mediana celor 2 siruri. Astfel vom avea patru secvente A1 A2 B1 B2, unde elementele din A1 si B1 sunt mai mici decat mediana iar elementele din A2 si B2 sunt mai mari decat mediana. Trucul principal din problema este cum putem ajunge din starea A1 A2 B1 B2 in A1 B1 A2 B2 in timp liniar si folosind memorie suplimentara constanta. Pentru asta putem inversa ordinea elementelor din secventa A2 B1 ca sa obtinem o secventa B1' A2' unde B1' e secventa B1 inversata iar A2' e secventa A2 inversata. Apoi putem inversa secventele B1' si A2' pe rand pentru a obtine sirul format din secventele A1 B1 A2 B2. Toate elementele din A2 B2 sunt mai mari decat elementele din A1 B1, deci am obtinut doua subprobleme de lungime (m + n) / 2 similare cu problema initiala. Astfel obtinem un algoritm de complexitate O((n + m) log (n + m)) ce foloseste memorie suplimentara O(log (n + m)). Avem nevoie de memoria suplimentara pentru a tine starea stivei algoritmului recursiv. Pentru a obtine un algoritm ce nu are nevoie de stiva putem sa rezolvam tot timpul probleme si subprobleme ce au dimensiuni egale cu puteri ale lui doi. Alta idee sa parcurgem sirul nostru si sa aplicam trucul anterior fiecaror doua secvente crescatoare consecutive.

E interesant ca problema poate fi rezolvata si in O(n + m) timp si O(1) memorie suplimentara, dar o asemenea rezolvare e mult mai complicata. Daca gasiti o abordare usor de explicat o veti putea publica ca lucrare de cercetare.

Rezolvitori:

Singura rezolvare completa pe ideea de mai sus a fost a lui Cosmin Gheorghe. Andrei Dragus a venit cu o solutie in O((n + m) sqrt(n + m)). Au mai rezolvat problema fara a face pasul de O(log (n + m)) la O(1) memorie Mihai Lazari, Stefan Istrate, Daniel Dumitran si Ionut Fechete.

Probleme de inrudite:

1.(CLRS, interviu) Se dau doua siruri sortate de lungime m si n, sa se determine in O(log (n + m)) timp mediana sirului obtinut prin interclasarea celor doua siruri.

2.(interviu Microsoft) Se da un sir de caractere de dimensiune n, sa se roteasca la dreapta cu k pozitii in timp O(n) si folosind memorie suplimentara O(1). De exemplu pentru "abcdef", n = 6, k = 2 trebuie sa obtinem "efabcd".

3.(interviu Microsoft) Se da un sir de caractere ce contine cuvinte separate prin spatii. Se cere sa se inverseze ordinea cuvintelor din sir in timp liniar si folosind memorie suplimentara constanta. De exemplu "Ana are mere" -> "mere are Ana".

4.(interviu Facebook) Se da un sir de obiecte X ce au chei de valori 0 sau 1. Se cere sa se sorteze stabil sirul de obiecte in complexitate mai buna de O(n^2) folosind memorie suplimentara constanta.

5.(Oni 2004) Sortare cu inversari http://infoarena.ro/problema/invsort

 Comentarii (2)

Categorii: potw

Problema saptamanii - Interclasare

Cosmin
Cosmin Negruseri
08 august 2010

Revenim dupa o pauza considerabila cu problema saptamanii. Problema s-a dat la un interviu de job in Cluj.

Se da un sir A de n + m numere intregi. Numerele de la 1 la n sunt in ordine crescatoare si numerele de la n + 1 la n + m sunt si ele in ordine crescatoare. Se cere sa se sorteze sirul in ordine crescatoare. Algoritmul trebuie sa foloseasca memorie suplimentara constanta, ordinea numerelor sa fie stabila, adica oricare doua numere egale din sir sa apara in aceeasi ordine dupa ce sirul a fost sortat, iar complexitatea algoritmului trebuie sa fie mai buna de O((n+m)^2).

Trimiteti solutii la adresa cosminn at gmail.com

 Comentarii (32)

Categorii: potw
Vezi pagina: 1 23 (30 rezultate)