GRAYSC - Editorial

editorial
, , , ,
22

such a luck :-/

@author + tester: is there test case where correct tuple are numbers with indexes 64, 65, 66, 67 ? It should get TLE…

23

try this… 2 0 2 3 2 6 2… it has “2 xor 2 xor 2 xor 2 = 0”… Is ur algo right for this?

24

yeah it works. output is “yes”.

1 Like
25

This is just a tip, but you should use %lld instead of %I64d, maybe this is the problem (it’s written in help).

26

I think that @saurabhmodi102000’s description is clear about this…

If not, try to find sequence where xors are A, A, B, B, C, C, such sequence is A = { 2, 3, 2, 6, 2, 10, 2 }, but if you choose 4 times 2 the result is 0.

27

Thanks for the tip, but it still gets WA.

28

That is the logic behind the O(n) solution, but there are corner cases to consider. See the first post.

29

sorry for confusion I meant %llu in this case, now it should work fine :wink:

anyway, I’m still interested in counter example…

1 Like
30

I have a problem… The problem gets Accepted everytime I submit your solution… However if I write my own Brute Force code and submit it it gives TLE… Any clues why?

31

you are using long long instead of unsigned long long, when I removed unsigned I got TLE, but I have no idea why…

32

Note : n < 2^64, so using signed long long changes the numbers(due to overflow), and this violates the property mentioned in the problem.(maybe due to which program is unable to find a solution and run in O(n^4))

2 Likes
33

here is the counter example

5
9223372036854775808
9223372036854775809
9223372036854775810
9223372036854775812
9223372036854775816
34

Wow it got accepted now! I didn’t know there was a different specifier for unsigned long long. Thanks!

35

@neil_812 :thanks

36

@javadecoder: is there something incorrect in my post?

37

Can you please tell me what is wrong with this code?

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long int
int main() {
	int n;
	cin>>n;
	ll arr[n];
	for(int i=0;i<n;i++) cin>>arr[i];
	
	map<ll,ll> freqs;
	
	bool ans = false;
	
	ll prev = arr[0]^arr[1];
	freqs[prev]++;
	for(int i=1;i<n-1;i++){
	    ll val = arr[i]^arr[i+1];
	    if(val!=prev){
	        if(freqs[val]==1){
	            ans=true;
	            break;
	        }
	        else
	            freqs[val]++;
	    }
	    prev=val;
	}
	if(ans)
	    cout<<"Yes\n";
	else
	    cout<<"No\n";
        
	return 0;
}
38 
#include <bits/stdc++.h>
#define ll long long
using namespace std;//coded by abhijay mitra
int main()
{
    int n;cin>>n;
    std::vector<unsigned ll> v(n+20,0);bool c=0;
    for (int i = 0; i < n; ++i)
        cin>>v[i];
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j<n; ++j)
            for (int k = j+1;k<n ; ++k)
                for (int z = k+1; z < n; ++z)
                    if(v[i]^v[j]^v[k]^v[z]==0){
                        cout<<"Yes";return 0;
                    }
    cout<<"No"; return 0;
}

what is wrong with this?

39

// GRAYSC Problem - CodeChef

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

void solve() {
int n; cin >> n;
vector v(n); for (int &i : v) cin >> i;

if (n >= 130) {
	cout << "YES";
	return;
}

sort(v.begin(), v.end());

for (int i = 0; i < n; ++i) {
	for (int j = i + 1; j < n; ++j) {
		for (int k = j + 1; k < n; ++k) {
			int x = (v[i] ^ v[j] ^ v[k]);

			if (binary_search(v.begin() + k + 1, v.end(), x)) {
				cout << "YES";
				return;
			}
		}
	}
}

cout << "NO";

}

int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

solve();

}

Why am I getting wrong answer on this ?? Need some help