GRAYSC - Editorial

editorial
, , , ,
16

Solved in O(n^2) time complexity

1 Like
17

I had the same algorithm initially, but i believe test data was not correct at that time. Then i switched to pigeonhole.

18

I think that you can always test input with assert statement in C/C++ and if your check fail you will get SIGABRT instead of WA, so you can write your feedback…

1 Like
19

Yeah i know. But somehow at that time, i wasn’t convinced with this algorithm and pigeonhole was another idea in my mind. So i stopped thinking too much about it :wink:

20

oops sorry something gone wierd please refer to the solution at CodeChef: Practical coding for everyone and tell me for what cases it goes wrong…

21

it returns no for

6
2 3 2 6 14 6
1 Like
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