TOPIC

alguma dica ??

🎈🎈 VICTOR 🎈🎈CI73A2019 asked 2 years ago

Já tentei 2 jeitos diferentes de abordar esse problema, e nunca da certo !! sempre TLE..

Um jeito de força bruta !!

E outro jeito.. é semelhante a força bruta só que em tempo de execução.. a cada valor de uma MULHER LIDO eu já percorro o vetor dos homens analisando.. mas sempre da um TLE ;/

This topic was solved and cannot recieve new replies.

  • Vitor Vilela replied 2 years ago

    Basicamente você precisa explorar as propriedades da aritmética modular...

    Se (h + m) mod K = 0, todo ((h + m) mod K) + K também será 0. Expandindo, também podemos fazer ((h mod K) + (m mod K)) mod K = 0, que é uma outra propriedade da aritmética modular...

    Usando essa propriedade, é possível encontrar uma função que já te dê todas as alturas m das mulheres que serão compatíveis com a dada altura h (ou vice-versa) e assim resolver o problema próximo de O(n lg n).

  • 🎈🎈 VICTOR 🎈🎈CI73A2019 replied 2 years ago

    kkk quanta coisa amigo... ta cheirando a TLE msm

  • NIGHTSX replied 2 years ago

    Também estou tomando TLE, minha solução: 1 - Ordenar o vetor de mulheres com o mergesort 2 - Para cada homem há uma função M(n) com n natural tal que fornece a altura de todas as mulheres compatíveis com o homem 3 - Percorrer o vetor dos homens e fazer uma busca binária no vetor das mulheres

    Acredito que essa solução seja O(N Log N) e mesmo assim continuo ganhando TLE.

  • 🎈🎈 VICTOR 🎈🎈CI73A2019 replied 2 years ago

    Vixi, eu não manjo de matemática mano !! Se conseguir me der um tema para estudar.. tipo aquele tema de exponênciação eficiente eu consegui pesquisar e aprender.. mas só falando na propriedade assim eu não conheço

  • Diego Rangel replied 2 years ago

    existe uma solucao em O(HlogM) pense: (h+m)modK = 0 ....