# Department blackout

**URL:** <https://forum.olinfo.it/t/department-blackout/4944>\
**Category:** Aiuto\
**Created:** [27 Dicembre 2017, 5:37pm UTC](https://forum.olinfo.it/t/department-blackout/4944 "2017-12-27T17:37:12Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\
**Post date:** [27 Dicembre 2017, 5:37pm UTC](https://forum.olinfo.it/t/department-blackout/4944/1 "2017-12-27T17:37:13Z")

</div>

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](https://pastebin.com/fECrGg4s)

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [27 Dicembre 2017, 6:59pm UTC](https://forum.olinfo.it/t/department-blackout/4944/2 "2017-12-27T18:59:12Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\
**Post date:** [29 Dicembre 2017, 11:10pm UTC](https://forum.olinfo.it/t/department-blackout/4944/3 "2017-12-29T23:10:59Z")

</div>

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](https://pastebin.com/6ZL23AK6)

---

<div class="post-metadata">

**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\
**Post date:** [29 Dicembre 2017, 11:13pm UTC](https://forum.olinfo.it/t/department-blackout/4944/4 "2017-12-29T23:13:12Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [30 Dicembre 2017, 9:36am UTC](https://forum.olinfo.it/t/department-blackout/4944/5 "2017-12-30T09:36:52Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [30 Dicembre 2017, 10:36am UTC](https://forum.olinfo.it/t/department-blackout/4944/6 "2017-12-30T10:36:48Z")

</div>

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
auto it = equal_range(tests.begin(),tests.end(),answ);
cont += distance(it.first,it.second);

```

---

<div class="post-metadata">

**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\
**Post date:** [30 Dicembre 2017, 10:40am UTC](https://forum.olinfo.it/t/department-blackout/4944/7 "2017-12-30T10:40:08Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [30 Dicembre 2017, 1:55pm UTC](https://forum.olinfo.it/t/department-blackout/4944/8 "2017-12-30T13:55:57Z")

</div>

Esattamente.  
quindi:

```auto
    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);

    }

```

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [30 Dicembre 2017, 3:16pm UTC](https://forum.olinfo.it/t/department-blackout/4944/9 "2017-12-30T15:16:40Z")

</div>

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”

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [30 Dicembre 2017, 7:52pm UTC](https://forum.olinfo.it/t/department-blackout/4944/10 "2017-12-30T19:52:37Z")

</div>

Ho provato le varie soluzioni ed ottengo:

- 0.440 map \<deque,int\>;
- 0.280 multiset 
- 0.276 map \<string, int\>

---

<div class="post-metadata">

**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\
**Post date:** [31 Dicembre 2017, 11:33am UTC](https://forum.olinfo.it/t/department-blackout/4944/11 "2017-12-31T11:33:17Z")

</div>

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 ?

---

<div class="post-metadata">

**Author:** ![daveede](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/e5b9ba/32.png) [@daveede](https://forum.olinfo.it/u/daveede)\
**Post date:** [31 Dicembre 2017, 11:56am UTC](https://forum.olinfo.it/t/department-blackout/4944/12 "2017-12-31T11:56:12Z")

</div>

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 😉