LZD_DeViL0902's blog

By LZD_DeViL0902, history, 4 weeks ago, In English,

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;
    }
}

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LZD_DeViL0902 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LZD_DeViL0902 (previous revision, new revision, compare).

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Sort the array first. If the number is 1, solve manually in O(log(n)), check for integers that are greater than 1 and count them using upper_bound. If the number is 2, again solve by brute force as I couldn't figure out a mathematical way/expression of integer 2. Now if, the number is 3 and beyond you can check for the following mathematical expression: If both x and y are positive then you can just check: log(x).x>log(y).y so if both x and y are greater than e≈2.7183 then you can just check: x < y So overall complexity can reduce to O(max(Nlog(m),Mlog(N))). The log term comes due to binary search(upper bound for searching a number greater than another number). I have provided the maths. Hope you can code it out!! All the best!

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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})$$$.