621 Dusman

[•DITzoneC]

Aici puteţi discuta despre problema Dusman.

[•Bogdan_tmm]

Problema asta nu se face cu backtracking?

[•Florian]

Ba da. Te-a contrazis cineva? 

[•Bogdan_tmm]

Pai timpii scosi de unii )=))

[•Mishu91]

Avand in vedere ca limita lui K e de 10000, si ca tu trebuie sa iti generezi doar primele K solutii, timpii scosi cu back nu sunt foarte mari

[•Bogdan_tmm]

lasa k ... Uitate la n.Acum ma convinsei si eu ca e un back dar cam de 10 x mai rapid decat ce faceam eu

Mai am o nelamurire uriasa:|.Backtracku'l cu conditia de finalitate pusa inainte de for e mai rapid decat cel in care conditia e in for?Si daca "da", de ce? pe unele teste e cam de 2-3 ori mai rapid, poate si mai mult.Dupa parerea mea as zice ca executa acelasi nr de operatii

[edit] Editeaza-ti mesajele in loc sa postezi consecutiv
Edit : ok scz

[•icb_mn]

imi zice si mie cineva ce trebuie sa fac ca sa nu iau TLE ] (*,)

[•Schumi]

Tu generezi prea multe permutari. Incearca sa le generezi doar pe cele valide. Nu inteleg prea bine ce faci cu cele doua if-uri din back. Cel mai simplu cred ca ar fi sa iti retii o matrice de adiacenta pentru relatiile de dusmanie, iar in back sa faci o singura verificare si sa apelezi backul doar cu valorile bune.

[•ionut98]

Cum as putea sa-mi optimizez bkt-ul ca nu stiu am facut iterativ ca am crezut ca e mai rapid decat recursiv si am construit doar permutarile valide(sa nu am alaturati 2 dusmani si sa nu se repete un numar)

[•ionut98]

Cum as putea sa-mi optimizez bkt-ul ca nu stiu am facut iterativ ca am crezut ca e mai rapid decat recursiv si am construit doar permutarile valide(sa nu am alaturati 2 dusmani si sa nu se repete un numar): http://www.infoarena.ro/job_detail/1495128