TOPIC

PROBLEM 2087 - URI Fórum 1.0

beecrowd asked 7 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • gduarte replied 7 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

  • Joao40 replied 7 years ago

    Eu usei 100010x26 e passou aqui.

  • SamuelEduardo replied 7 years ago

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

  • ssilvino replied 7 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();
    }
}

  • dsoares replied 7 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!

  • Joao40 replied 7 years ago

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

  • dsoares replied 7 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?