Please read the new rule regarding the restriction on the use of AI tools. ×

Swayam78's blog

1 line soln for Today Div 2 C
By Swayam78, history, 4 hours ago, In English

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.

283646208

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

With the help of truth table of all possible combinations for the i pos bit.

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep.

    → Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
4 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

I also want proof of it as I went with most common solution of constructing a bit by bit

→ Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Dayyum :D I went too brute i guess haha

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Almost Everybody have done the same.

    → Reply
    • »
      »
      »
      4 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        3 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        did your carry approach get ac? if yes can u explain it pls

        → Reply
        • »
          »
          »
          »
          »
          3 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 hours ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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

              → Reply
»
3 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

wait damn how does this work? also how did you get this idea? just looking at samples or something

→ Reply
»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

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

why is that

. 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.

→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks.

    → Reply
  • »
    »
    114 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain , Why we don't take care of carry part?

    → Reply
    • »
      »
      »
      99 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
»
87 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me what's wrong w/ my code? I also just did bit by bit comparisons: 283629286

→ Reply
  • »
    »
    84 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Use 1ll<<i, otherwise will get overflow

    → Reply
    • »
      »
      »
      74 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      and this is why you're master unlike me :orz:

      → Reply