Suggerimenti per yutaka

Salve a tutti, sto provando a risolvere il problema yutaka e sto avendo delle difficoltà ad ideare la soluzione con programmazione dinamica (sono alle prime armi). Praticamente quello che ho fatto è stato prima risolvere il problema in maniera brute force (ricorsiva), poi ho osservato l’albero delle chiamate e ho pensato a come si potesse ottimizzare. Alla fine sono arrivato a questo algoritmo solo che non riesco a capire come migliorarlo ulteriormente (se si può fare): (ottengo 49/100)

#include<bits/stdc++.h>
using namespace std;
vector<int> solution(1000001, -1);
int recursive(int pezzi[], vector<int> &posPezzi, int n, int i=1, int spez=-1)
{
	if(i==n)
		return 1;
	if(solution[spez+1]!=-1)
		return solution[spez+1];
	if(posPezzi[i]>spez)
		return solution[spez+1]=recursive(pezzi, posPezzi, n, i+1, i-1)%1000000007;
	return solution[spez+1]=(recursive(pezzi, posPezzi, n, i+1, spez)%1000000007+recursive(pezzi, posPezzi, n, i+1, i-1)%1000000007)%1000000007;
}
int taglia(int N, int V[])
{
    vector<int> posPezzi(N);
	vector<int> temp(1000007, -1);
	for(int i=0;i<N;++i){ //con questo ciclo memorizzo dentro posPezzi per ogni pezzo la posizione del precedente 
		posPezzi[i]=temp[V[i]];
		temp[V[i]]=i;
	}
    return recursive(V, posPezzi, N);
}

Praticamente mi salvo in un vettore il numero di soluzioni per ogni ultimo taglio. In questo modo se successivamente dovrò fare lo stesso taglio mi basta restituire il risultato memorizzato. Per esempio se ho l’input:

5
3 1 3 1

Con l’algoritmo brute force l’albero delle chiamate è questo:

Qui per esempio mi genero tutto l’albero di sinistra di recursive(1, -1), memorizzandomi il risultato di recursive(3, 1) (asterisco 1) e non solo. Quando poi mi trovo in recursive(2, 0) (asterisco 2) e da qui invoco recursive(3, 1) visto che effettuo un taglio dove lo avevo gia fatto sono in grado di restituire immediatamente il risultato in quanto gia calcolato precedentemente.

Ti consiglierei di salvarti come variabili globali N, V[] e gli altri vettori in modo da alleggerire la funzione ricorsiva. Infatti il passaggio di un intero oggetto vettore come parametro di una funzione può essere molto pesante e rallentare io tuo programma (considera che il vettore nel caso peggiore occupa ≈4mb di RAM).
Un’alternativa è passare il puntatore ma secondo me se le metti globali viene più facile da scrivere e da vedere

infatti è presente ‘&’.

Scusa è vero non ho guardato bene il codice :sweat_smile:
Ma che tipo di errore ti dà? Timeout oppure output non corretto?

Non riesco a stare dentro i tempi (time out).

Prova ad approciare il problema in modo diverso, per cercare di utilizzare un solo parametro variabiile( ora usi sia i che spez) .
HInt 1 ( 64/100): conta il numero di gruppi validi fino ad un certo indice( anziche’ pensare a cosa succederebbe se si tagliasse in quell’indice). Cosa devi conoscere per farlo?
HInt2 (100/100): Esistono modi piu’ efficienti per farlo? Cosa devi escludere dal conteggio?

Sono riuscito a fare 64/100. Il codice è questo:

    #include<bits/stdc++.h>
    using namespace std;
    vector<int> solution(1000001, -1);
    int recursive(int pezzi[], vector<int> &posPezzi, int n, int i=0)
    {
    	if(i+1>=n)
    		return 1;
    	if(solution[i]!=-1)
    	    return solution[i];
    	int cont=0;
    	for(int j=i+1;j<=posPezzi[i];++j)
            cont=(cont%1000000007)+(recursive(pezzi, posPezzi, n, j)%1000000007)%1000000007;
    	return solution[i]=cont%1000000007;
    }
    int taglia(int N, int V[])
    {
        vector<int> posPezzi(N);
    	vector<int> posTagliMax(N);
    	vector<int> temp(1000007, N);
    	for(int i=N-1;i>=0;--i){
    		posPezzi[i]=temp[V[i]];
    		temp[V[i]]=i;
    	}
    	posTagliMax=posPezzi;
    	for(int i=N-2;i>=0;--i)
    		if(posTagliMax[i]>posTagliMax[i+1])
    			posTagliMax[i]=posTagliMax[i+1];
    	return recursive(V, posTagliMax, N);
    }

Una miglioria che potrebbe aiutarmi ad arrivare a fare 100/100 potrebbe essere penso utilizzare la binary exp. In questo modo se ho l’input:

12
5 3 1 1 3 1 3 1 1 2 3 4

Posso creare 3 insieme:

  1. 5 3 1 (computo il risultato con binary exp) -> 4
  2. 1 3 1 3 1 (computo il risultato con la funzione ricorsiva) -> 8
  3. 1 2 3 4 (computo il risultato con binary exp) -> 8

Alla fine il risultato sarà dato dal prodotto di questi 3 risultati quindi 4x8x8 = 256. Non so però tutta sta roba quanto potrebbe essere utile :confused:

Il for dentro la funzione recursive allunga i tempi.
In che modo puoi ottenere la somma degli elementi di un vettore statico (in questo caso solutions) da un indice i a un indice j in tempo costante?
Hint: prefix sums

So come funziona prefix sum, solo che non capisco come faccio a sfruttarla se l’array solution non è ancora riempito in quel intervallo

Infatti per usare le somme prefisse il vettore deve essere riempito fino all’indice su cui stai lavorando.
A tale scopo ti consiglio di fare una dp bottom up: cominci definendo sol[0], poi passo per passo arrivi a definire sol[N-1]. In questo caso farlo iterativamente viene più comodo che con una funzione ricorsiva.

Non ho proprio idea di come come convertirlo in un bottom up o di scrivere una soluzione bottom up per questo problema :pensive: .

Come nel testo del problema definiamo \text{V} il vettore con i numeri.
Definiamo \text{sol[i]} con 0 \le \text{i} \le N-1 la soluzione migliore per i primi \text{i+1} elementi.
Puoi cominciare definendo \text{sol[0] = 1}, infatti con un solo elemento c’è una sola possibilità.

Durante il procedimento dovrai pure tenere due vettori utili: il vettore delle prefix sums (che chiameremo \text{ps}, dopo spiego a cosa serve), andrà aggiornato ogni volta che trovi un nuovo \text{sol[i]} in questo modo: \text{ps[i+1] = ps[i]+sol[i]}. Durante queste addizioni bisogna sempre stare attenti al modulo.
Poi il vettore che tiene traccia delle ripetizioni di ogni elemento: ci serve perché in ogni gruppo di numeri consecutivi non devono esserci duplicati. Lo chiameremo \text{lastoc}, che sta per “last occurrence” (i nomi che do ai vettori non sono sempre bellissimi :smile:). Per fare un esempio \text{lastoc[n]} è l’ultima posizione in cui l’elemento con valore \text{n} è comparso (se non sbaglio tu l’hai chiamato posPezzi). Anche questo andrà aggiornato passo per passo, ma va inizializzato a -1 perché nessun elemento è ancora comparso all’inizio.

Iniziamo iterando con una variabile \text{i}, che rappresenta l’indice su cui stiamo lavorando, e la facciamo andare da 1 a N-1 (perché \text{sol[0]} è già definito)
A questo punto dobbiamo calcolare \text{sol[i]}, ma per farlo dobbiamo considerare tutti i possibili tagli che partono da \text{i} e vanno all’indietro. Ma c’è un limite oltre il quale non possiamo indietreggiare, dobbiamo infatti assicurarci che non ci siano ripetizioni in uno stesso taglio.
Ci teniamo pure una variabile che chiamo \text{pos}, che indica fino a che punto si può estendere un eventuale taglio che parte da \text{i} e va all’indietro. Inizialmente pos=0, il taglio si può estendere fino all’inizio. Ogni volta che incontri un nuovo elemento devi vedere se è già comparso e dove, lo puoi fare grazie all’array \text{lastoc} che poi aggiornerai con l’elemento corrente. A tal punto se è già comparso alla posizione \text{j=lastoc[ V[i] ]} deduci che un ipotetico taglio che parte da \text{i} non si potrà estendere più indietro di \text{j}, e non potrà neanche comprendere la posizione \text{j} (altrimenti in uno stesso taglio ci sarebbe un duplicato). Quindi la variabile pos, definita a tale scopo, andrà aggiornata così ogni volta: \text{pos = max(pos, j+1)}.
Ora occorre fare un’osservazione grazie alla quale possiamo utilizzare la programmazione dinamica per risolvere questo problema: nel momento in cui in taglio che inizia in \text{i} e va indietro fino a k (con pos \le k \le \text{i}) non c’è bisogno di calcolare il numero di possibili tagli da k-1 a 0, perché questo risultato è già presente in \text{sol[k-1]}. Quindi basta sommare a \text{sol[i]} tutti i \text{sol[k-1]} per ogni k tale che pos \le k \le \text{i}.
Attenzione: se \text{pos=0}, dobbiamo stare attenti perché \text{sol[-1]} non esiste. Infatti se \text{pos=0} significa che possiamo estendere il taglio fino all’inizio e per questo aumentare di 1 \text{sol[i]} perché un nuovo intervallo indipendente dai precedenti può essere creato.
Da ultimo useremo il vettore delle prefix sums per sommare a \text{sol[i]} tutte le \text{sol[k-1]} valide in tempo costante (ricordo che pos \le k \le \text{i}) ed evitare il timeout.

1 Mi Piace

Ho provato ad implementarlo solo che penso mi stia perdendo qualcosa di banale ho problemi in subtask 3, 4, 5.

#include<bits/stdc++.h>
using namespace std;
int taglia(int N, int V[])
{
	vector<int> posTagliMax(N); //contiene fino a dove al massimo posso tagliare a partire da ogni elemento
	vector<int> temp(1000007, -1); //vettore di supporto per calcolare posTagliMax
	vector<int> solution(1000001, 0);
	vector<int> prefixSum(N, 0);
	for(int i=0;i<N;++i){
		posTagliMax[i]=temp[V[i]];
		temp[V[i]]=i;
	}
	for(int i=1;i<N;++i)
		if(posTagliMax[i]<posTagliMax[i-1])
			posTagliMax[i]=posTagliMax[i-1];
	solution[0]=1;
	prefixSum[0]=1;
	for(int i=1;i<N;++i){
		if(posTagliMax[i]==-1)
			solution[i]=((prefixSum[i-1]%1000000007)+(1%1000000007))%1000000007;
		else if(posTagliMax[i]==0)
			solution[i]=prefixSum[i-1]%1000000007;
		else
			solution[i]=((prefixSum[i-1]%1000000007)-(prefixSum[posTagliMax[i]-1]%1000000007))%1000000007;
		prefixSum[i]=(solution[i]%1000000007+prefixSum[i-1]%1000000007)%1000000007;	
	}
	return solution[N-1]%1000000007;
}

Il modulo in c++ non funziona con i numeri negativi, quindi per le sottrazioni viene sfruttata un altra proprietà :

(A-B+mod)%mod

ecco il codice con quella piccola modifica

#include<bits/stdc++.h>
using namespace std;
int taglia(int N, int V[])
{
	vector<int> posTagliMax(N); //contiene fino a dove al massimo posso tagliare a partire da ogni elemento
	vector<int> temp(1000007, -1); //vettore di supporto per calcolare posTagliMax
	vector<int> solution(1000001, 0);
	vector<int> prefixSum(N, 0);
	for(int i=0;i<N;++i){
		posTagliMax[i]=temp[V[i]];
		temp[V[i]]=i;
	}
	for(int i=1;i<N;++i)
		if(posTagliMax[i]<posTagliMax[i-1])
			posTagliMax[i]=posTagliMax[i-1];
	solution[0]=1;
	prefixSum[0]=1;
	for(int i=1;i<N;++i){
		if(posTagliMax[i]==-1)
			solution[i]=((prefixSum[i-1]%1000000007)+(1%1000000007))%1000000007;
		else if(posTagliMax[i]==0)
			solution[i]=prefixSum[i-1]%1000000007;
		else
			solution[i]=((prefixSum[i-1]%1000000007)-(prefixSum[posTagliMax[i]-1]%1000000007)+1000000007)%1000000007;
		prefixSum[i]=(solution[i]%1000000007+prefixSum[i-1]%1000000007)%1000000007;	
	}
	return solution[N-1]%1000000007;
} ```
1 Mi Piace