x is and Element of Array 1 and y is the element of array 2, Find the number of ways in the two arrays where x^y>y^x (NOTE: ^ denotes power here and not the XOR)
First line inputs the number of test cases, second line input the number of elements in two upcoming arrays third line inputs the first array fourth line inputs the second array
EXAMPLE: sampleINPUT:
1
3 2
2 1 6
1 5
sampleOUTPUT 3
<<HERE IS MY POOR CODE,JUST A BRUTE FORCE!!>> IS THERE ANY WAY TO SOLVE IT IN TIME LESS THAN THIS??
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int m,n;
cin>>m>>n;
vector<int> vm(m,0);
vector<int> vn(n,0);
for(auto &it:vm)
cin>>it;
for(auto &it:vn)
cin>>it;
int counts=0;
for(int x:vm)
for(int y:vn)
{
if(pow(x,y)>(pow(y,x)))
{
counts++;
}
continue;
}
cout<<counts<<endl;
}
}
I think if the elements are positive integers then pow(x,y) > pow(y,x) can be written as ylogx > xlogy implies logx/x > logy/y.
So for integer in the two arrays calculate logx/x , sort them and then count can be calculated in O(n+m).
Assume that you have $$$a^b$$$ and $$$b^a$$$. $$$a^b$$$ is greater than $$$b^a$$$ if $$$a$$$ is closer to $$$e$$$ than $$$b$$$ and vice-versa.
Using this property, we can say that $$$x^y > y^x$$$ if $$$|e-x| < |e-y|$$$.
Your code is $$$O(n^2y)$$$ if you use normal exponentiation or $$$O(n^2 \log{y})$$$ if you use fast exponentiation.
We can do better. Let's assume that $$$e = 3$$$ (please don't downvote). We can store $$$|e-x|$$$ in set 1 and $$$|e-y|$$$ in set 2. Since we're using sets, all elements are sorted. We can iterate through all elements in set 1 and use binary search to find the smallest element in set 2 such that it's greater than the current $$$|e-x|$$$. If there is such an element, add set2.size()-pos+1 (if you number the elements from $$$1$$$ to $$$n$$$) where pos is the position of the element in the set.
Total complexity: $$$O(n \log{n})$$$.