Google Kickstart Round-D-2019(1st Problem's unofficial editorial)

The editorial to the first problem hasn’t been released yet , so here we go :slight_smile:

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 :slight_smile:

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 array till you find the first odd(bits) element… and that’s your answer :slight_smile:

9)Now , a question might arise, why does removing an odd element makes ‘m’ an even bits number ? You can try many examples and you’ll always find that it always true!!!…I leave the proving part up-to you (it is easy as well!!)

10)You can keep track of all the odd elements using a map.

If you have different solution to this problem, you may share int the comments :slight_smile:

Link to my solution for full points:- TrGEAY - Online C++0x Compiler & Debugging Tool - Ideone.com

1 Like

Can you tell me about kickstart,
I didn’t participate from round one. Is it recommended to do it now ?

How is it different from other contests like codejam, hashcode, hackercup…etc ?

1 Like

This is how I feel:-
About Round-D :- It was not so easy. Very few people got AC(full pts) in first problem. 2nd and 3rd problem were Hard.
So its like a Div-1 contest but problems require fast and creative thing, just knowing some random concepts won’t help.
Best things:- You don’t need many pre-requisites. All you need is problem-solving skills :slight_smile:

1 Like

good editorial…but your code is so bad as always :grimacing::grimacing:

Thankyou :slight_smile: :slight_smile: :slight_smile: