Shuaib's blog

Weird selection of problems in the book "programming challenges"
By Shuaib, 12 years ago, In English

The book "Programming Challenges" has some very annoying selection of problems from UVa. In the chapter "Dynamic Programming", the second problem is "Distinct subsequences". The problem is simple DP, but the upper limit on possible result is 10^100. How on earth am I suppose to hold such a value in any of the builtin types in C++. I don't think the UVa judge will let me use any external libraries, would it? If not, the problem isn't only DP, it also requires an implementation of some form of BigInt within the solution.


Any ideas how to handle such a situation?

The problem in question is this: Distinct Subsequences
  • Vote: I like it
  • -15
  • Vote: I do not like it

12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Implement BigInt?
→ Reply
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
just implement it in Java and use its BigInteger built in library.
→ Reply
  • 12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yea, I am thinking of doing that. Thanks :)
    → Reply