Help in finding error

help
1

Please help to find error in this solution for problem for Programmers Army Monthly Contest - Bit Manipulation.

Problem Link - HBOB02 Problem - CodeChef
My Solution with error - CodeChef: Practical coding for everyone
My AC Solution - CodeChef: Practical coding for everyone

1 Like
2

@ssjgz help in this any compiler warning or something else , these two solutions seems exactly same …then what’s the error

1 Like
3

That’s the same thing happened with me, My solution is exactly like yours but it give wrong ans when i submitted , I tested it on more than 100 test cases locally it give right answer but when i submitted it gives wrong.

2 Likes
4

The mistake that you have commited is nothing but to obtain current element
You are Xoring with every previous element which is occured before
As you are updating x in every case which is false in each case x should be the previous case’s un-updated y .

In short In order to obtain normal array from prefix array you are expected to XOR with previous element only and not the every element occured before which you are doing in second the Accepted solution

Here Your AC solution with first approach
with some modifications as discussed earlier

https://www.codechef.com/viewsolution/42150578

1 Like
5

@rushi2001 Can you please provide a testcase which gives different outputs for WA solution and AC solution?
I will appreciate.

6

my solution was same like you AC solution still got WA many times…Still don’t know where my solution fails :expressionless::expressionless:

7

I went through Your code and And I just found incorrect logic Which I then corrected and submitted which got accepted
I haven’t run updated code and previous code on any special testcase made by me though and just submitted which got accepted .
Also I tried later but I wasn’t able to find the corner case .
I think there might be a strong corner testcase .

8

No @rushi2001 rushi the logic is fine there is some other issue ,

9

@sunil5798 I had issue with similar problem and asked the same question. Please look following thread - https://discuss.codechef.com/t/weird-behaviour-of-c-code-during-submission/84862/6.
Maybe my last comment is the actual root cause.

10

Why I think the logic is incorrect
Let’s say we have array
1 2 3 4 5
It’s Prefix sum is
1 3 6 10 15

Now if We want to retain original array from prefix array
what we’ll do is
1 3-1 6-3 10-6 15-5
and not
1 3-1 6-3-1 10-6-3-1 15-10-6-3-1

I think the same case should have to happen with prefix XOR array
like

we have array
1 -----2-------- 3 --------4

its prefix XOR is
1-------1^2 ----------1^2^3---------1^2^3^4

from this normal array can be obtained by
Case 1 :
1----------(1^2)^(1)---------(1^2^3)^(1^2)-------- (1^2^3^4)^(1^2^3)

Gives 1----- 2----- 3 ------4

and not
Case 2 :
1----------- (1^2)^(1)-----------(1^2^3)^((1)^1^2)--------- 1^2^3^4^ ( (1)^(1^2)^1^2^3 )

gives = 1----- 2 -----2----- 6
Which is not our array

I think My explaination is correct ?
Tell me if you found anything wrong .

12

bro u interpreted wrong if u see above solution @sunil5798 is not doing any prefix sum … he just take xor of previous and current value…which is correct in both of cases

see in WA solution if u print x and y , u will see the X is previous value not the xor of array till i , and y = current_Y ^ just previous value.

should i explain more , or u dry run it ?

13

Ya that’s true . You Pointed it out correct .

But if You see same solution with some modifications it gives right answer I don’t know why

https://www.codechef.com/viewsolution/42150578

See this instead of restoring the value by xoring it again with x I restored it by using some temp variable and it worked
I don’t know how ?

And also i put example of prefix sum there
just for explaination i haven’t said he used it in program .

I used it to compare Prefix Xor with prefix sum .

14

it may possible just asking @sunil5798 after xoring again it exceeds int value ?

EDIT : My mistake , I missed that already int is defined as long long

15

I think the problem setter is fraud vector se karo AC mil rha ha and array se WA.Kuch to galat horha
@admin please take action its a 6 star coder who is complaining one of my junior also told about this problem.What others think?

16

Intriguing - I can’t find a well-formed testcase where this actually breaks. Of course, this is from a third-party contest so there’s always the possibility of broken test input …

One situation where the outputs may differ is if the test input provides less than N entries for the array - maybe someone could submit a quick test for this? Just adding:

assert(cin);

as the last line in main would do the trick.

Edit:

Hmmm … maybe not. I’d expect this solution to be a RE rather than a WA if that were the case …

1 Like
17

So how is vector making a difference sir and can u please give some advice on this matter should c++ coders should always stick to vectors, its important because sometimes there is a prize money for such third party contests as well so :sweat_smile:

18

In my hypothetical example - which is probably barking up the wrong tree (see my Edit):

  • In the case that doesn’t use vector, if there are fewer than N array elements provided in the test input, then:
int y;cin>>y;

will give an unintialised value of y (it’s Undefined Behaviour what you’ll get, but in practice y will likely retain the previous value it read).

  • In the case using vector, the final element of the vector will be 0.
2 Likes
19

I got ur point sir understood why the top rankers used vector for the same but vector has got issues too like with bound i guess it doesn’t provides exceptions as well but anyways thanks for ur reply sir :grinning_face_with_smiling_eyes: and thanks for this blog too @sunil5798

2 Likes