Блог

Я пытаюсь выполнить задачу Bonetrousle HackerRank.

Проблема заключается в следующем:

Найдите B различных положительных целых чисел ниже K, чтобы их сумма была равна N, или скажите, что это невозможно.

Ограничения:

 n, k <= 10^18
b <= 10^5
  

Вы можете проверить, что решение существует, если заданное N лежит между минимальной (возьмите первые B элементов) и максимальной (возьмите последние B элементов) возможной суммой.
С этого момента я начинаю с минимальной суммы и пытаюсь довести ее до N, присваивая каждому элементу максимально возможное значение без нарушения ограничения. (без дублирования, сумма == N)

Ниже приведен код, который я написал.

 def foo1(n,k,b):
    minSum = (b*(b 1))//2
    maxSum = (b)*(k-b 1 k)//2
    #maxSum = (k*(k 1))//2 - minSum
    #print(minSum, maxSum)


    if n>=minSum and n<=maxSum:
        minArr = [i for i in range(1,b 1)]
        minArr.reverse()
        sumA = sum(minArr)

        maxA = k
        for i in range(len(minArr)):
            tmp = minArr[i]
            minArr[i] = maxA
            sumA = sumA-tmp minArr[i]

            while sumA > n:
                sumA -=1
                minArr[i] -= 1
            maxA = minArr[i]-1
            """
            while sumA 1 <= n and minArr[i] 1 <= k and minArr[i] 1 != maxA:
                #print(minArr, maxA)

                minArr[i] =1
                sumA  =1
            maxA = minArr[i]    
            if sumA == n:
                break
            """

    else:
        return [-1]
    return minArr
  

Код выдает правильные решения, однако время ожидания для ранга хакера истекает для 4 тестовых случаев. (пример n, b, k : 19999651, 20000000, 6324)
Это дает ответ в течение 3 секунд на моей машине для того же тестового примера.

Изначально я думал, что проблема была в прокомментированном коде, поскольку я пытался увеличивать каждый элемент массива 1 на 1, пока не будет достигнута сумма. Я изменил код, чтобы присвоить каждому элементу максимально возможное значение, а затем уменьшить его, если это нарушает ограничения, однако, по-видимому, это не сильно помогло.

Есть предложения по изменению кода, чтобы заставить его пройти ограничение по времени или гораздо более быстрый алгоритм?

Сначала найдите B наибольших последовательных целых чисел с суммой <= N. Проблема невозможна, если эта последовательность начинается с целого числа < 1 или заканчивается целым числом > K

Сумма B целых чисел, начинающихся с x, равна B * (2x B-1) / 2, поэтому просто решайте для x напрямую.

Очевидно, что если бы вы добавили единицу к каждому из целых чисел в последовательности, начинающейся с x, то вы получили бы следующие B последовательных целых чисел, и их сумма равна > N, так что вам не нужно увеличивать так много. Просто добавьте 1 к целым числам с наибольшей N-суммой в последовательности, чтобы сумма получилась правильной.