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. I would appreciate if you can add proof for same.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Name |
---|
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.
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
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.