for example in count sign sequences problem
I can calculate if length <28
but after that my program hangs (I use c++ (compiler g++) and my computer is a bit slow)
3 years, 10 months ago
Well, that's the trick. You have to reduce the complexity of your code. For example, if you are solving the problem by evaluating every sequence of length 40, the computer would undergo enormous amount of calculations and that's not the way the designer of problem meant it to be solved. That's why number 40 is chosen to make the problem hard to solve. You might often think regarding many CS problems that its impossible to solve it by reducing it's calculations but many a times its surprisingly possible like in this problem.
Log in to reply
This is exactly right, thanks! A big part of computer science is finding the most efficient algorithm, so that it can handle very large inputs such as these.