A quanto pare io ed i Fenwick Tree non andiamo molto d’accordo.
Sto avendo problemi anche con il Fenwick2. Come faccio a gestire due valori consecutivi uguali? Non ho idee…
Cosa fa il tuo algoritmo?
Ordino il vettore e cerco delle corrispondenze tra valori successivi, formando un ulteriore array che contiene il numero di volte in cui un determinato valore compare nel primo vettore. Ovviamente la dimensione di questo vettore è minore rispetto a quella del primo ed i valori rappresentati da ogni posizione del vettore rappresentano valori diversi.
Dopo di che calcolo il numero di sottostringhe presenti fino alla posizione i (1 <= i <= cont, dove cont è il numero di valori diversi presenti), moltiplicandolo per il numero di volte in cui compare il valore in posizione i.
Sono consapevole del fatto che non è la via giusta, perciò sto cercando di farmi venire in mente un altro modo per gestire più valori uguali.
Ma non usi nessun fenwick?
Sì scusa mi ero dimenticato di dirlo, uso un fenwick per la somma di tutti i valori di S, dove S[i] è il numero di sottostringhe che terminano per vet[i]
Ora ho cambiato algoritmo (credo che sostanzialmente sia corretto), ma ancora non funziona.
Uso un array S dove S[i] è il numero di sottosequenze terminanti con vet[i].
Per quest’array vale che S[i] = 1+sum(i-1) (dove sum(i-1) è la somma di tutti gli elementi S[j] con 0 < j < i) se vet[i]!=vet[i-1] (con vet ordinato), mentre vale S[i]=S[i-1] se vet[i]==vet[i-1].
Tutti questi valori “alimentano” il fenwick ed il risultato finale sarà la somma di tutti gli elementi di S (calcolata grazie al fenwick).
Ora quest’algoritmo mi sembra corretto, però totalizzo solo 10/100.
EDIT:
Possibile che sbaglio qualcosa nel codice?
#include <fstream>
#include <algorithm>
#define MAXN 100010
using namespace std;int N;
int vet[MAXN], S[MAXN], fenwick[MAXN];void update(int p, int val){
for(;p<=N; p+=p&-p) fenwick[p]+=val;
}int query(int p){
int r=0;
for(; p; p-=p&-p) r+=fenwick[p];
return r;
}int main(){
ifstream in(“input.txt”);
in >> N;
for(int i=1; i<=N; i++)
in >> vet[i];
in.close();sort(vet+1, vet+N+1); update(1, 1); S[1]=1; for(int i=2; i<=N; i++){ if(vet[i].second > vet[i-1].second) if(vet[i].first!=vet[i-1].first) S[i] = query(i-1)+1; else S[i] = S[i-1]; else S[i] = 1; update(i, S[i]); } ofstream out("output.txt"); out << query(N) << "\n"; out.close(); return 0;}
Uhm… ma per questo input scrivi correttamente zero?
3
3 2 1
No, restituisce 7. Immagino che non avevo capito cosa deve fare il programma…
EDIT:
Scusa ma non dovrebbe restituire 3? Cioè le Increasing Subsequences dovrebbero essere {3}, {2}, {1}.
EDIT2:
Ho nuovamente cambiato algoritmo, dato che ho realizzato che non dovevo ordinare il vettore. Le modifiche che ho fatto sono poche. Il vettore “vet” ora è un vettore di pair<int,int> dove first rappresenta il valore, mentre second la posizione nella quale si trova al momento dell’acquisizione. Dopo di che ordino il vettore in ordine crescente per l’elemento first, oppure per l’elemento second in caso di parità.
Poi controllo che in due elementi consecutivi del nuovo vettore ordinato, l’elemento second del secondo sia maggiore del primo (vet[i].second>vet[i-1].second). Se è così faccio la stessa operazione di prima, altrimenti pongo S[i] = 1.
Questo è il codice:
#include <fstream>
#include <algorithm>
#define MAXN 100010
using namespace std;typedef pair<int,int> T;
int N;
int S[MAXN], fenwick[MAXN];
T vet[MAXN];void update(int p, int val){
for(; p<=N; p+=(p&-p)) fenwick[p]+=val;
}int query(int p){
int r=0;
for(; p; p-=(p&-p)) r+=fenwick[p];
return r;
}bool cmp(T el1, T el2){
if(el1.first==el2.first) return el1.second<el2.second; return el1.first<el2.first; }int main(){
ifstream in(“input.txt”);
in >> N;
for(int i=1; i<=N; i++){
in >> vet[i].first;
vet[i].second = i;
}
in.close();sort(vet+1, vet+N+1, cmp); S[1]=1;<p> update(1, 1);</p> for(int i=2; i<=N; i++){ if(vet[i].second > vet[i-1].second) if(vet[i].first!=vet[i-1].first){ S[i] = query(i-1)+1; update(i, S[i]); }else{ S[i] = S[i-1]; update(i, S[i]); } else{ S[i] = 1; update(i, 1); } } ofstream out("output.txt"); out << query(N) << "\n"; out.close(); return 0;}
Mi dà ancora 10/100
Hai ragione, volevo dire 3.Scusa ma non dovrebbe restituire 3? Cioè le Increasing Subsequences dovrebbero essere {3}, {2}, {1}.Lawliet
Comunque, un'osservazione: il risultato può essere molto grande (per $n$ elementi distinti ordinati è $2^n-1$).
Vero, ci avevo pensato (infatti non sarebbe altro che l'insieme delle parti meno l'insieme vuoto) ma poi non ho più corretto.Comunque, un'osservazione: il risultato può essere molto grande (per n elementi distinti ordinati è 2n-1).
wil93
Ora ho corretto e sta valutando. Ci sta mettendo parecchio oggi a valutare le sottoposizioni...
Questo non dovrebbe essere un problema, dato che il risultato deve essere modulo 1000000007...Hai ragione, volevo dire 3.Scusa ma non dovrebbe restituire 3? Cioè le Increasing Subsequences dovrebbero essere {3}, {2}, {1}.Lawliet
Comunque, un'osservazione: il risultato può essere molto grande (per n elementi distinti ordinati è 2n-1).wil93
Infatti ancora non funziona. Non che mi aspettassi di avere un 100/100, però nemmeno un miglioramento. Mark, posso sapere se l'algoritmo che hai usato è perlomeno simile al mio?Questo non dovrebbe essere un problema, dato che il risultato deve essere modulo 1000000007...Comunque, un'osservazione: il risultato può essere molto grande (per n elementi distinti ordinati è 2n-1).
wil93
mark03
È simile, cambia leggermente la funzione cmp che mi permette di evitare tutti i controlli che tu fai dopo…
Comunque credo che il tuo errore sia dove dici che se vett[i].second<vett[i-1].second allora S[i]=1… Non è detto che non ci sia nessuno numero più piccolo con posizione minore… Quindi S[i] potrebbe anche essere maggiore di 1…
Per la terza volta ho cambiato algoritmo e finalmente ho il mio 100/100.
Innanzitutto ho “compresso” il mio array così come facevo all’inizio, usando un indice fittizio che non incrementa in caso di valori consecutivi uguali. Dopo di che era sufficiente applicare la formula S[i] = sum(i-1)+1, dove i è appunto l’indice fittizio. Non era difficile, però mi ero “impantanato”, soprattutto all’inizio fraintendendo l’obiettivo del problema.
Grazie a tutti!