Ciao a tutti,
è da qualche giorno che sto provando a risolvere il Problema delle nazionali del 2007 senza mai riuscirci per via del timeout.
All’inizio sono partito con l’implementare una soluzione O(Nlog N) che però andava tristemente in timeout sui task 16 e 19, così ho implementato un algoritmo che tende a O(N) nei casi fortuiti sfruttando questa idea qui:
se N è divisibile per X (numero a caso), e ho già fatto una prova in O(N) per trovare quante sono (e da dove iniziano) le sequenze uguali di petali distanti X l’uno dall’altro, allora per controllare se vi sono anche delle sequenze uguali di petali distanti tra di loro Y (dove Y è un sottomultiplo di X e quindi anche di N) mi basta controllare solo se i primi X/Y petali di ognuna di queste possibili sequenze (che se ci sono hanno il primo petalo sempre nell’intervallo [0,Y) ) siano tutti dello stesso colore e che al contempo stesso siano i primi petali di una sequenza che va a salti lunghi X.
Ciò dovrebbe far si quando risulta possibile applicare questo ragionamento la ricerca di tutte le sequenze lunghe Y abbia complessità O(X) invece di O(N).
Questo è il mio codice:
#include <bits/stdc++.h>
using namespace std;
using vb = vector<bool>;
using vi = vector<int>;
//#def DEB
int bitmask[4000000];//sz=max_N/2
int *petali;
vi divisori;
///< Questo funziona
inline int test(int id, int N) //O(N)
{
int M = divisori[id];
int c {};
for(int j {}; j!=M; ++j)
{
for(int i {j+M}; i<N; i+=M)
{
if(petali[i-M] != petali[i]) goto next;
}
++c;
bitmask[j] |= 1<<id;///Partendo da j si forma una corolla con l'id-esimo divisore
next:
;
}
return c;
}
int solve(int N, int* petali)
{
if(N>8000000) abort();
::petali = petali;
int i {2}, val{}, conta{}, lim {sqrt(N)}, j, id, volte;
///< Trova tutti i divisori di N
for(i=2; i!=lim+1; ++i) //O(sqrt(N))
{
if(N%i == 0)
{
divisori.push_back(i);
if(i*i != N) divisori.push_back(N/i);
}
}
divisori.push_back(1);
sort(divisori.rbegin(), divisori.rend());///Li ordina in ordine decrescente
//for(auto x : divisori) cout << "\t" << x; cout << "\n";
///Per ogni divisore
for(i=0; i!=divisori.size(); ++i)
{
id = val =-1;
///Cerca se ne abbiamo già passato uno che è multiplo di quello attuale
for(j=0; j!=i; ++j)
{
if(divisori[j]%divisori[i]==0)///Lo identifica
{
id = j;
val = divisori[j];
}
}///E se ce n'è uno trova il più piccolo tra questi
if(val == -1) conta += test(i, N);///Se non è così si fa alla vecchia maniera
else
{
///I salti sono lunghi M
int M = divisori[i];
///Quanti valori vecchi vanno controllati?
volte = divisori[id]/divisori[i] -1;
for(int w {}; w!=M; ++w)
{
int x = w+M;
///Il primo valore della sequenza è conforme a quanto serve?
for(int k {}; k!=volte; ++k)
{
if(petali[x-M] != petali[x] || !(bitmask[x-M]&bitmask[x]&(1<<id))) goto next;
x += M;
}
++conta;
bitmask[w] |= 1<<i;
next:
;
}
}
}
///cout << "Conta = " << conta << endl;
return conta;
}
Adesso come adesso il codice ottiene 75/100 mentre se invece di usare lo stratagemma spiegato solo faccio lavorare solo la funzione test(…) ottengo 90/100 per timeout.
Qualcuno gentilmente potrebbe aiutarmi ad individuare il problema nell’algoritmo?
Grazie in anticipo.
P.S.:
Per chi questo problema lo ha già risolto: il testo del problema dice che i colori dei petali sono al massimo 32, cosa che io nello scrivere la mia soluzione ho ignorato beatamente. Questo 32 come limite superiore dovrebbe servire per rendere possibile applicare un qualche algoritmo di ordinamento stabile O(N) per separare gli indici dei petali dei vari colori e poi applicare qualche magia su questi valori per ottenere la soluzione o è messo completamente a caso (cosa che io dubito fortemente)?
Grazie a tutti quelli che avranno la pazienza di leggere tutto ciò. 