Salve, sto provando a risolvere il problema petali solo che non riesco a superare gli ultimi 4 testcase in quanto il mio algoritmo va in timeout. Il mio algoritmo è questo:
Ciao, attualmente la tua complessità è \mathcal O\left(N\cdot d(N)\right)\le\mathcal O(N^{\frac{4}{3}}). Non credo si possa risolvere in \mathcal O(N) ma sicuramente si può fare di meglio.
Sia f(i,j) una funzione che vale 1 se è possibile creare una corolla di periodo i partendo da j e vale 0 altrimenti. Chiaramente f(i,j) vale 1 se e solo se i fiori in posizione j,j+i,j+2i,\ldots,j+\left(\frac{N}{i}-1\right)i sono tutti uguali. Tuttavia possiamo anche notare che f(i,j) vale 1 quando f(k\cdot i,j),f(k\cdot i,j+i),\ldots,f(k\cdot i,j+(k-1)i) valgono tutti 1 e i fiori in posizione j,j+i,j+2i,\ldots,j+(k-1)i sono tutti uguali.
Per cui scegliendo il più piccolo valore k tale che k\cdot i divide N, possiamo calcolare i valori di f(i,j) in ordine decrescente di i evitando molti controlli che abbiamo già eseguito. La risposta al problema è banalmente \sum_{i|N}\sum_{j=0}^{i-1}f(i,j). La complessità è \mathcal O(\text{un po' di più di }N).
Nota: il problema non richiede di stampare il risultato modulo 10^9+7 (anche perché il risultato è molto più piccolo di 10^9).
Da quanto mi sembra di aver capito nel primo esempio, per trovare la corolla con periodo 3 che parte dalla posizione 1 mi basta semplicemente controllare che ci siano due corolle con periodo 6 che partono una dalla posizione 1 e l’altra dalla posizione 4 invece di effettuare tutti i controlli.
12
2 2 3 1 2 3 2 2 2 1 2 1
le corolle sono:
2///2///2///
2/////2/////
/2//2//2//2/
/2/////2////
///1/////1//
////2/////2/
Ho provato ad implementare un algoritmo che sfrutti questo concetto utilizzando una matrice di booleani e costruendomi un sorta di albero dei divisori. Sfortunatamente riesco ad ottenere sempre 80/100.
Codice:
int solve(int N, int* S)
{
int cont=0;
vector<int> divisor;
//memorizzo i divisori in ordine crescente
divisor.push_back(1);
for(int i=2;i<=N/2;++i)
if(N%i==0)
divisor.push_back(i);
vector<int> pos(divisor.size(), -1); //mantengo memorizzato per ogni divisore la posizione del successivo numero che quello corrente riesce a dividere
/*
es:
n=12
divisori: 1, 2, 3, 4, 6
pos: 1, 3, 4, -1, -1
*/
for(int i=divisor.size()-1;i>-1;--i){
for(int j=i+1;j<divisor.size();++j)
if(divisor[j]%divisor[i]==0){
pos[i]=j;
break;
}
}
//inizializzo la mia matrice
vector<vector<bool>> flag(divisor.size());
for(int i=0;i<divisor.size();++i){
flag[i].resize(divisor[i]);
for(int j=0;j<divisor[i];++j)
flag[i][j]=true;
}
for(int i=divisor.size();i>-1;--i){
if(pos[i]==-1){
int exit=0;
for(int j=0, freq=0;j<N;++j, freq=(freq+1)%divisor[i]){
if(exit==divisor[i])
break;
if(S[j]!=S[(j+divisor[i])%N]&&flag[i][freq]){
flag[i][freq]=false;
++exit;
}
}
cont+=(divisor[i]-exit);
}
else{
int contFalse=0;
for(int j=0;j<divisor[i];++j)
for(int k=j;k<divisor[pos[i]];k+=divisor[i])
if(!flag[pos[i]][k]||S[k]!=S[j]){
flag[i][j]=false;
++contFalse;
break;
}
cont+=(divisor[i]-contFalse);
}
}
return cont;
}