Revizia anterioară Revizia următoare
Cifre3
Prima observatie utila ar fi ca daca adaugam un numar convenabil de 1 in fata numerelor valide mai mici decat ( B-1 )10 obtinem solutiile anterioare deci putem reduce problema la intervalul
[ (B-1) 10 , B10-1 ] .
In continuare trebuie sa analizam numarul maxim de solutii care ar putea aparea: 9 = 32 , 8 = 23 , 5=5 , 7=7 , iar B <= 20. Deci avem maxim 60 factori de 2 , 40 factori de 3 , 20 factori de 5 , 20 factori de 7. 60 * 40 * 20 * 20 = 960 000. Deci avem 960 000 de cazuri de tratat , insa numarul de solutii va fi mult mai mic datorita faptului ca , de exemplu daca adaugam un 8 atunci nr de factori de 2 creste cu 3 dar restul nu vor mai putea creste doar pana la 38 , 19 si 19. De aici se pot intui mai multe solutii.
1. Putem folosi un backtracking. Acesta solutie este probabil cea mai la indemana deoarece ne permite memoria sa retinem o matrice ( folosind bitset ) 4D in care sa marcam numerele deja folosite. Daca construim aceasta matrice cu bitset ne vom incadra in memorie. Problema complexitatii nu va aparea datori faptului ca backul va merge pana la numarul de solutii si va verifica doar numerele de la 2 la 9. Datorita nr mic de solutii aceasta solutie va merge in practica destul de repede ( 16ms worst case ).
2. Iteram prin toate cele 960000 de descompuneri posibile. Mai ramane de rezolvat o problema: avand o descompunere 2a * 3b * 5c * 7d, se poate obtine ca produs de cel mult B cifre? Pentru factorii 5 si 7, trebuie folosite c + d cifre (c cifre de 5 si d cifre de 7). Acum, pentru puterile lui 2, este optim ca folosind o singura cifra de 8 sa reduc a-ul cu 3. Dupa ce nu se mai poate scadea 3 din a (a < 3), am 3 posibilitati:
- folosesc o cifra de 6 si obtin un a si un b mai putin in descompunere
- folosesc o cifra de 4 si obtin si obtin 2 de a mai putin in descompunere
- folosesc o cifra de 2 si obtin un a mai putin de descompunere
Aceeasi situatie se intampla si pentru 3. Folosind greedy, este optim sa iau cat mai mult posibil. Intai o sa aplic cazul 2 pe numerele a si b. Daca atat a cat si b ajung 1, le aplic 1. (folosind o cifra de 6, in loc de una de 2 si una de 3) Altfel, folosind cazul 3 o sa iau cifra. Acum am numarul de cifre minim (adunand toate numerele de mai sus) pentru care se poate obtine descompunerea 2a * 3b * 5c * 7d. Daca este <= B, atunci descompunerea e valida.
3. Se poate deduce o formula de recurenta bazandu-ne pe rezultatul anterior. Aceasta solutie poate obtine rezultatul in O(B).
4.Problema admite si solutie in O(1). Conform primei observatii , avem nevoie doar de numerele de B cifre.Astfel ca: SOL = ((B+1)*(B+2)/2)2 . Pentru cazul B>1 se poate obtine si produsul 0 , astfel ca incrementam SOL cu o unitate.
Culori4
Switch
Observam ca daca amandoua matricele au acelasi numar de elemente de 1 atunci intotdeauna o putem obtine pe una din cealalta. Daca executam o operatie asupra unei matrice atunci fie nu se schimba numarul de elemente de 1 (cand cele doua elemente sunt diferite) fie creste sau scade cu 2 (cand sunt egale). Din aceste observatii rezulta ca daca diferenta dintre numarul de elemente de 1 ale celor doua matrice este para atunci se poate transforma prima matrice in a doua.
Triangles
Pentru inceput sa analizam modul in care ar trebui sa arate cele K laturi selectate.Sa le notam cu x1,x2,...,xK,unde x1<=x2<=...<=xK.Conditia necesara pentru ca 3 numere a,b,c sa reprezinte laturile unui triunghi (chiar si degenerat) este ca a+b>=c,a+c>=b si a+b>=c. Daca presupunem a<=b<=c,atunci singura conditie necesara de verificat va fi a+b>=c. Acum sa ne reintoarcem la selectia noastra de K laturi. Pentru ca selectia sa fie valida trebuie doar ca suma celor mai mici 2 laturi sa fie mai mare decat cea mai mare latura,adica x1+x2>=xK.
1.Solutia O(N*log N) care nu se incadreaza in timp ar fi sortarea sirului de N laturi + parcurgerea lui pentru verificarea conditiei de mai sus pentru fiecare subsecventa de lungime K.
2.Solutia O(N*log K) care ia 100pct este aceea de a citi primele K numere dintre cele N,a le pune intr-un min-heap (retinand si elementul maxim din el intr-o variabila) si verificarea conditiei.Daca conditia este verificata atunci afisez elementele din heap,altfel scot minimul din heap,citesc un nou numar,il introduc in heap actualizand elementul maxim din heap din variabila auxiliara si continui verificarea pana gasesc o solutie de afisat.
