SIMPLE XOR - cook142b - my sliding window solution not working!

i have been working on this solution to the problem simple XOR which uses sliding window approach to get the answer.

The complexity is o(n) and works well with the constraints.
yet i keep getting wrong answer again and again.

any help would be appreciated, please look into the following code.

Note: here is the link to the problem.
https://www.codechef.com/COOK142B/problems/SIMPLE_XOR

// Template Code -> 16 may, 2022
//  by: kushagra sharma

#include <bits/stdc++.h>
// header files (pbds)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long int
#define MAXN 102
#define MOD 1000000007
#define fastio() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define debug(x) cout << #x << ": ";  _print(x); cout << "\n";
#define INF 1e18
#define end "\n"
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()


using namespace std;

// namespace for policy-based data structures
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template<typename T> void _print(T x) { cout << x << " "; }
template <class T, class U> void _print(pair<T, U> p);
template <class T> void _print(vector<T> v);
template <class T> void _print(set<T> s);
template <class T, class U> void _print(map<T, U> mp);
template <class T> void _print(multiset<T> v);
template<class T, class U> void _print(pair<T,U> p) { cout << "{ "; _print(p.ff); cout << ", "; _print(p.ss); cout << "}"; }
template<class T> void _print(vector<T> v) { cout << "[ "; for(auto &x : v) { _print(x); } cout << "]"; }
template<class T> void _print(set<T> s) { cout << "{ "; for(auto &x : s) { _print(x); } cout << "}"; }
template<class T,class U> void _print(map<T,U> mp) { cout << "{ "; for(auto &x : mp) { _print(x); cout << " "; } cout << "}"; }
template<class T> void _print(multiset<T> s) { cout << "{ "; for(auto &x : s) { _print(x); } cout << "}"; }


// used in sieve of eratosthenes
int spf[MAXN];


signed main() {

    fastio();

    int t; 
    cin >> t;
    while(t--) {
        
        int l,r;
        cin >> l >> r;
        
        int flag = -1;

        for(int i=l; i<=r-3; i++) {
            if(i^(i+1)^(i+2)^(i+3) == 0) {
                flag = 1;
                cout << i << " " << i+1 << " " << i+2 << " " << i+3 << "\n";
                break;
            }
        }

        if(flag == -1)  {
            cout << -1 << "\n";
        }
        
    }

    return 0;
}

Try this input:

1
5 8
1 Like

Hello suman!
Thank you so mych … but i’ve got the answer.
the problem is sorted when we do pairwise xor and then check if they give 0.

Here is the corrected loop:

for(int i=l; i<=r-3; i++) {
            int a = (i^(i+1));
            int b = ((i+2)^(i+3));
            
            if((a^b) == 0) {
                flag = 1;
                cout << i << " " << i+1 << " " << i+2 << " " << i+3 << "\n";
                break;
            }
        }

        if(flag == -1)  {
            cout << -1 << "\n";
        }

You should probably know the reason why your old code was failing.

1 Like