Sto cercando di risolvere paletta usando un segment tree.
Al momento faccio 22.6 su 100 (riesco a distinguere quando esiste una soluzione ma non sempre risulta corretta e nell’ultimo subtask 4 su 5 vanno in tle).
La mia idea era di dividere l’array in 2 sub-array di numeri pari e dispari (affinche’ sia risolvibile il problema, ogni elemento deve essere pari/dispari come il suo indice(0-based)).
Successivamente contare il numero di swap che bisogna fare per ordinarli.
Avevo in mente di farlo con un segment tree e quindi conto per ogni numero quanti numeri prima di lui sono piu’ grandi.
Ma non so perche’ non funziona, some help?
EDIT:
trovato l’errore ed ora mi fa 94/100 ma mi hanno detto che con segment tree non si riesce a risolvere questo problema.
Codice:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define PB push_back
typedef vector<int> vi;
const int mxN = 1500000;
int n;
vi t(mxN*4,0);
void upd( int l1, long long x, int i=1, int l2=0, int r2=n-1)
{
if(l2==r2){
t[i] = x;
return;
}
int m2 = (l2+r2)/2;
if(l1 >= l2 && l1 <= m2)
upd(l1, x, 2*i, l2, m2);
else
upd(l1, x, 2*i+1, m2+1, r2);
t[i] = t[2*i] + t[2*i+1];
}
int qry(int l1, int r1, int i=1, int l2=0, int r2=n-1){
if (l1 > r2 || r1 < l2)
return 0;
if(l1 <= l2 && r2 <= r1)
return t[i];
int m2 = (l2+r2)/2;
int q1 = qry(l1, r1, 2*i, l2, m2);
int q2 = qry(l1, r1, 2*i+1, m2+1, r2);
return q1 + q2;
}
long long paletta_sort(int N, int V[]){
long long ris=0;
vi p,d;
n=N;
for (int i = 0; i < n; ++i){
if(i%2!=V[i]%2)
return -1;
if(V[i]%2==1)
d.PB(V[i]);
else
p.PB(V[i]);
}
for(int i=0; i<d.size(); ++i){
ris += qry(d[i]+1, n-1);
upd(d[i], 1);
}
fill(t.begin(), t.end(), 0);
for(int i=0; i<p.size(); ++i){
ris += qry(p[i]+1, n-1);
upd(p[i], 1);
}
return ris;
}
C’è una struttura dati molto simile al Segment che fa tutte le operazioni che ti servono per il problema, sempre con O(logN) a query ma con un fattore costante abbastanza migliore. (Fenwick Tree).
Poi implementi il segment ricorsivamente, facendolo iterativamente credo diventi abbastanza veloce per fare 100.
sono riuscito a ridurre il problema di spazio (riducendo anche la comlessita’ del Fenwick tree) facendo si che al posto di avere i 2 array contenenti i numeri dispari e pari, ciascuno conterra’ il numero della posizione sortata (1-based) che rappresenterebbe quel numero se l’array fosse soltanto fatto di numeri pari/dispari.
Esempio:
2 3 0 5 4 1 diventa un array solo pari e uno sono dispari:
il subarray pari poi diventa:
2 0 4 -> 2 1 3
il subarray dispari poi diventa:
3 5 1 -> 2 3 1
e quindi conto quanti numeri piu grandi prima del numero che sto puntando ci sono
ma non riesco ancora a risolverlo usando un segment tree.
Puoi usare un ragionamento analogo a quello che usi con il segment tree. Quello che stai facendo al memento è una query (somma di elementi in un suffisso) ed un update (modifica di un elemento). Con il fenwick non puoi fare lo stesso identico ragionamento ma quasi, l’update puoi farlo senza problemi, mentre le query si posso fare solo su prefissi. Quindi devi, invece di effettuare una query sul suffisso, effettuarla sul prefisso e poi ottenere il valore che cercavi: diciamo che se sei in posizione i con x elementi minori di v[i] nel prefisso [0,i-1] allora ci saranno i-x elementi più grandi di v[i] nel prefisso [0,i-1].
so che pretendo troppo pero ci provo, qualcuno molto gentile potrebbe spiegare passo-passo il ragionamento dietro questo problema ? Perche ho letto che si deve usare l’albero di fenwick e ho capito come funziona ma non mi è molto chiaro come si posso poi implementare. Ho letto anche la discussione fatta in precedenza qua sopra ma non capisco il perche i pari e dispari debbano essere divisi
ciao, non è obbligatorio usare un Fenwick tree per risolvere paletta, si può benissimo usare il merge sort che trovo molto più semplice rispetto a un Fenwick tree. come puoi vedere, puoi ordinare l’array soltanto scambiando i numeri in celle alternate, quindi se osservi bene cosa succede quando scambi due celle seguendo questa regola è che se un numero si trova in una cella con indice pari, anche dopo lo swap sarà ancora in una cella con indice pari. da qui si può dedurre che il numero di scambi necessari sia la somma tra gli scambi nell’array formato da tutte le celle con indice pari e gli scambi nell’array formato da tutte le celle con indice dispari.
Ciao, nell’ordinamento a paletta i pari di un vettore devono occupare le posizioni pari e i dispari quelle dispari. In pratica ogni pari deve essere tra due numeri dispari e ogni dispari tra due pari.
Quindi, ad esempio, il vettore V{2, 1, 0} può essere ordinato con uno scambio dei 2 pari V{0, 1, 2} mentre il vettore V{2, 0, 1} NON può essere ordinato con il metodo a paletta.
Pertanto Il task si risolve dividendo il vettore tra pari e dispari e contando separatamente le inversioni dei pari e dei dispari per riportarli nel giusto ordine.
Per contare le inversioni puoi ricorrerre ad uno di questi metodi:
La divisione del vettore in un sottovettore delle poizioni pari e uno per le posizioni dispari è chiaro, ma quello che non mi è chiaro è perche per forza un numero pari deve essere in posizione pari ad esempio: V{7, 4, 2} non segue la regola da voi detta ma cmq si puo ordinare. Mi si potrebbe chiarire questo?
questo vettore non è un input valido dato che i vettori in input hanno dimensione N e in un vettore ci sono tutti i numeri da 0 a N-1. ad esempio un input valido è
5
3 0 1 4 2