Aiuto pronunceable words (ois words)

Ciao a tutti di nuovo
Questa volta mi trovo bloccato sulla risoluzione di words
Con una semplice dp di complessita’ O(n l) posso ottenere il numero di sequenze dato uno o piu’ trigrammi di partenza di ogni lunghezza da 3 a l caratteri (o da 0 a l-2 trigrammi)
Il problema sta nel ricavare la soluzione perche’ so quante stringhe terminano in con un trigramma ma non quante ce l’hanno all’inizio
Per fare questo potrei chiamare quella stessa funzione n volte ciascuna con un trigramma di partenza diverso, ma andrei nell’ordine di O(n^2 l)
Il codice lo posto solo per dimostrare che ci ho gia’ pensato su a lungo ma chiedo soltanto un hint
grazie in anticipo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;

ll n, l, k;
vector<string> t;
vector<vi> adj;
vector<vi> memo;

int main() {
   // trovo molto piu' sensato che k sia la k-esima parola in ordine
   // mentre n il numero di trigrammi
   cin >> k >> l >> n;
   l -= 2;
   // t e' il vettore contenente i trigrammi
   t.resize(n);
   // adj e' la lista di adiacenza
   adj.resize(n);
   // memo[i][j] contiene il numero di sequenze di lunghezza i trigrammi 
   // che terminano in t[j]
   // siccome per il calcolo di ogni valore si utilizza la riga
   // precedente allora si puo' tagliare a solo 2 righe
   memo.resize(2, vi(n));
   // assegnando 1 a tutta la riga il calcolo si applica a tutte le sequenze
   // assegnando 1 solo a determinati j si calcolano solo le sequenze che iniziano in t[j]
   memo[0].assign(n, 1);
   for (int i = 0; i < n; i++) cin >> t[i];
   // il sort permette di calcolare l'adiacenza in O(n log(n)) invece che O(n^2)
   sort(t.begin(), t.end());
   for (int i = 0; i < n; i++) {
      string s = t[i];
      // metodo brutale per ottenere le ultime 2 lettere del trigramma
      string bi = ""; bi += s[1]; bi += s[2];
      int low = lower_bound(t.begin(), t.end(), bi) - t.begin();
      bi += 'z'+1;
      int high = lower_bound(t.begin(), t.end(), bi) - t.begin();
      for (int j = low; j != high; j++)
         adj[i].push_back(j);
   }
   // b serve per decretare la riga corretta da leggere/scrivere
   // e si alterna ad ogni iterazione
   bool b = false;
   for (int i = 0; i < l-1; i++) {
      b = not b;
      for (int j = 0; j < n; j++) {
         for (auto u: adj[j]) {
            memo[not b][u] += memo[b][j];
            memo[not b][u];
         }
      }
   }
}

hint 1: per sapere quali sono i prossimi trigrammi che puoi mettere non ti serve tutto il trigramma precedente, ti bastano 2 lettere
hint 2: con una top-down (ricorsiva) puoi evitarti di calcolare tutto il dominio guardando quando superi k stringhe
per il resto mi sembra che sei nella direzione giusta, con sti 2 consigli dovresti riuscire a fare 100

Ho convertito la dp lineare in ricorsiva top down e ora so quante stringhe iniziano in t[i]
Pero’ sono ancora confuso sulla costruzione della soluzione perche’ riesco a fermare la dp solo dopo che ha calcolato tutte le stringhe che iniziano in t[i]. Dunque passo, ad esempio, da “50esima stringa di lunghezza l” a “t[i] + 13esima stringa di lunghezza l-1”

ll dp(int i, int j) {
   if (i == l-1) return 1;
   if (memo[i][j] != -1) return memo[i][j];
   ll res = 0;
   for (int u: adj[j])
      res += dp(i+1, u);
   memo[i][j] = res;
   return res;
}

int main() {
   for (int i = 0; i < n and k > 0; i++) {
      k -= dp(0, i);
   }
}

Questa e’ come si presenta l’array per la memoizzazione
memo[i][j] e’ il numero di sequenze di lunghezza l-i che iniziano in t[j]

23 11 16 0 23
16 7 11 0 16
11 5 7 0 11
7 4 5 0 7
5 2 4 0 5
4 1 2 0 4
2 2 1 0 2

Quando sei in un certo nodo dell’albero della dp, sai quante stringhe <= di tot hai, se quel numero e’ >= a k, allora sei gia troppo in la, quindi la soluzione passa per il figlio precedente. Vedi tu come utilizzare sta cosa, e’ da molto che non faccio sto esercizio e non so dirti su due piedi quale sia il modo piu comodo. In ogni caso cosi sai che ramo della dp e’ quello con la soluzione, quindi se ripeti sta cosa anche per i nodi dopo trovi tutta la soluzione.

Grazie mille per la dritta, l’ho risolto

Mi risulta ancora magia nera il metodo con cui si riesce a utilizzare solo un vettore monodimensionale per la memoizzazione; un vettore bidimensionale n*l e’ nell’ordine del 10^8, dunque sforava. Pero’ una buona vecchia hash map ha funzionato ugualmente bene perche’ la matrice veniva abbastanza larga