[short]

Pentru cei care cumva iau MLE, merge si cu short sa declarati matricile in loc de int 

Poate au avut sau vor mai avea si altii problema optimizarii, desi e destul de standard. In rezolvare se folosesc 2 matrice, iar din recurentele termenilor generali ai matricelor reiese clar ca un element A[j] depinde doar de A[j-1], deci n-are rost sa retin efectiv o matrice, ce doar un vector A[], pe care sa-l completez de fiecare data cand parcurg o linie.
Dar cea mai importanta optimizare ar fi in cadrul matricei best[][] care imi ofera si solutia. best[j] nu depinde decat de best[i-1][j-1] si de A[j], ceea ce inseamna ca, de fapt, este nevoie de retinerea doar a 2 linii din matrice, caci pe a doua o completez cu ajutorul primei.

Mai ramane de facut interschimbarea liniilor, dar n-are rost sa o copiez integral pe a doua in prima, ci, daca notam L0 prima linie cu care lucram si cu L1 a doua linie, matricea best[n][m] se reduce la best[2][m], iar L0 = 0 si L1 = 1 (initial).
Functia care imi permite "interschimbarea" celor 2 linii este f(x) = 1 - x (din 1 imi face 0 si din 0 face 1). Dupa fiecare parcurgerea a unei linii imi voi interschimba liniile la modul L0 = 1 - L0 si L1 = 1 - L1. Sper ca v-am fost de ajutor! 

primul comentariu la problema asta are mare dreptate.

bool viz[5000555];
queue <long long int> q;
long long int nr1, nr2, nr3, nr4, N, P, rest,x;

pe memoria asta iau Memory Limit Excedeed

iar dupa ce le dau unsigned la 8 variabile, 100p 

bool viz[5000555];
queue <long long int> q;
unsigned long long int nr1, nr2, nr3, nr4, N, P, rest,x;

 

Salut. Am incercat problema si iau 28 de puncte. Ideea si chiar implementarea au fost simplute, dar se pare ca nu si eficiente.
1) am completat vectorul A cu divizorii lui n pe care apoi urmaresc sa ii permut astfel incat sa satisfaca conditia;
2) mi-am dat seama ca impartirea asta A/A[i+1] sau A/A[i+1] inseamna div1/div2 si rezultatul este tot un divizor al lui n. Exemplu:
n= f1^k1 * f2^k2 * ... f3^k3
div1= f1^exp1 * f3^exp2 * f10^exp3
div2= f1^exp4 * f3^exp5 * f10^exp6

de dragul discutiei sa zicem ca exp1=exp4 si exp2=exp5, iar exp3=exp6+1;

atunci div1/div2=f10^1, adica f10 (un factor prim)

deci folosesc un vector 1/0  (sau true/false) destul de mare ca dimensiune

bitset <1000000005> f;  /// unde f= 1, daca i = factor prim in descompunerea lui N
                                                  = 0, altfel
SI ATUNCI AM DESCOMPUS n-ul in factor primi, completand totodata vectorul f.

3) am implementat un backtracking recursiv de generare a permutarilor multimii divizorilor unde criteriul de validare este alcatuit din 2 chestii:
a) v=0, adica sa nu fi pus deja divizorul cu indicele i in stiva
b) f[cat]=1, adica cat=nr1/nr2 sa fie numar prim...

Este ineficienta metoda? De ce iau Time Limit Exceeded pe atat de multe teste?