6
\$\begingroup\$

We have array of N (<=10^5) elements with Q(<=10^5) queries.

Each query is of type: p q r s x, where we have to find if there exist a element from array in range [p,q] and an element in [r,s] whose xor is equal to X. If exists, print "true" else "false".

Constraints:

1 <= N <= 10^5
1 <= p,q,r,s <= N
1 <= A[i] <= 10^5
Example: 
Array : 1 2 3 4 5 6
Query : 1 3 4 6 5 
Output: true.

1 from range [1,3] and 4 from range [4,6] has an XOR value equal to X=5.

I tried to solve it by loading the second sub array into a hashmap then XORing x with each element from first array and if the result exists in hashmap answer is yes.

But this \$O(n)\$ solution for each query isn't sufficient to pass. I am looking for ideas for how I can achieve this in possible \$O(logn)\$ or \$O(1\$) time for each query, or if it is possible to answer queries offline using MO's algorithm in \$O(sqrt(n))\$ time.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
int a[100001];

bool query(int p,int q,int r,int s,int x)
{
    unordered_map<int,int> mp;
    for(int i =r;i<=s;i++)
    {
        mp[a[i]]=1;
    }
    for(int i =p;i<=q;i++)
    {
        if(mp.count(a[i]^x) > 0)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    int n,q;
    cin>>n>>q;
    for(int i =0;i<n;i++)
    {
        cin>>a[i];
    }
    while(q--)
    {
        int p,q,r,s,x;
        cin>>p>>q>>r>>s>>x;
        // -1 because they are 1-indexed
        if(query(p-1,q-1,r-1,s-1,x))
        {
            cout<<"true\n";
        }
        else
        {
            cout<<"false\n";
        }
    }

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Apparently I misunderstood the question that we need to check if xor of the given ranges is required, but instead a element from both ranges is required \$\endgroup\$ – RE60K Jun 4 '17 at 11:37
  • \$\begingroup\$ That means i couldn't explain the problem well enough, what would you suggest i should edit in the post to make it more obvious? \$\endgroup\$ – Alexa yuki Jun 4 '17 at 11:39
  • 1
    \$\begingroup\$ Is the array guaranteed ordered? Or even guaranteed contiguous? \$\endgroup\$ – Deduplicator Jun 4 '17 at 11:45
  • \$\begingroup\$ array elements can be in any order, p,q,r,s are in range [1,N], but they do not overlap. and array elements are <= 10^5. I will update the statement with this info. sorry i missed out \$\endgroup\$ – Alexa yuki Jun 4 '17 at 11:48
  • \$\begingroup\$ Can you share a link to the problem statement, just in case? \$\endgroup\$ – vnp Jun 5 '17 at 5:19
1
\$\begingroup\$
  1. Avoid non-standard headers. Especially giant composite-headers like <bits/stdc++.h>. They make your program unportable and/or slow compilation down.

  2. You are using using namespace std;.
    That's a bad idea, read "Why is “using namespace std;” considered bad practice?".

  3. Aside from its obscuring impact if you ever used the typedefs, vi and ll are unused. Remove to minimize confusion.

  4. Do you know std::unordered_set? That's better for representing a set than std::unordered_map...
    Anyway, you should change the algorithm but we'll get there later.

  5. You should consider whether swapping the ranges can speed things up.

  6. The conditional operator (ternary operator, exp ? true_exp : false_epp) is perfect for choosing the value to use.

  7. You never check for input-failure or inputs being out-of-range.

Now the algorithm:

Consider initializing a std::unordered_multimap, or if duplicates are plentiful a std::unordered_map of sorted std::vector from the input-array.
Then for each query check every element in the smaller range whether element xor x is in the whole array, and filter that down to the second range.

\$\endgroup\$
  • \$\begingroup\$ 1 - 2.) I am aware of that, but at the moment i only wish to have a good algorithm for it. So this is my throw away code, you can say. 3.) those are some things i use very often, so are part of my basic template. 4. ) i choose unordered_map for easy (and efficient) look ups. and yes Algorithm needs changing. 5.) In worst case, the running time would still be O(N). 6) Ok. 7) It is guaranteed to follow the given constraints. \$\endgroup\$ – Alexa yuki Jun 4 '17 at 12:29
  • \$\begingroup\$ Algorithm part is almost same as i have implemented already. Which happens to be too slow :(. \$\endgroup\$ – Alexa yuki Jun 4 '17 at 12:30
  • \$\begingroup\$ Hm, we are Code Review, expect everything to be reviewed. Better lean it up before submitting here. Well, you are using the map as a set, so use a set. Yes, swapping the ranges does not change the algorithms asymptotic complexity, but every little bit might help. You know trust but verify? Or at least add a comment "Input is assumed well-formed". The changed algorithm only builds the structures for lookup once, which gets amortized over all queries. Should drop the complexity from O((range_1 + range_2) * lookup) to O(min(range_1, range_2) * lookup) (lookup depends on #unique) \$\endgroup\$ – Deduplicator Jun 4 '17 at 13:06
0
\$\begingroup\$

Besides what @Deduplicator said some comments.

  1. The easiest way to get the sets is constructing them directly from the ranges:

    std::vector<int> data;
    auto start = std::next(data.begin(), offset1);
    auto end = std::next(data.begin(), offset2);
    std::set<int> range(start, end);
    

That way you only have to deal with the considerably smaller subsets of the vectors.

  1. If you have a deterministic range do not use while loops. Thats what for loops are for.
\$\endgroup\$
  • \$\begingroup\$ 1. The overall complexity would still be the same, if not better :( \$\endgroup\$ – Alexa yuki Jun 5 '17 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.