Abhibansal53's blog

Problem 570-D
By Abhibansal53, history, 9 years ago, In English

Can anybody please explain me the following part of this Solution:- int t = H[h][l].second ^ H[h][r].second; bool ok = t — (t & -t); if(!ok) printf("Yes\n"); else printf("No\n");

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

int t = H[h][l].second ^ H[h][r].second; Each bit say that letter is odd counts or even. What's this means? (t & -t) Let's see on bit form. Put t = 1001100. So -t = 0110100 t & -t =0000100 And you can see, that smallest nonzero bit always stay nonzero. So, we should know, how much nonzero bits are there in t? If there is 1 or 0 nonzero bit, t = (t — &t) and t — (t & -t) = 0 and answer is "we can build polyndrom", else there are 2 or more bits and we can't built polyndrom. Sorry for my poor English :)

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

    I am not able to understand what does 't' mean here?

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

      For each query we have some letters. We can build from this letters polyndrom. If there are 2 or more letters, that appear odd counts, we can't build polyndrom. So, let's define for each letter a bit. For 'a' — first bit, for 'b' — second bit. And if 'a' appears odd counts — first bit equal 1, else equal 0. So, we have 26 bits and this bits build number. This is 't'. After this we should find number of nonzero bits.

      → Reply