Неправильно ли этот тестовый пример с вызовом колидности (Zin c 2018)? - PullRequest
Новая
       122

Неправильно ли этот тестовый пример с вызовом колидности (Zin c 2018)?

0 голосов
/ 01 августа 2020

Я случайно выбрал этот вызов ...

Вопрос и отчет можно найти здесь: https://app.codility.com/demo/results/training3NRM6P-HSG/

Для тестового примера N = 100,000, all performances are different., он говорит: got 166661666700000 expected 665533373

Для N = 100,000 все разные характеристики не должны быть: C(100000, 3) = int(len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2), как рассчитывается 665533373?

Вставьте мое решение сюда для удобства чтения: 

def solution(A):
    # write your code in Python 3.6
    if not A or len(A) < 3:
        return 0
        
    if len(set(A)) == len(A):
        return int(len(A) * (len(A) - 1) * (len(A) - 2) / 3 / 2)
        
    check = {}
    def bt(path, nxt):
        if len(path) == 3:
            t = tuple(path)
            if t not in check:
                check[t] = None
            return
        
        if len(path) > 3:
            return
        
        for i in range(nxt, len(A)):
            if i > nxt and A[i] == A[i-1]:
                continue
            path.append(A[i])
            bt(path, i + 1)
            path.pop()
            
    bt([], 0)
    
    return len(check)

1 Ответ

1 голос
/ 01 августа 2020

Посмотри внимательнее на вопрос! В нем четко сказано, что «поскольку ответ может быть очень большим, предоставьте его по модулю 10 ^ 9 + 7 (1 000 000 007)».

Ваш ответ, 166661666700000 % (10^9 + 7) = 665533373, который является ожидаемым результатом.

Итак, все, что вам нужно сделать теоретически, это отредактировать последнюю строку вашего кода следующим образом: 

return len(check) % (10**9 + 7)
...