Ancient Text (text)

Chiarimenti
1

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!

2

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

3

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:

#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;
}
4

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).

5

Grazie mille, ci proverò!