Too Much Xor Problem

help
,
1

Where am I wrong in problem CodeChef: Practical coding for everyone?

My solution link is CodeChef: Practical coding for everyone

2

Though I was unable to solve problem but I can tell you that your code fails on
1
4
0 0 0 0
This problem was based on exception cases caused due to A[i]=0 , I felt :frowning:

1 Like
3

Oh yes bro you are correct even all the cases where first 4 elements are 0 and rest are anything else is also failing. Thanks bro

4

For n == 3 there are few more cases you need to take into consideration. For example:

3
1 0 2

You can make it good with the following operations:

1
1 2 3

Have a look at my submission: CodeChef: Practical coding for everyone

3 Likes
5

@cp_guy from what I can see your n==3 case is not complete.
You can look at my n==3 case here.

ps: my code is a bit messy there could be better ways to generalize it.

6

All fine but I can’t understand what u did here and what logic did u apply.

7

There’s easy way to handle n=3 without any ugly casework. After applying 1st operation, the seq doesn’t change in any further operations. So, you’re left with checking only 4 options-
check if the array is already good. If yes print 0.
else try 3 cases- operation on all 3 indices individually. If array becomes good in any of those, then print that operation otherwise print -1.

8

Your prob was so great that I couldn’t think of anything

1 Like
9

Okay, let me explain (I’ll do my best)

  1. For n <= 3 I just hard-coded the output based on different inputs
  2. For n > 4, you can always follow the below strategy to get a good sequence:
    1. find the first index that has non-zero value. If you are not able to find, then the output is -1
    2. Lets name the index as nzi. Now you can take another index nzi2 such that it is nzi-2 or nzi+2.
    3. If nzi is odd then fill all even indices with arr[nzi] ^ arr[nzi2]
    4. if arr[nzi] == arr[nzi2], then all the even indices are filled with zero. You can use nzi and any even index to make all the values at odd indices equal to arr[nzi]. Thus you get a good sequence.
    5. if arr[nzi] != arr[nzi2], then all the even indices are filled with some value say X. You can use any two even indices and make all values at odd indices equal to 0. Thus you get a good sequence.
    6. if nzi is even, you use nzi and nzi2 to first fill the odd indices and then fill even indices similar to steps 4 and 5
1 Like