whitedevil's blog

By whitedevil, 12 years ago, In English
what are the meaning of that ?

the first test case :

i get a binary number then ----- i convert it to decimal and get 220  :) that's right

the second test case :

i get a binary number then------i convert it to decimal i get a very large number 

the problem here i can't convert it to satisfy this condition 

Output the size of the equivalent Unary program modulo 
1000003 (106 + 3)
  • Vote: I like it
  • -11
  • Vote: I do not like it

| Write comment?
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
456 modulo 7, means: divide 456 by 7, and return the remainder. In c++ the operator that does this operation is %. Although it does not work very well with negatives.


456 % 7 = 1

You probably need this page: http://en.wikipedia.org/wiki/Modular_arithmetic

The reason it is used in contests is usually that the normal result of something would be very large, and big numbers are a hassle in many languages.

  • 12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    when i convert the second binary number  1010101010101010111010001101110  i get 2147483647 

     now how i can get the result in the second test case ?!
    • 12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      First read this: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=integersReals

      What happens is that the numbers 1000101101... in this problem can have many bits. A lot more bits than 64. So, it is hard to first convert it to decimal and then get the remainder.

      If you grab a calculator app that supports very large numbers, I think that even windows' does it, you can see the real conversion of that bit sequence is : 1431663726, if you calculate the mod, you will get: 659433

      Since there will be many more bits than 64, in this problem it is best to calculate the modulo on the go instead of first calculating the decimal value and then the modulo.

      So you will have a huge string
      s = "101010101010101010101110111110000...."

      The usual way to convert that to int is:

      res = 0
      for i = 0 , i < n {   res = res * 2 + int( s[i] ) }
      res = res % 1000003

      With modular arithmetic, you will see that you can do:

      res = 0
      for i = 0 , i < n {   res = (res * 2 + int( s[i] )  ) % 1000003  }

      And it will give the wanted result without causing overflow.

    • 12 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      You need to see "Modular arithmetic".
      Since you asked to output only "modulo 10^6+3 ".
      You can, at each step while converting from bin. to dec. , take modulo 10^6 + 3, that way the number never exceeds Integer range.

      Example :

      Binary number : 110 
      Decimal conversion Process :
      Expected Answer = ((2^0)*0 + (2^1)*1 + (2^2)*1) % (1000003);
      Modular arithmetic tells us:
      (A + B) % M  is equivalent to (A%M + B%M)%M;
      so at each step find the modulus, that is :
      Final Answer = ((2^0)*0% (1000003) + (2^1)*1% (1000003) + (2^2)*1% (1000003))% (1000003);