javacoder1's blog

DP SOLUTION NEEDED!!
By javacoder1, history, 8 years ago, In English

You have a string of length 10^5 which is a binary representation of a number.The string has no leading zeros like 11001 represent the number 25. We have to represent it as sum of numbers of the form of 2^x or -2^x (x>=0) . Find the minimum number of numbers needed to do so. Please highlight the states you use and the transitions when replying !

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

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

A binary number can be converted to a decimal by using the following formula: \sum_{i=0}^n a_i2^{n-i} Where a is the binary representation of the number. Therefore a simple solution is this: 

printf("2^%d", n);
for(int i = 1; i < n; i++) {
  if(a[i] == '1') {
    printf("+2^%d", n - i);
  }
}
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You didn't understand the problem. For example, take 7. The answer isn't 1+2+4, it is 8-1

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

http://codeforces.net/contest/132/problem/D

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

    Can you explain the dp part , i read the editorial but could not get it properly.

    → Reply