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.
