Can anybody tell me how to approach this problem link-Kick Start - Google’s Coding Competitions
I think they provide detailed explanation of problem solution. Don’t they ?
Editorial is not yet out
that was in a codeforces blog which i read earlier…
https://codeforces.com/blog/entry/68535?#comment-530759
Then wait for sometime.
for 3rd question it already come wait for other two…
1 Like
@anon11801154
Here is my solution to the first Google Kickstart problem which was a bit tricky : -
Observations: -
1)If the xor of all the numbers in array is ‘x’, and ‘x’ is a xor-even-bits number, answer is ‘n’.
2)Say ‘m’ is the xor of full array , now how to handle updates?
If a[pi]=vi, do : m=m^a[pi](previous value)^vi(new value)
3)Again, if ‘m’ is xor-even number, output ‘n’ else , do this : -
4)If you observe carefully:- if each number in the array has even number of bits, then their xor will also have even number of bits and answer to the query will be ‘n’ .
5)If some numbers have odd bits and some have even number of bits, then the longest sub-array will always be a prefix or suffix.
Example : -
0 2 84 4 5 .
Answer is 3(0,2,84)
6)We know that ‘m’ is not a number with even number of bits as of now. It has odd number of bits.So if you remove a number from the end of the array which has even number of bits, ‘m’ will still be a number with odd number of bits…So unless, you find a number with odd number bits from the end or start, you need to keep removing elements 
7)In this case :- 0,2,84,4,5 , m(xor of full array)= 87 which has odd number of bits.
Now, remove, ‘5’ which has even number of bits, and now m=82(which still has odd number of bits )
.
.
.
Now, remove, ‘4’ which has odd number of bits…the array looks like this now :- 0 , 2 , 84 .
and m=86(which has even number of bits)…
8)So the solution is , remove a prefix or suffix of an array till you find the first odd(bits) element… and that’s your answer
9)Now , a question might arise, why does removing an odd element makes ‘m’ even bits? You can try many examples and you’ll always find it true…I leave the proving it part upto you (it is easy as well!!)
2 Likes