Aiuto con Papà?

Aiuto
1

Salve, stavo cercando di risolvere il problema papa, ma la mia soluzione funziona solo nel testcase di esempio, mentre negli altri o produce output non corretto o l’esecuzione supera il tempo limite.
La mia idea era quella di confrontare ogni sottostringa di DNA con le altre, calcolarne la stringa “genitore” se esiste e sostituirla alle due confrontate nel vettore. Dopodiché nel vettore dovrebbero rimanere solo sequenze di DNA che non possono essere unite le une alle altre, quindi quelle che cerca la traccia.
Qualcuno potrebbe aiutarmi?

    #include <iostream>
    #include <unordered_map>
    #include <vector>
    using namespace std;

    struct Sottostringa {
        unordered_map <int, char> str;
        int inizio;
        int fine;
    };

    Sottostringa unisci(Sottostringa ss1, Sottostringa ss2)
    {
        Sottostringa unione;
        unione.inizio = min(ss1.inizio, ss2.inizio);
        unione.fine = max(ss1.fine, ss2.fine);

        if(ss1.inizio > ss2.fine || ss2.inizio > ss1.fine)
            return unione;

        for(int i=unione.inizio; i<=unione.fine; i++) {
            char c1, c2;
            c1 = (ss1.str.find(i) != ss1.str.end()) ? ss1.str[i] : '?';
            c2 = (ss2.str.find(i) != ss2.str.end()) ? ss2.str[i] : '?';

            if(c1 != c2 && c1 != '?' && c2 != '?') {
                unione.str.clear();
                return unione;
            } else {
                unione.str[i] = (c1 != '?') ? c1 : c2;
            }
        }

        return unione;
    }

    int main()
    {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);

        int N, t, i, j;
        cin >> N;

        int M[N];
        for(t=0; t<N; t++) {
            cin >> M[t];
        }

        for(t=0; t<N; t++) {
            vector <Sottostringa> ss(M[t]);

            for(i=0; i<M[t]; i++) {
                Sottostringa s;
                cin >> s.inizio >> s.fine;
                for(j=0; j<s.fine; j++) {
                    cin >> s.str[s.inizio+j];
                }
                s.fine += s.inizio - 1;
                ss.at(i) = s;
            }

            for(int i=0; i<ss.size()-1; i++) {
                for(int j=i+1; j<ss.size(); j++) {
                    Sottostringa unione = unisci(ss.at(i), ss.at(j));

                    if(!unione.str.empty()) {
                        ss.erase(ss.begin()+max(i, j));
                        ss.erase(ss.begin()+min(i, j));
                        ss.insert(ss.begin()+i, unione);
                    }
                }
            }

            if(ss.size() >= 3) cout << "1" << endl;
            else cout << "0" << endl;
        }

        return 0;
    }
2

Ecco un caso in cui il tuo algoritmo non funziona:

1
4
1 2 A?
1 2 ?G
1 2 G?
1 2 AA

La risposta sarebbe 0 ma il tuo programma stampa 1.
Questo perché combinando le prime due stringhe “perdi” il punto interrogativo, che ti sarebbe servito per inserire l’ultima stringa.
Credo invece che i lunghi tempi di esecuzione siano dovuti al fatto che ti trovi a confrontare stringhe di lunghezze che arrivano fino a 2 * 10^9.

1 Mi Piace