Problema Tracce Aliene

Ciao a tutti, qualche aiuto/suggerimento per risolvere questo problema?
Ho tentato fin da subito di evitare di provare tutte le soluzioni possibili, perché data la dimensione dei risultati avrei sicuramente problemi di tempo.
Quel che finora ho pensato è che, data la stringa S e l’intero K, calcolando L=k-s.size() trovo il numero di caratteri “liberi”, ossia quei caratteri che in una stringa di dimensione K non sono occupati da S. Ognuno di tali caratteri può variare da 0 a 9, per cui a rigor di logica le possibili combinazioni sono 10^L * N, dove N sono tutte le possibili posizioni che la stringa S può assumere all’interno di una stringa più grande di lunghezza K.

Ciò che non riesco ad implementare è il fatto che bisogna eliminare alcune possibilità.
Come si vede nel secondo caso d’esempio (K=6 , S=“210”), se si applica la formula detta sopra una stringa (“210210”) verrebbe conteggiata due volte: una quando S si trova all’inizio e una quando S si trova alla fine. Ho provato a capire come conteggiare il numero di queste possibilità, ma non riesco più a orientarmi, soprattutto se considero numeri K molto grandi dove la stringa S si può ripetere più di 2 volte.

Sono completamente fuori strada? C’è un modo per calcolare tali possibilità o devo seguire un approccio totalmente diverso?

Pensa a quante volte verrà conteggiata ogni stringa del tipo di 210210. Se avessi 210210210 (con S=“210”) oppure 10101010 (con S=“10”), quante volte verrebbero contate?
Un buon punto di partenza può essere il fatto che S termina sempre con zero e non lo contiene mai in altre posizioni - ovvero è della forma [1-9]*0

1 Mi Piace

Sostanzialmente viene conteggiata il numero di volte che appare…
ad esempio in “210210210” viene conteggiata 3 volte, mentre io devo tenere conto solo di una

Ciò che trovo difficile è pensare a tutte le possibili combinazioni di stringhe di questo tipo, non so se mi spiego… mettiamo ad esempio una stringa “210” e un numero K=7
avremmo
210210x
210x210
x210210
e per ognuna di queste x che va da 0 a 9, quindi 30 possibilità
la questione diventa enormemente più complessa se prendiamo numero più grandi, anche solo k=10 se vogliamo restare sulla stringa d’esempio

Sono ancora in alto mare, se a qualche buon samaritano nel frattempo è venuto in mente un consiglio da darmi avrà la mia gratitudine eterna :laughing:

Supponiamo di aver già calcolato quante stringhe di lunghezza 1, 2, \dots, n contengono almeno un occorrenza della stringa aliena, cosa possiamo dire riguardo le stringhe lunghe n+1 ?
Più precisamente, cosa accade quando ad una stringa lunga n (non necessariamente con un’occorrenza aliena) aggiungo un carattere all’inizio?
Tra le tante cose hai due casi di particolare interesse che ti permettono di suddividere le stringhe lunghe n+1 in due categorie.

Grazie mille per l’aiuto.
Dunque …
Poniamo per esempio la stringa aliena “210”
So che…
per n=3 “210” può occupare solo una posizione
per n=4 ne può occupare due (x210 e 210x)
per n=5 ce ne sono 3 e così via

Inoltre avere un carattere libero “x” significa che ci sono ben 10 possibilità per ognuno di questi caratteri, poiché possono variare da 0 a 9.
Quindi per n=3 c’è comunque solo 1 stringa perchè non ho caratteri liberi, per n=4 ce ne sono 20, per n=5 600…

Quindi se ad esempio una stringa lunga n aggiungo un carattere (n+1) sostanzialmente devo contare una possibile posizione in più della stringa aliena e moltiplicare per 10 per il nuovo carattere libero.

Non capisco cosa intendi quando parli di due categorie di stringhe…
Aggiungo inoltre che il mio problema si verifica proprio nel contare, poniamo in questo caso per n=6, quelle stringhe da togliere perchè considerate due volte secondo questo metodo

Il problema però è che quando inizi a crescere con n inizi ad avere più caratteri liberi rispetto alla lunghezza della stringa aliena, quindi inizi anche a contare più volte le stesse combinazioni.

Il discorso delle due categorie è questo (sempre considerando 210):

[spoiler] Tra tutte le stringhe lunghe n ci sono quelle del tipo 10x_1\dots{}x_{n-2}.
Supponiamo ora di aggiungere un carattere e ottenere la stringa y10x_1\dots{}x_{n-2} e distinguiamo due casi:

  • x_1\dots{}x_{n-2} contiene almeno un’occorrenza di 210
  • x_1\dots{}x_{n-2} non contiene occorrenze di 210

Come ci comportiamo?
[/spoiler]

Grazie mille, sono riuscito a capire il meccanismo finalmente :heart_eyes:
L’unico problema che mi resta è capire come mai uno dei testcase del subtask 15 mi dia risultato sbagliato (sono a 80 punti per ora)… immagino non ci sia un modo per sapere quali sono gli input che vengono sottoposti

1 Mi Piace