0

To resolvendo um desafio aqui, que é, basicamente, ver quantos elementos de uma lista encaixam em TODOS os intervalos de uma matriz.

E minha solução foi essa:

def countSignals(frequencies, filterRanges):
    corretos = 0
    len_fR = len(filterRanges)
    for i in frequencies:
        for a in range(len_fR):
            if i in range(filterRanges[a][0], filterRanges[a][1] + 1):
                passou = True
                if passou and filterRanges[a] == filterRanges[-1]:
                    corretos+=1
            else:
                 break
    return corretos


if __name__ == '__main__':

    frequencies_count = int(input().strip())

    frequencies = []

    for _ in range(frequencies_count):
        frequencies_item = int(input().strip())
        frequencies.append(frequencies_item)

    filterRanges_rows = int(input().strip())
    filterRanges_columns = int(input().strip())

    filterRanges = []

    for _ in range(filterRanges_rows):
        filterRanges.append(list(map(int, input().rstrip().split())))

    result = countSignals(frequencies, filterRanges)

    print(result)

Como funciona a execução:

Recebo um número, que será equivalente à len(frequencies). Depois, recebo cada um dos elementos que irá compor a lista frequencies. Em seguida, recebo o valor de len(filterRanges). Depois recebo a dimensão de cada uma das listas que compõe filterRanges No final, recebo os valores de cada uma das listas.

Exemplo de input:

5 #-> len(frequencies)
20 #-> frequencies[0]
5 #-> frequencies[1]
6 #-> frequencies[2]
7 #-> frequencies[3]
12# -> frequencies[4]
3 #-> len(filterRanges), sendo que este é composto por listas
2 #-> tamanho das listas que compõe filterRanges
10 20 #-> filterRanges[0] = [10,20]
5 15 #-> filterRanges[1] = [5,15]
5 30 #-> filterRanges[2] = [5,30]

O código precisa contar quantos valores de frequencia estão no intervalo de TODAS as listas que compõe filterRanges.

Nesse caso, por exemplo, o retorno seria 1, pois apenas o numero 12 se encaixa em todos os intervalos.

Ele passou em 10 dos 15 testes, e os outros 5 deu timeout. alguém tem alguma sugestão para otimizar o código? O erro que deu foi "Terminated due to timeout", porque o codigo ficou executando por mais de 10 segundos (ele dá timeout qunado chega em 10). Como faço pra otimizar esse código?

EDIT APÓS SUGESTÕES:

def countSignals(frequencies, ranges):
    ranges = [range(i[0], i[1] + 1) for i in ranges]
    return sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)


if __name__ == '__main__':

    frequencies_count = int(input().strip())

    frequencies = []

    for _ in range(frequencies_count):
        frequencies_item = int(input().strip())
        frequencies.append(frequencies_item)

    filterRanges_rows = int(input().strip())
    filterRanges_columns = int(input().strip())

    filterRanges = []

    for _ in range(filterRanges_rows):
        filterRanges.append(list(map(int, input().rstrip().split())))

    result = countSignals(frequencies, filterRanges)

    print(result)

Passei em 12/15 testes. Preciso otimizar mais... Não consigo alterar nada definido no método main, apenas consigo alterar a função countSignals.

4
  • coloca o link para o desafio, talvez fique melhor para dar sugestões Commented 4/08/2019 às 14:39
  • hackerrank.com/tests/2h92ckdchlg Commented 4/08/2019 às 16:11
  • infelizmente pede para se cadastrar Commented 4/08/2019 às 17:18
  • eu coloquei o que ele pede. simplesmente falar quantos valores de "frequencies" se encaixam em todos os intervalos dentro de "filterRanges"... Commented 4/08/2019 às 17:26

1 Resposta 1

0

Algumas dicas:

Pelo menos na IDLE do Python, não é preciso utilizar o método strip na função input, visto que ao pressionar Enter o caractere '\n' não é levado em conta. Porém se for algo que não é exigido na competição, recomendo remover.

Ao ler os valores do filterRanges, transforme os valores em um objeto range ao invés de uma lista.

for _ in range(filterRanges_rows):
    ini, fin = (int(i) for i in input().split(' '))
    filterRanges.append(range(ini, fin+1))

A função countSignals você pode fazer em uma linha:

def countSignals(frequencies, ranges):
    return sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)

Por partes:

f in r
# verifica se f está em r

f in r for r in ranges
# retorna um iterável de booleanos onde cada elemento
# indica se f está em r para cada r na lista ranges

all(f in r for r in ranges)
# verifica se todos os elementos desse
# iterável são verdadeiros (True), ou seja,
# se a frequência f está em todos os
# intervalos da lista ranges

1 if all(f in r for r in ranges) else 0
# retorna 1 se todos os elementos do iterável
# são verdadeiros, senão retorna 0

1 if all(f in r for r in ranges) else 0 for f in frequencies
# repete essa operação para todas as frequencias

sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)
# soma todos os elementos que possuem 1
# ou seja, a quantidade de frequencias que
# estão em todos os intervalos da lista ranges

Veja se essas dicas melhoram o tempo de execução do seu código.

EDIT: Haha, desculpa, não sabia que a parte do main era pré-definido pela plataforma. Você pode ir modificando alguns fatores da função countSignals e vendo o resultado:

Tente utilizar expressões geradoras ao invés de compreensão de listas quando são criados os objetos range na primeira linha da função, onde

ranges = [range(r[0], r[1] + 1) for r in ranges]

se torna

ranges = (range(r[0], r[1] + 1) for r in ranges)

Tente substituir o uso dos objetos range por comparações dos elementos na própria lista ranges, onde

ranges = [range(r[0], r[1] + 1) for r in ranges]
return sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)

se torna

return sum(1 if all(f >= r[0] and f <= r[1] for r in ranges) else 0 for f in frequencies)

Você pode também remover o uso do else 0 visto que ele não interfere na função sum.

return sum(1 for f in frequencies if all(f >= r[0] and f <= r[1] for r in ranges))
3
  • 1
    Tem um problema só kkkk. A parte de baixo (depois do main) é tudo pré-definido pela plataforma. O que eu fiz, para seguir as suas sugestões, é criar uma nova lista e num for loop atribuir os valores da lista de antes, mas como range. Vou adicionar esse código abaixo, como um edit para você me ajudar... PS: a performance do código melhorou bastante e passei por 12/15. Agora faltam 3, se puder me ajudar Commented 4/08/2019 às 14:30
  • 1
    Adicionei o código na pergunta, se puder me dar uma ajudada <3 kkkk Commented 4/08/2019 às 14:33
  • Editei minha resposta, vê se ajuda em alguma coisa kkk
    – enzo
    Commented 5/08/2019 às 16:11

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .