Find possible values of a,b,c,d (my answer is giving tle)

[4z86RXSz]

Write your question here.
From an array of N(<=1000) we have to find all possible values of a,b,c,d such that a^2+b=c^2+d^2
We have to do it for T(<=5)Test cases
EX:-
1 <= T <= 5
1 <= N <= 1000
1 <= a[i] <= 1000000000 , for each valid i

Input:
1
4
1 2 3 4
Output:
15

I have taken 2 maps with key as a^2+b,c^2+d^2 respectively and finding the possible values that match still it is giving tle why

  Put the code you need help with here.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define re(n) for(ll i = 0 ; i < n ; i++)
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll arr[n];
        re(n)
        cin>>arr[i];
        unordered_map<ll,ll> h,h1,h2;
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            {
                ll prod = (arr[i]*arr[i])+(arr[j]*arr[j]);
                ll prod1 = arr[i]*arr[i]+arr[j];
                h[prod]++;
                h1[prod1]++;
            }
        }
        ll c=0;
        unordered_map<ll,ll>::iterator it;
        for(it=h.begin();it!=h.end();it++)
        {
            if(it->second>=1)
            {
                c+=(h[it->first]*h1[it->first]);
            }
        }
        cout<<c<<endl;
    }
    return 0;
}

[kbw]

Why do you need maps?

Don't you just evaluate the functions and compare the results?

[dhayden]

Every item you put into h gets incremented at line 24. So h will never contain zero as a value.

That means line 32 will always be true.

Okay, so you find a value that's a²+b². What's going on at line 34?

What should the output be? A count of the number of solutions? If so then why does line 34 add a product to the output number?

Bottom line: I can't figure out your algorithm. Can you explain in words how you're trying to solve this?

Oh, and if the numbers can be up to 1,000,000,000 then you may have to worry about overflow.

[jonnin]

a,c,d are the set of all numbers and b is the result of those values run through the equation?
are you only seeking INTEGER answers?

can you partly solve it with triangles? A2+B2 = C2? 3,4,5 and multiples for example? The groups of these are well known, there are not many. That isnt all the answers, but if b == 0, its *some* of the answers.

remember that C&D can be interchanged, so if 5,0,4,3 is a solution so is 5,0,3,4

another family of integer solutions is let b = x*x. then x*x + a*a = c*c+d*d and all the equality ones fall out, that is x = c , a = d, and x = d, a = c pop right out.

it seems likely there is something simple though. Take the equations and try to simplify it somehow... or graph it. its a math question. Brute force isnt the way.

not allowing zero seems to be the key.
I think the b = x*x and not allowing zeros makes it work. hang on.

[jonnin]

Still thinking. Not finding a generalized solution ... lots of things that work for 1234 don't really work.

[tpb]

I don't understand the example. How does 1,2,3,4 give 15?

EDIT: I think I've figured out that 15 is the count of how many ways there are to satisfy the equation, including duplicates. So the 15 ways (a,b,c,d) would be:

1,1,1,1
1,2,2,1
1,2,1,4
1,3,3,1
1,4,4,1
2,1,2,1
2,1,1,4
2,2,2,4
2,3,3,4
2,4,4,4
3,1,3,1
3,2,3,4
3,3,4,2
4,1,4,1
4,2,4,4

EDIT2: This gives the right answer for the example. I don't know how it would do on time, though.

#include <iostream>
#include <unordered_set>

int main() {
    typedef long long LL;
    std::unordered_multiset<LL> s;
    int a[1000];

    int t;
    std::cin >> t;
    while (t--) {

        int n;
        std::cin >> n;
        for (int i = 0; i < n; i++)
            std::cin >> a[i];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                s.insert(LL(a[i])*a[i] + a[j]);

        size_t cnt = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cnt += s.count(LL(a[i])*a[i] + LL(a[j])*a[j]);

        std::cout << cnt << '\n';
        s.clear();
    }
}

[tpb]

A bit of a speed-up:

#include <iostream>
#include <unordered_map>

int main() {
    typedef long long LL;
    std::unordered_map<LL, int> m;
    int a[1000];

    int t;
    std::cin >> t;
    while (t--) {

        int n;
        std::cin >> n;
        for (int i = 0; i < n; i++)
            std::cin >> a[i];

        for (int i = 0; i < n; i++) {
            LL ai = LL(a[i]) * a[i];
            m[ai * 2]++;
            for (int j = i + 1; j < n; j++)
                m[ai + LL(a[j]) * a[j]] += 2;
        }

        size_t cnt = 0;
        for (int i = 0; i < n; i++) {
            LL ai = LL(a[i]) * a[i];
            for (int j = 0; j < n; j++) {
                auto p = m.find(ai + a[j]);
                if (p != m.end())
                    cnt += p->second;
            }
        }

        std::cout << cnt << '\n';
        m.clear();
    }
}

[jonnin]

it seems like there should be a way to do it without the double loop. But I haven't found anything reliable. This problem is better than most of them.

[dhayden]

So the 15 ways (a,b,c,d) would be:

1,1,1,1
1,2,2,1
...

Although your code looks correct, 1,2,2,1 isn't a solution (1²+2 != 2²+1² I think the solutions for 1,2,3,4 are:

1 1 1 1
1 4 1 2
1 4 2 1
2 1 1 2
2 1 2 1
3 1 1 3
3 1 3 1
4 1 1 4
4 1 4 1
2 4 2 2
3 4 2 3
3 4 3 2
4 4 2 4
4 4 4 2
4 2 3 3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using std::cin;
using std::cout;
using std::endl;

int
main(int argc, char **argv)
{
    unsigned long long a,b,c,d;
    unsigned T, N;
    unsigned result = 0;
    
    cin >> T;
    while (T--) {
	cin >> N;
	std::vector<unsigned long long> nums;
	while (N--) {
	    nums.push_back(0);
	    cin >> nums.back();

	}
	// Sort them so we can find values quickly below.
	std::sort(nums.begin(), nums.end());

	// We're looking for 4 numbers such that c^2+d^2-a^2 = b.
	// Start will all possible values of c and d
	for (size_t ci=0; ci<nums.size(); ++ci) {
	    c = nums[ci];
	    for (size_t di=ci; di<nums.size(); ++di) {
		d = nums[di];
		unsigned long long cdsq = c*c + d*d; // (c^2 + d^2)

		// for values of a that make c^2+d^2-a^2 non-negative
		auto iter = std::upper_bound(nums.begin(), nums.end(), ceil(sqrt(cdsq)));
		for (auto aIter=nums.begin(); aIter < iter; ++aIter) {

		    // Compute b = c^2+d^2 - a^2
		    a = *aIter;
		    b = cdsq - a*a;

		    // If b is one of the numbers then a,b,c,d is a solution.
		    if (std::find(nums.begin(), nums.end(), b) != nums.end()) {
			cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
			++result;
			// a,b,d,c is also a solution if c and d are different
			if (c != d) {
			    cout << a << ' ' << b << ' ' << d << ' ' << c << endl;
			    ++result;
			}
		    }
		}
	    }
	}
	cout << result << endl;
    }
}

[tpb]

Yeah, a bunch of those "answers" of mine aren't right. I don't remember exactly how I generated them (I didn't keep that version of the program).

Your's definitely prints the correct replacements, but I'm not sure if it's a serious solution to the actual problem since it seems too slow. My last solution can solve the following worst-case test-generator in about 4 seconds. (The answers are 0 for all 5 test cases since the values are totally random in the given range.) After commenting out the couts of a,b,c,d in your program, how long does it take?

#include <iostream>
#include <random>

int main() {
    std::default_random_engine rnd(std::random_device{}());
    std::cout << 5 << '\n';
    for (int i = 0; i < 5; i++) {
        std::cout << 1000 << '\n';
        for (int i = 0; i < 1000; i++)
            std::cout << rnd() % 1000000000 + 1 << ' ';
        std::cout << '\n';
    }
}

[dhayden]

tpb, you're right, mine is much slower. I cancelled it after about a minute of runtime on your sample data. I suspect we'd all be dead and buried before it finished. :)

[4z86RXSz]

@tpb thanks now there is no TLE can you explain your code a little though that would be a great help :)

[4z86RXSz]

@tpb i understood your first code using multiset what can you explain the one below that thanks

[tpb]

The first one (with the unordered_multiset) goes through two n-squared loops. But that means that it inserts both the results for a[x],a[y] and a[y],a[x] into the set (if x!=y), which can be avoided by making the second loop start at i + 1 and incrementing the resulting map element by 2 (to count both orders). For the cases where x==y it just increments by 1.

I got the speed-up idea from one of jonnin's posts. I also agree with him that there should be a better way since this is still pretty brute force, but I can't think of it.

[4z86RXSz]

cool thanks for that explanation :)
yea i also think there should be a way other that brute force :/

[tpb]

Can you give the link to the problem?

[4z86RXSz]

https://www.codechef.com/ISCC2018/problems/T27 link to the problem

[jonnin]

what I am trying to figure out (math, and wow, I am rusty) is the b issue.

look at the solutions. B can't be 3. Why? Its tied to the squares ... 1 squared is easy to deal with, 2 squared is 4 and 4 is in the data, and 4 is in the data and can be square rooted.
I still think there is a way to detect invalid bs and remove them.

you can also see that if 3 appears, it has to appear twice, and it has to appear on the left and right sides to cancel itself out. Because 9 isnt in the data, and 3 isnt a perfect square.

But these are side-effects.... some of this info is only useful because the values happen to be 1,2,3,4 here. I am trying to find a provable tweak to discard known bad answers, and one that isnt so convoluted that you need N*N work to save a tiny bit of iteration.

It also feels like maybe one of the trig subs would do something here. But I haven't had a chance to look at those.

I have lost a lot of integer skills... I barely recall how to solve something such that the answer is a perfect int -- everything I am used to is in the real space.

[tpb]

b is definitely the tricky part, and probably the clue to a better solution. The original form of the equation in the codechef question (translated into our a,b,c,d variables) is

a = sqrt(c*c + d*d - b)

The usual form of the equation for a circle wouldn't have the -b at all.

However, it seems that b can be 3, e.g., 7*7 + 3 = 4*4 + 6*6