Qualche tempo fa ho provato a risolvere questo problema (https://cms.di.unipi.it/#/task/bufale/statement) e ho ottenuto 92/100 pt.
Essendo l’algoritmo greedy ho cercato un criterio che dunque mi permettesse di valutare le Mozzarelle in modo corretto e ho trovato che : facendo la differenza tra i voti, e ordinandoli posso capire chi dovrà valutare quella mozzarella:
Se dopo l’ordinamento la differenza tra i voti si trova nella tra 0 <=pos <N/2 allora la mozzarella sarà valutata da Paolo altrimenti da Monica.
Ho provato ad implementarlo attraverso 2 differenti algoritmi:
•Inserisco le differenze in una struct e le ordino O (NlogN)
•Inserisco le differenze in un multiset(credo rimanga O (NlogN) )
Entrambi gli algoritmi sforano come tempo e mi sono informato e ho scoperto che posso ottenere la mediana di un array in complessità O (N) quindi lineare ma non ho ancora capito in che modo.
Se non ho capito male una strategia possibile si chiama divide and conquer ma non ne sono sicuro
Qualcuno puoi spiegarmi come fare o indicarmi delle buone dispense, grazie mille!!
Esiste un algoritmo che trova la mediana di un array in O(N), il BFPRT o mediana delle mediane. La cosa bella è che è implementato nella stl, come std::nth_element (Dovrebbe usare l’introselect come algoritmo, una variazione del BFPRT)
La funzione modifica l’array in-place, un po’ come fa anche std::sort, ovvero: la esegui e lei ti modifica l’array senza restituire nulla.
L’effetto di std::nth_element però non è quello di produrre un array ordinato (altrimenti sarebbe almeno O(N \log N)) bensì una cosa un po’ più “facile da fare”: l’array modificato sarà suddiviso in due parti, la prima con tutti gli elementi minori di X, e la seconda con tutti gli elementi maggiori di X.
Quindi, se ci pensi, ci sarà esattamente un elemento sicuramente ordinato (ovvero che si trova nella stessa posizione in cui si troverebbe se l’array fosse ordinato) ed è proprio quell’elemento X. Tutti gli altri invece non ti danno garanzie, potrebbero essere messi a caso (ma sempre all’interno della loro “metà”).
In realtà il secondo parametro non è la fine (che devi indicare nel terzo parametro). Il secondo è la posizione di quell’elemento X che abbiamo citato.
Ad esempio il codice seguente:
int main() {
int v[] = {0, 10, 90, 20, 80, 30, 70, 40, 60, 50};
nth_element(&v[0], &v[5], &v[10]);
// oppure: nth_element(v, v + 5, v + 10);
}
Produce un array in cui hai la garanzia che l’elemento v[5] conterrà l’elemento che conterrebbe dopo un sort (ovvero 50). A sinistra ci saranno (disordinati) tutti i più piccoli, e a destra i più grandi.
Ma mi rimane comunque un dubbio , io ho utilizzato questa funzione Confronta per scegliere come campo della struct sul quale far lavorare la funzione nth_element, il campo voto
struct elemento
{
long long int voto;
long long int indice;
}A[MAXN];
bool confronta(elemento &a, elemento &b)
{
return a.voto>b.voto;
}
E poi l’ho passata come "parametro " alla funzione nth nth_element(A,A+n/2, A+n, confronta);
Solo che non a cosa serva il corpo della funzione , ovvero nella funzione Confronta di fatto specifico quale campo ordinare non quale usare, o faccio entrambe le cose?
Sto cercando di risolvere il problema. Ho utilizzato una map e due vector con dentro i voti dei due utenti. Purtroppo ottengo solo 45/100 e vorrei capire come fare per migliorare il mio punteggio.
Ecco il codice:
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define MAXN 10000000
using namespace std;
static int N;
static int M[MAXN], P[MAXN];
long long solve(int N, int* M, int *P){
vector <float> monica, paolo;
map <int, float> weights;
int val, val1;
long long totale = 0;
for (int j=0; j<N; j++){
monica.push_back(M[j]);
paolo.push_back(P[j]);
weights[j] = (M[j] - P[j]);
}
while (weights.size()>0){
std::map<int,float>::iterator best = std::max_element(weights.begin(),weights.end(),[] (const std::pair<int,float>& a, const std::pair<int,float>& b)->bool{ return a.second < b.second; } );
totale += monica[best->first];
weights.erase(best->first);
std::map<int,float>::iterator worst = std::min_element(weights.begin(),weights.end(),[] (const std::pair<int,float>& a, const std::pair<int,float>& b)->bool{ return a.second < b.second; } );
totale += paolo[worst->first];
weights.erase(worst->first);
}
return totale;
}
Vedendo questo thread ho provato a risolvere il problema, ma non riesco a scendere sotto 1200ms di tempo, mentre in classifica c’e’ gente con 900ms.
Uso fastio e scorro gli array esattamente 2 volte, insieme (obv li ho messi in struct per better cache).
Per il resto dovrebbero essere operazioni relativamente poco costose.
Sono weak minded io oppure sono i server che sono piu lenti ora di quando sono state submittate le soluzioni piu veloci?
Confermo la mia soluzione migliore che nel 2020 girava in un po più di 1200 ms ora gira in 1900ms.
Per curiosità come si fa ad utilizzare fastio quando c’è il grader di mezzo?
Se l’input e’ encriptato/obfuscato c’e’ poco da fare a meno che non conosci come e’ fatto, ma in questo caso l’input e’ come descritto nello statement, basta fare una classe con un istanza globale che come costruttore ha il main e fa exit(0) alla fine.
)