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.
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
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 |
Название |
---|
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.
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)
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: