Problema Caesar Cypher

Aiuto
1

Stavo provando a risolvere il problema Caesar Cypher e ho preso soltanto 40/100, non riesco a capire quale possa essere il problema… questo è il codice

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N, D, risF=1;
    cin >> N >> D;
    vector<string> word(N+2);
    vector<int> R(N+2, 0);
    for(int i=0; i<N; i++){
        cin >> word[i];
    }
    for(int i=0;i<N && R[i]==0;i++){
        int ris=1;
        for(int j=i+1;j<N && R[j]==0; j++){
            char cost;
            if(word[j][0]-word[i][0]<0)
                cost=word[j][0]-word[i][0]+26;
            else
                cost=word[j][0]-word[i][0];
            int t=0;
            for(int z=1;z<D && t==0;z++){
                char cost2;
                if(word[j][z]-word[i][z]<0)
                    cost2=word[j][z]-word[i][z]+26;
                else
                    cost2=word[j][z]-word[i][z];
                if(cost!=cost2){
                    t=1;
                }
            }
            if(t==0){
                ris++;
                R[j]=1;
            }
        }
        if(risF<ris)
            risF=ris;
    }
    cout << risF << endl;
}
2

Nei testcase irrisolti il problema è l’output sbagliato o il limite di tempo?

2 Mi Piace
3

Nei testcase irrisolti mi dà output non corretto

4

Non è detto che se R[i]!=0 o R[j]!=0 i cicli vadano interrotti.

5

Io credo vadano interrotti perchè è una pila già calcolata… potresti farmi un esempio pratico?

6

Prova con questo input
N = 5
D = 2
ab
ef
xx
yy
zz
Il tuo programma restituisce 2, la risposta corretta è 3.

1 Mi Piace
7

Ora ho capito avevi ragione… ho corretto il codice ora prendo 65/100 e i casi rimanenti vanno fuori tempo massimo

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N, D, risF=1;
    cin >> N >> D;
    vector<string> word(N);
    vector<int> R(N, 0);
    for(int i=0; i<N; i++){
        cin >> word[i];
    }
    for(int i=0;i<N;i++){
        if(R[i]==0){
            int ris=1;
            for(int j=i+1;j<N; j++){
                if(R[j]==0){
                    char cost;
                    if(word[i][0]-word[j][0]<0)
                        cost=word[i][0]-word[j][0]+26;
                    else
                        cost=word[i][0]-word[j][0];
                    int t=0;
                    for(int z=1;z<D && t==0;z++){
                        char cost2;
                        if(word[i][z]-word[j][z]<0)
                            cost2=word[i][z]-word[j][z]+26;
                        else
                            cost2=word[i][z]-word[j][z];
                        if(cost!=cost2){
                            t=1;
                        }
                    }
                    if(t==0){
                        ris++;
                        R[j]=1;
                    }
                }
            }
            if(risF<ris)
                risF=ris;
        }
    }
    cout << risF << endl;
}
8

Questo a causa della complessità del tuo codice che dovrebbe essere O(D * N^2). Con pochi accorgimenti e la giusta struttura dati della STL puoi abbassare la complessità a O(D * NlogN) e prendere 100 punti.