hulk_baba's blog

Use of Hash Map unclear
By hulk_baba, 8 years ago, In English

Please go through the problem. I was impressed by this solution which is what editorial also suggested editorial. I got how to compute 2's power and what needs to be added to get the power of 2 but can't understand how they are calculating the count of such pairs? Please explain with context to what editorial and solution are trying to do.

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that there are two cases for the count: if ai + ai is a power of 2, and if it isn't. In the first case, you have that you can pair ai with the other cntai - 1 elements for sum = 2ai. (i.e. all of the indices that are not i, but their value equals ai).If you do not substract 1 from cntai, you would be pairing an element with itself. In the second case, you can pair it with cntsum - ai elements, as sum - ai ≠ ai. Then, you have no risk of pairing an element to itself. What the guy with the submission did was substracting 1 from cntai before adding cntsum - ai to the answer in order that, if 2ai = sum, ans only increases by the corresponding amount (cntai - 1), and if it 2ai ≠ sum, it increases by cntsum - ai. Therefore, both cases are handled at once. Finally, note that you are counting each valid pair twice. You are counting the pair (a, b) first when i = a, and then when i = b. In order for the algorithm to give the correct answer, you must account for this by dividing ans by 2.

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

    Thank you Saat. It was really helpful. I guess this was also what editorial suggested except that they did not restore the value of cnt[a[i]]. Am I rightly saying so?

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

      Yes, that was what the editorial suggests. Only that managing that special case is a little bit tedious to write

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

I don't know why my this code gives TLE. I just used other way of counting by keeping the records of elements already looked. Could you help me please.

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

    Not completely sure about it, but according to my experience, every time you consult the value of something in a map, if the node was not created, it is created now. (i.e. suppose that values in cnt were 1-10. Then, if you search cnt11, a new node is created.) Then, while adding to ans, the size of cnt can increase by a factor of 32. As this is the heaviest part of your code, it is prone to TLE

    → Reply