Problema Acronimi Forzati

Aiuto
1

Sono fermo da giorni su questo problema. Qualche indizio per risolverlo?
p.s. sono fermo a 75 punti, le ultime sottoposizioni escono fuori tempo massimo.

2

Prova a pensare a come puoi ottenere un acronimo partendo da uno più corto. Assomiglia al problema helloworld soltanto che al posto di hello e world hai le lettere dell’acronimo.

3

Non sono sicuro di aver capito bene il tuo suggerimento. Intendi ridurre la dimensione della stringa? Se sì, l’ho già fatto rimuovendo tutti i caratteri che non fanno parte dell’acronimo ma senza un miglioramento apprezzabile delle prestazioni.

4

Ridurre la dimensione della stringa non serve. L’idea di partenza è che un acronimo di lunghezza l è formato da un acronimo di lunghezza l-1 più l’ultima lettera. Prova a pensare quanti acronimi o parti di acronimo posso fare con un prefisso della stringa.

5

Anch’io avevo pensato a una cosa del genere, ma non capisco come implementarla, per ora mi è venuta in mente solo una soluzione ricorsiva che sicuramente non starebbe nel tempo massimo. Da quel che ho capito non bisogna provare ogni soluzione possibile, ma non capisco come fare…

6

Ah, ora capisco (credo) … Tuttavia c’è un problema e cioè che io gia utilizzo un metodo simile, non provo tutte le combinazioni possibili, solo che non saprei come rendere più veloce l’algoritmo.

7

Partendo dal caso facile con un acronimo di due lettere “ab” se una lettera è uguale ad “b” posso formare un acronimo con quella lettera e ogni “a” che viene prima. Pensate a come estenderlo ad acronimi più lunghi.

8

Grazie, a quanto pare ero sulla strada giusta… Alla fine comunque l’ho risolto con una dinamica top-down.

9

Penso di aver capito come implementare la tua idea, infatti ora non ho più il problema del tempo.
Gli ultimi subtask però mi danno risultato errato e non riesco a capire il motivo :sob:

for(i=0;i<(int)parola.size();i++){
    if(binary_search(acronimo.begin(),acronimo.end(),parola[i]))
        s.push_back(parola[i]);
}

for(i=0;i<(int)a.size();i++)
    possibili[i]=0;

for(i=0;i<s.size();i++){
    for(j=a.size()-1;j>0;j--)
        if(a[j]==s[i])
            possibili[j]=possibili[j]+possibili[j-1];

    if(s[i]==a[0])
        possibili[0]++;
    }

out<<possibili[a.size()-1]%1000000007;
10

Devi utilizzare l’operatore modulo ogni volta che effettui una somma, non soltanto sull’ouput :slight_smile:

Dal testo del problema:

11

Ma certo, che idiota che sono. Ora ho risolto,100 punti.
Grazie mille a tutti per l’aiuto :slight_smile: