0

Здравствуйте,

В уравнении приведенном ниже нужно посчитать кол-во решений(integer solutions). Использование 5 for loops естественно будет слишком долгим, я так понимаю O(n^5). Есть подсказка в том что нужно использовать Hash Table. По какому принципу лучше распределить числа в таблицы? Какую Hash Function можно было бы использовать? Я пытался подойти к этой проблеме пытаясь работать с парами, то есть y_1^3+y_2^3 и хранить их суммы, решение получается все равно слишком долгим.

Был бы благодарен любой наводке!

введите сюда описание изображения

0

2 ответа 2

2

Переписал решение Harry на питон. Время выполнения у меня составляет меньше 2 секунд.

K = 200
J = -300
H = 749
S = 1000
R = 344
U = -265

yrange = range(-65, 65 + 1)

def intersection(l, r):
    return sum(r[key] * l[key] for key in r if l.get(key))

def main():

    l, r = {}, {}

    for y1 in yrange:
        for y2 in yrange:

            rval = S - R * y1 ** 4 - U * y2 ** 5
            if rval in r:
                r[rval] += 1
            else:
                r[rval] = 1

            for y3 in yrange:

                lval = K * y1 ** 3 + J * y2 ** 3 + H * y3 ** 3
                if lval in l:
                    l[lval] += 1
                else:
                    l[lval] = 1

    return intersection(l, r)

if __name__ == '__main__':
    import timeit
    print(timeit.timeit(main, number=1))
3
  • Ага, я что-то не сообразил вычисление правых частей внести в общий цикл...
    – Harry
    22 фев 2018 в 9:13
  • @Harry Ну даже на питоне это разница в сотых долях секунды. Выигрыш минимальный.
    – user207200
    22 фев 2018 в 9:18
  • Это да. Тут можно сыграть на предвычислении степеней и на циклах от 0 до 65 с вариацией знаков. Впрочем, как я понимаю, для задачи такого уровня это уже не столь существенно - выжимать миллисекунды...
    – Harry
    22 фев 2018 в 9:27
1

Ну, как минимум O(n^4) - потому что пятая переменная вычисляется из предыдущих четырех. А 131^4 - это меньше 300 миллионов, уже практически реально :)

Далее, запишем как K..+J..+H.. = S-R..-U.. - ну, вы поняли :)

Левая часть может иметь 131^3 = 2 с небольшим миллиона значений. Складываем в тот же хеш. Правая часть - и того меньше, 17 тысяч. После чего находим пересечения этих таблиц - вот они и есть решениями...

Update

Вот решение на С++

#include <iostream>
#include <iomanip>
#include <map>

using namespace std;

const long long K = 200, J = -300, H = 749, R = 344, U = -265, S = 1000;

long long intersection(const map<long long,int>& l,
                       const map<long long,int>& r)
{
    long long sum = 0;
    auto first1 = l.begin(), last1 = l.end();
    auto first2 = r.begin(), last2 = r.end();
    while (first1 != last1 && first2 != last2)
    {
        if (first1->first == first2->first)
        {
            sum += first1->second*first2->second;
            ++first1; ++first2;
        } else if (first1->first < first2->first) ++first1;
        else ++first2;
    }
    return sum;
}

int main()
{
    map<long long,int> l,r;
    for(long long y1 = -65; y1 <= 65; ++y1)
        for(long long y2 = -65; y2 <= 65; ++y2)
            for(long long y3 = -65; y3 <= 65; ++y3)
                l[K*y1*y1*y1 + J*y2*y2*y2 + H*y3*y3*y3]++;
    for(long long y4 = -65; y4 <= 65; ++y4)
        for(long long y5 = -65; y5 <= 65; ++y5)
            r[S-R*y4*y4*y4*y4-U*y5*y5*y5*y5*y5]++;

    cout << intersection(l,r) << endl;

}

У меня работает около 2 секунд. Накинем на то, что это Python, порядок (понятно, что я утрирую) - все равно до часа далеко...

17
  • То есть хотите сказать что O(n^4) это самый быстрый вариант решения? 22 фев 2018 в 6:13
  • Нет. Предложенный мною далее - уже O(n^3), например...
    – Harry
    22 фев 2018 в 6:14
  • Учесть то что мне нужно использовать питон, я думаю это займет около часа :) 22 фев 2018 в 6:20
  • Ну это вряд ли... Я с Питоном не дружу, а с С++ сейчас поиграюсь.
    – Harry
    22 фев 2018 в 6:22
  • Если честно я не совсем понял что вы предлагаете сделать, в первую таблицу положить значения всех комбинаций с (Ky_1^3 + Jy_2^3 + Hy_3^3, а во вторую (S - Ry_4^4 - Uy_5^5) ? и потом найти их пересечения? 22 фев 2018 в 6:23

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.