Hello,

In the equation below you need to count the number of solutions (integer solutions). Using 5 for loops will naturally be too long, as I understand it O (n ^ 5). There is a hint that you need to use the Hash Table. What is the best way to distribute numbers in tables? What Hash Function could be used? I tried to approach this problem by trying to work with pairs, that is, y_1 ^ 3 + y_2 ^ 3 and store their amounts, the solution is still too long.

Any tip would be grateful!

enter image description here

    2 answers 2

    Well, at least O (n ^ 4) - because the fifth variable is calculated from the previous four. And 131 ^ 4 is less than 300 million, it’s almost realistic :)

    Next, we write K .. + J .. + H .. = SR ..- U .. - well, you get the idea :)

    The left side may have 131 ^ 3 = 2 with a small million values. Fold in the same hash. The right side - and even less, 17 thousand. After that we find the intersections of these tables - so they are the solutions ...

    Update

    Here is the C ++ solution.

    #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[SR*y4*y4*y4*y4-U*y5*y5*y5*y5*y5]++; cout << intersection(l,r) << endl; }

    I have about 2 seconds running. Throw on the fact that this is Python, the order (of course, that I exaggerate) is still an hour away ...

    • So you want to say that O (n ^ 4) is the fastest solution? - Denis Orekhov
    • Not. Offered by me further - already O (n ^ 3), for example ... - Harry
    • Considering the fact that I need to use a python, I think it will take about an hour :) - Denis Orekhov
    • Well, it is unlikely ... I am not friends with Python, and now I will play with C ++. - Harry
    • To be honest, I didn’t quite understand what you propose to do, in the first table put the values ​​of all combinations with (Ky_1 ^ 3 + Jy_2 ^ 3 + Hy_3 ^ 3, and the second (S - Ry_4 ^ 4 - Uy_5 ^ 5)? And then find crossing them? - Denis Orekhov

    Rewrote Harry's solution to python. My runtime is less than 2 seconds.

     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))
    • Yeah, I didn't realize something about the calculation of the right parts to the general cycle ... - Harry
    • @Harry Well, even on python, this is the difference in hundredths of a second. The win is minimal. - mkkik
    • This is yes. Here you can play on the prediction of degrees and on cycles from 0 to 65 with a variation of the signs. However, as I understand it, for a task of this level it is no longer so important - to squeeze in milliseconds ... - Harry