Department blackout

Aiuto
1

Salve, il mio codice per il problema blackout, dà 40 su 100, e non capisco come ottimizzarlo, in pratica “conto” il numero di risposte per valore(simil - counting sort), e confronto gli array ottenuti(quello delle risposte dello studente e quello dei test)
https://pastebin.com/fECrGg4s

2

Potresti cercare di abbassare la complessità “ordinando” le varie sequenze e rendere più veloce il confronto .

1 Mi Piace
3

ok, quindi devo fare un ordinamento lessicografico degli array delle quantità, (sulla falsariga del problema caesar cypher), e dopo? come faccio a capire in quale posizione è il primo array uguale alla query e in quale l’ ultimo?, io ho provato così:
https://pastebin.com/6ZL23AK6

4

Scusa la sintassi con commenti e indentazione fatta male ma è mezzanotte XD

5

Una volta ordinata ogni sequenza diventa utile ordinare tutte le sequenze in modo che per cercarne una puoi usate la ricerca dicotomica.

Per farlo in un modo meno elegante ma efficace puoi ordinare ogni sequenza , trasformarla in una stringa, ed inserirla in un multiset.
Poi ti basterà utilizzare la .count () del multiset per capire se la stringa è presente

1 Mi Piace
6

Non serve trasformare un vector in una stringa, si può usare direttamente come key.
Comunque un modo più elegante è usare la funzione equal_range che ritorna il range dell’elemento uguale alla chiave. Si può fare quindi una cosa del tipo:

auto it = equal_range(tests.begin(),tests.end(),answ);
cont += distance(it.first,it.second);
1 Mi Piace
7

In multiset da quanto ho capito sarebbe un set che ammette ripetizioni giusto?

8

Esattamente.
quindi:

    for(int j=0;j<a;j++)
    {
        string s="";
        for(int i=0;i<c;i++)
            A[i]=readInt();
        sort(A, A+c);
        for(int i=0;i<c;i++)
            s+=A[i];
        M.insert(s);
    }
    int sol=0;
    for(int j=0;j<b;j++)
    {
        string s="";
        for(int i=0;i<c;i++)
            A[i]=readInt();
        for(int i=0;i<c;i++)
            s+=A[i];
        if(M.count(s)>0) sol+=M.count(s);

    }
1 Mi Piace
9

In un multiset, la funzione count ha una complessità di O(logN + K) dove K sono le occorrenze del termine che cerchiamo - in alcuni casi potrebbe essere meglio utilizzare una map in cui memorizzare il numero di occorrenze per ciascuna “chiave”

10

Ho provato le varie soluzioni ed ottengo:

  • 0.440 map <deque,int>;
  • 0.280 multiset
  • 0.276 map <string, int>
1 Mi Piace
11

Domanda a scopo puramente informativo, andrebbe bene anche una ricerca sequenziale, per il conteggio delle sequenze uguali(che si interrompe appena ne trova una diversa), oppure solo la dicotomica rimane entro i limiti ?

12

Ad ogni modo ho risolto il problema con il multiset e la funzione count, (adesso ho nel mio arsenale una bella arma) grazie mille dell’ aiuto :wink: