LINUX.ORG.RU

Произведение двух чисел равное сумме последовательности чисел

 ,


2

1

В общем задачка известная, но есть проблема — на сайте с заданиями не могу пройти тест по времени — слишком долго выполняется. Дело в том, что делаю простым перебором всех возможных комбинаций (грубо говоря брут-форс), а нужно как-то сузить рамки поиска.

Задание:

нужно найти в числа в последовательности, произведение которых равно сумме всех элементов последовательности без этих двух чисел. Пример:

26 → нужные числа 15 и 21
sum([x for x in range(27) if x not in [15, 21]]) == 351
15 * 21 = 351
На данный момент код такой:
def func(n):
    lst = []
    rsum = (n * (n + 1)) / 2
    for i in range(n + 1):
        for j in range(n + 1, 0, -1):
            if i * j == rsum - i - j:
                lst.append((i, j))
    return lst
Работает медленно, как сузить поиск?

P.S. Это не лабораторная в школе, задание из одного онлайн задачника.

А ограничения какие ?

Можно попробовать делать усечение перебора, или искать какой-то алгоритм с меньшей сложностью. Без ограничений не поймешь, можно ли пропихнуть перебор просто оптимизировав его.

Balantay
()

Можно попробовать отсортировать массив /O(n * logn)/, потом перебирать первое число, а второе искать бинпоиском по оставшейся справа от первого части массива.

Balantay
()

если я правильно побмню питон, то range(n) аллоцирует массив, и это писец, т.к. у тебя в пустую аллоцируется туева хуча этих массивов, когда достаточно одного (а на деле и один не нужен)

Deleted
()
Ответ на: комментарий от Balantay

Ограничения на выполнение? 8 секунд на последовательность в ~1000000. Т.е. задание более математическое, нужно понять примерное расположение первого множителя и предположить, где будет второй. Таким образом сильно уменьшим количество пар для перебора. Проверял в цикле на до 1000 — вариант всегда один, если он есть.

conformist ★★★
() автор топика

Сообщение прочел по диагонали. Можно, например, посчитать сумму всех чисел и сразу отбрасывать числа, произведение которых больше этой величины. Эта элементарная оптимизация уже немного сократит время.

aquadon ★★★★★
()
Ответ на: комментарий от Deleted

Это третьепитон, тут range работает как xrange во втором. В данном случае на решение задачи это не сильно влияет.

conformist ★★★
() автор топика
Ответ на: комментарий от conformist

Хм. Попробуй сделать так, как я предложил выше (с бинпоиском второго числа) - это будет сложность O(n * log n) - по идее должно пропихнуться в ограничение.

Balantay
()
Ответ на: комментарий от Balantay

1 1 1 1 1 1

судя по коду там 1 2 3 4 5 6 и т.д.

Deleted
()

если i * j > rsum - i - j, то i * (j + 1) > rsum - i - (j + 1). Т.е. внутренний цикл делай от 1 до n и прерывай сразу, как только превысило. Также можно начинать внутренний цикл от i, чтобы зеркальные дубликаты не учитывать. Также можно посчитать верхнюю границу цикла для i.

Legioner ★★★★★
()
Последнее исправление: Legioner (всего исправлений: 2)
Ответ на: комментарий от conformist

1000000

кто-то еще квадрат советует оптимайзить, ага

f1u77y ★★★★
()

Ищи пары множителей числа (n(n+1)/2)+1 и вычитай из каждого множителя в паре по единице. Как минимум один из множителей не может быть больше квадратного корня.

beresk_let ★★★★★
()
Последнее исправление: beresk_let (всего исправлений: 1)

пиши nlog n как уже сказали и засылай по pypy(у меня python на самом оптимальном, что я смог написать, 14с работает)

f1u77y ★★★★
()
def func(n):
    n += 1
    lst = []
    nrange = range(1, n)
    rsum = sum(nrange)
    for i in nrange:
        for j in range(i + 1, n):
            if i * j == rsum - i - j:
                lst.append((i, j))
    return lst
kernelpanic ★★★★★
()

Обзываем элементы последовательности a. i-й элемент будет a_i. Считаем сумму всех элементов, S.

Требуется найти a_i и a_j такие, что a_i * a_j = S - a_i - a_j. Путём нехитрых манипуляций получаем a_i = (S - a_j) / (a_j + 1). Стало быть, нам нужно перебрать все a_j и посчитать соответствующие им a_i. Для ускорения проверки перед проходом кладём все элементы в hashset. Итого — O(NlogN). Если все элементы целые, нужно ещё проверять, что частное будет целое. Ещё чуть быстрее.

i-rinat ★★★★★
()
Ответ на: комментарий от kernelpanic

Сейчас бы вместо одного квадратичного решения предложить другое квадратичное...

Softwayer ★★
()
Ответ на: комментарий от f1u77y

решение за O(n)

Что-то я сомневаюсь, что есть за O(n).

Если элементы последовательности — натуральные числа, тогда да, O(N).

i-rinat ★★★★★
()
Последнее исправление: i-rinat (всего исправлений: 2)
Ответ на: комментарий от Legioner

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

beresk_let ★★★★★
()

Ну тупо отсечь, например, так: берем сумму всех чисел в диапазоне (всех), а потом для каждого члена последовательности смотрим, делится ли сумма - a(i) на a(i). У кого делится, тех и перебираем.

anonymous
()

В общем случайно наткнулся на решение на java с пояснением:

import java.util.*;

/**
 * http://www.codewars.com/kata/is-my-friend-cheating/
 */
public class IsMyFriendCheating {
	
    /*
     * The sum of numbers 1..n is n*(n+1)/2
     * So, define the operation sum(n) as n -> n*(n+1)/2.
     *
     * For any pairs (a,b) in 1..n s.t. a < b, where
     * sum(n) - a - b = a * b, we note that
     *
     * sum(n-1)/(n+1) <= a < sqrt(sum(n)+1) - 1
     * and
     * b = (sum(n)-a)/(a+1)
     */
    public static List<long[]> removNb(long n) {
        LinkedList<long[]> pairs = new LinkedList<>();
        long sum = n * (n + 1) / 2;
        long lowerBound = ((n - 1) * n / 2) / (n + 1);
        long upperBound = (long) Math.sqrt(sum + 1) - 1;
        for (long a = upperBound; a >= lowerBound; a--) {
            long b = (sum - a)/(a + 1);
            if (a * b + a + b == sum) {
                pairs.addFirst(new long[]{a, b});
                pairs.addLast(new long[]{b, a});
            }
        }
        return pairs;
    }

}
переписал его на python:
def func(n):
    lst = []
    rsum = (n * (n + 1)) / 2
    low = ((n - 1) * n // 2) // (n + 1)
    up = round((rsum + 1) ** 0.5 - 1)
    for a in range(low, up + 1):
        b = int((rsum - a) // (a + 1))
        if a * b + a + b == rsum:
            lst.append((a, b))
    return lst
Прошёл. После прохождения можно глянуть лучшие решения, скину одно, может кому интересно будет:
def removNb(n):
    sum = n*(n + 1)/2  
    return [(x, (sum - x) / (x + 1)) for x in xrange(1, n+1) if (sum - x) % (x + 1) == 0 and 1 <= (sum - x) / (x + 1) <= n]
Всем спасибо :)

conformist ★★★
() автор топика
Ответ на: комментарий от anonymous

нет, все классно. Только вот деление есть, да

f1u77y ★★★★
()
Ответ на: комментарий от beresk_let

Ну там тривиальные рассуждения, не стал их расписывать. Да, конечно при положительных числах это всё имеет смысл, у топикстартера в цикле по крайней мере именно так идёт. С отрицательными будет интересней.

Legioner ★★★★★
()

Кстати я туплю, есть ещё простое и очевидное решение. Цикл по i идёт от 1 до какой-то границы (по идее в районе корня, надо распиывать). Далее имеем:

i * j = rsum - i - j
i * j + j = rsum - i
(i + 1)*j = rsum - i
j = (rsum - i) / (i + 1)

т.е. надо проверить, делятся ли эти числа нацело и если делятся, то ответ готов. Таким образом внутренний цикл не нужен. Сложность будет в районе O(N^(1/2)).

Legioner ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.