avik26091998's blog

Unary
By avik26091998, history, 7 years ago, In English

133B — Unary

In the Editorial of The Problem 133B — Unary.......It is given to multiply by 16 and then add...i can't Understand Why to multiply by 16.....can anybody help????

Editorial Link — http://codeforces.net/blog/entry/3302

And why is this soln giving me negative decimal value for large binary value...Please help if i can correct my soln..

my soln — Your text to link here...

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

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

Concatenating two binary numbers of size 4 abcd and efgh to abcdefgh is the same as abcd*2^4 + efgh. Same reason why 27 = 2*10 + 7 or 1234 = 12*10^2 + 34.

Your solution doesn't work, because pow(2,x - i) will return a double.

You convert it implicitly into a long long. But for some big x and small i, the value of pow(2,x - i) will be too big for a long long, and therefore you will get an integer overflow, and you end up with a random number, possible negative.

Second, doubles only have a certain amount of accuracy. So computing the power and converting it back will almost always end up with an inaccurate result.

If you want to compute big exponents mod some number, take a look at this algorithm: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Each character of the original program is replaced by a binary code of length 4. This means that when you append code for one character, the rest of the code is shifted right by 4 binary digits, which is the same as multiplied by 24 = 16.

Storing power of 2 in long long overflows; you have to take modulo during the power calculation, not in the end (https://ideone.com/Kq9tBI)

→ Reply