TOPIC

PROBLEM 2087 - URI Fórum 1.0

URI Online Judge asked 4 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Gabriel Duarte replied 4 years ago

    A ideia é essa mesmo, na verdade você não precisa nem fazer uma DFS, no momento de inserção já consegue saber se é bom ou ruim. Tome cuidado com esses tipos de casos:

    abc
    abcdef
    
    abcdef
    abc
    
    acde
    acde

    Como o Yuri disse, uma solução quadrática não era para passar, acho que deixaram com muita folga o tempo do problema. Quando escrevi a questão tinha tentado fazer com que só soluções mais elaboradas passassem, mas acho que os casos que criei estão muito fracos D:

    MOD
  • João replied 4 years ago

    Eu usei 100010x26 e passou aqui.

  • Samuel Eduardo replied 4 years ago

    Qual o limite de vértices que vocês colocaram na Trie ? Estou recebendo Runtime...

  • Samuel Silvino replied 4 years ago

    Não utilizei nenhuma estruturas de dados sofisticada como Trie. Mas acredito que deveria passar pela minha lógica. Eu adiciono strings em um vetor, ordeno eles lexicograficamente (só pode ser prefixo de outra se eles são vizinhos quando estão ordenados, certo?

    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        vector<string> palavras;
        int qtdTeste, i;
    
        while (scanf(" %d", &qtdTeste) && qtdTeste)
        {
            int conjuntoRuim = 0;
    
            while (qtdTeste--)
            {
                char temp[200];
                scanf(" %s", temp);
                palavras.push_back(temp);
            }
            sort(palavras.begin(), palavras.end());
    
            for (i=0; i<(int)palavras.size()-1; i++)
            {
                if (strncmp(palavras[i].c_str(), palavras[i+1].c_str(), palavras[i].size()) == 0)
                {
                    conjuntoRuim = 1;
                    break;
                }
            }
    
            if (conjuntoRuim)
                printf("Conjunto Ruim\n");
            else
                printf("Conunto Bom\n");
    
            palavras.clear();
        }
    }
  • Diogo Soares 👌 replied 4 years ago

    Pow podia adicionar mais casos ou diminuir o tempo. Eu tava usando essa questão pra aprender Trie com uns amigos.

    Pow, valeu os casos de teste, eu tinha cometido um erro na trie também. Fiz verificação durante a inserção mesmo e passou. Obrigadão Gabriel. ^^

    AC!
  • João replied 4 years ago

    Algoritmo quadrático passa no tempo (não deveria).

  • Diogo Soares 👌 replied 4 years ago

    Alguém tem algum caso de teste crítico neste problema? Estou tomando WA 10%.

    Eu fiz usando uma Trie. Insiro cada palavra normalmente na trie e usando uma marcação leaf pro fim de cada palavra. Depois rodo um dfs pra ver se há algum nó folha que ainda possua outras folhas (sendo, portanto um prefixo).

    Alguém tem alguma dica?

  • Unknown replied 4 years ago

    I think you should contact some experts to get help.