237 Invcs

[ditzone]

Aici puteţi discuta despre problema Invcs.

[•Dastas]

Ce complexitate trebuie pentru 100 de puncte?

Cu un O(N!) optimizat cat stiu iau 30...

[•DITzoneC]

Parca O(2^N*N).

[•Dastas]

Nu ma prind . Cum s-ar face in complexitatea aia?

[•astronomy]

Gandeste-te de exemplu ce se intampla cand fixezi elementul maxim in permutare. Sa zicem ca incerci sa fixezi N pe o pozitie x, numarul de permutari valide ar fi numarul de permutari de N-1 elemente care pot fi asezate pe pozitiile 1..x-1,x+1..N care sa satisfaca conditiile.

[•raula_san]

nu imi intra in timp ... shi am facut (2^N*N)  ... iau 40

[•astronomy]

Incearca cu memoizare, de multe stari nu ai nevoie.

[•raula_san]

Ms ... a mers cu memorizare 

[•dutzul]

eu iau 30 de pcte cu un n^4*2^n.. nu stiu ce pot optimiza ;
eu fac asa , am o stare valida care foloseste doar numere din intervalul 1..i  si incerc sa bag un nou bit care reprezinta numarul i+1 astfel incat sa respecte conditia vectorului auxiliar.. nu intaleg cum se se foloseste memoizarea. mersi anticipat.