# Ancient Text (text)

**URL:** <https://forum.olinfo.it/t/ancient-text-text/8070>\
**Category:** Chiarimenti\
**Created:** [22 Febbraio 2023, 4:40pm UTC](https://forum.olinfo.it/t/ancient-text-text/8070 "2023-02-22T16:40:11Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![seqq](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/278dde/32.png) [@seqq](https://forum.olinfo.it/u/seqq)\
**Post date:** [22 Febbraio 2023, 4:40pm UTC](https://forum.olinfo.it/t/ancient-text-text/8070/1 "2023-02-22T16:40:11Z")

</div>

Ciao a tutti qualcuno riesce a spiegarmi come nel secondo input (abcdefh) la distanza è di 0.75? Non dovrebbe essere di 1?  
abcdefg D = 1;  
-abcdefh- (S[i])  
abcdefh D = 0;  
abcdefi D = 1;  
abcdefj D = 2,  
la somma è 4 e si divide per 5 - 1 giusto? Grazie per il futuro aiuto!

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [22 Febbraio 2023, 4:54pm UTC](https://forum.olinfo.it/t/ancient-text-text/8070/2 "2023-02-22T16:54:51Z")

</div>

Per la stringa “abcdefj” la distanza da “abcdefh” è 1.

---

<div class="post-metadata">

**Author:** ![seqq](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/278dde/32.png) [@seqq](https://forum.olinfo.it/u/seqq)\
**Post date:** [23 Febbraio 2023, 7:30pm UTC](https://forum.olinfo.it/t/ancient-text-text/8070/3 "2023-02-23T19:30:53Z")

</div>

Grazie! Beh si ho capito il mio problema, calcolavo il numero di posizioni che differiva ogni singola lettera, e comunque non riesco a prendere 100/100. Ho provato ad ottimizzare un po’ il tutto ma mi va fuori tempo.  
Questo è il codice:

```auto
#include <iostream>
#include <fstream>
using namespace std;

int N, K;
string S[1000000];
long long sum[1000000];

int dist(string a, string b){
    int length = 0;
    for(int i = 0; i < K; ++i) if(a[i] != b[i]) ++length;
    return length;
}

int main() {
    int i, j;
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    cin >> N >> K;  
    for(i = 0; i < N; ++i) cin >> S[i];
    
    float min = 1000000.f;
    int pos = 0;
    for(i = N - 1; i >= 0; --i){
        for(j = i - 1; j >= 0; --j){
            int x = dist(S[i], S[j]);
            sum[i] += x;
            sum[j] += x;
        }
        if((float)sum[i] / (N - 1) <= min){
            min = (float)sum[i] / (N - 1);
            pos = i;
        }
    }
    cout << pos;
    return 0;
}

```

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [23 Febbraio 2023, 8:15pm UTC](https://forum.olinfo.it/t/ancient-text-text/8070/4 "2023-02-23T20:15:58Z")

</div>

Ciao, intanto nota che il fattore \frac{1}{N-1} è presente in tutte le distanze medie, quindi non ti serve dividere per N - 1 (e anzi rischi di incappare in problemi di precisione con i float).  
In quanto ai TLE, la tua soluzione ha come complessità \mathcal{O}(N^2K). Per fare 100 ti serve una soluzione in \mathcal{O}(NK), in cui calcoli le distanza media di una stringa in \mathcal{O}(K).

---

<div class="post-metadata">

**Author:** ![seqq](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/278dde/32.png) [@seqq](https://forum.olinfo.it/u/seqq)\
**Post date:** [23 Febbraio 2023, 8:24pm UTC](https://forum.olinfo.it/t/ancient-text-text/8070/5 "2023-02-23T20:24:47Z")

</div>

Grazie mille, ci proverò!