Here , u just have to take a = c^d ,Then check if it do satisy the condition or not , if it doesn't then cout -1 , else cout a.
Proof: In my solution (283677605) you only ever add a bit to a if exactly one of c and d contains that bit, otherwise you either get a contradiction on the spot, or you don't add the bit and move on
why is that If you add that bit to a then (looking just at that bit) a | b=1 and so 1−c=d . If you don't add that bit, then a & c=0 and so b=d . If neither b=d nor c ^ d=1 holds then you can't construct such a . Note that carrying over never happens throughout the process.
. You can skip the latter cases and check if that value of a works, at the end. This is exactly equivalent to setting a=c ^ d and checking if it works.
With the help of truth table of all possible combinations for the i pos bit.
Yep.
.
I also want proof of it as I went with most common solution of constructing a bit by bit
I am working on it.
Proof Added.
Dayyum :D I went too brute i guess haha
Almost Everybody have done the same.
Yeah and I even considered carry and now i feel like carry part was totally wrong there but it was not even needed so no effect on solution :P
did your carry approach get ac? if yes can u explain it pls
Yes, it was accepted but I guess i did a bit more than what was required.
Actually I ran it in such a way that i was considering making a binary no. that gives carry and one which doesn't. And most probably it would have worked even if i was only considering to make a binary string which would just not give carry.
ik its just overkill but i am interested to know how it works. but arent there many binary no possible solutions if u consider carry part
exactly there are but i was taking just any 2 of previous step. I used just two string there and at any point i could get at most 4 strings and i took just any 2 out of them and go to next point. So simply i had to work on only 62*4 strings. That ain't much ig
wait damn how does this work? also how did you get this idea? just looking at samples or something
Proof added.
where i can see your proof?I want to know why this project can solve.
Now you can see it in Post.
dawg where
Now you can see it in Post.
Cool!
Proof: In my solution (283677605) you only ever add a bit to $$$a$$$ if exactly one of $$$c$$$ and $$$d$$$ contains that bit, otherwise you either get a contradiction on the spot, or you don't add the bit and move on
If you add that bit to $$$a$$$ then (looking just at that bit) $$$a $$$ | $$$ b = 1$$$ and so $$$1 - c = d$$$. If you don't add that bit, then $$$a$$$ & $$$c = 0$$$ and so $$$b = d$$$. If neither $$$b = d$$$ nor $$$c$$$ ^ $$$d=1$$$ holds then you can't construct such $$$a$$$. Note that carrying over never happens throughout the process.
. You can skip the latter cases and check if that value of $$$a$$$ works, at the end. This is exactly equivalent to setting $$$a=c$$$ ^ $$$d$$$ and checking if it works.
Thanks.
Can you please explain , Why we don't take care of carry part?
Think about it, you have $$$a$$$ | $$$b = d + (a$$$ & $$$c)$$$. If the bit of $$$a$$$ you're looking at is $$$0$$$ then this is just $$$b=d$$$, there is no addition thus no carrying over. If it's $$$1$$$ then you must have $$$1 = d + c$$$, so it's either $$$0+1$$$ or $$$1+0$$$, also no carrying. (you suppose you didn't get any carry from the last bit, by induction)
Amazing , Thanks
Could someone tell me what's wrong w/ my code? I also just did bit by bit comparisons: 283629286
Use 1ll<<i, otherwise will get overflow
and this is why you're master unlike me :orz: