I am interested in one of the problems that I encountered in one of the server for programming contest but I could not solve it for a long time.
Given small number (<=10) of DNA disease segments (of characters A,G,T,C) of small length <=10, ask how many DNA sequences of a given length (<=20000000000) do not contain those sequences. The answer should be the remainder of division by 100000. For details, please look at the link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2778. The limit is 1s. Let n denote the given length of those sequences. I have some idea for small maximum length of the string like around 5 then the dimension of the matrix is 4^4 x 4^4, and the matrix denote how sequences ending at 4 random characters and do not contain disease segment grow. Then the complexity would be (4^4) ^ 3 * (2 log n). But for sure, the dimension is huge when maximum length is 10 it would be 4^9 x 4^9. I am doubtful about my matrix... Phuong --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
