OJ Board

Posted: **Fri Jun 11, 2010 12:17 am**

hmm. I found the bug. For 2 rather simple test cases:
accepted/accept
success/scs

Posted: **Sun Feb 13, 2011 10:46 am**

Can someone please explain to me the idea behind the problem ? any hint about the recurrance relationship please ?

Posted: **Fri May 20, 2011 11:29 am**

I made DP a solution for this problem using a 2-D memo table..And I'm sure my logic is working..But I didn't deal with big integer case..Because c/c++ can't allocate huge memory for a char memo[10000][100][100] array..Can anyone tell me how I can handle memory limitation?If u say to handle it by using STL vector,then would u plz tell me how to use vector for character array..?
Edit: GNU compiler can supports this array..and I solved it...

Posted: **Mon Jan 30, 2012 10:23 pm**

My Acc prog gives the following o/p for these cases

Code: Select all

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffgggggggggghhhhhhhhhhiiiiiiiiiijjjjjjjjjjkkkkkkkkkkllllllllllmmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
abcdefghijklmnopqrstuvwxyz
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Code: Select all

66400000000000000000000000000
133352780953543421259359468955239189723988854631557625988982658421013199754408615273536

happy coding

Posted: **Mon May 04, 2015 7:14 am**

RTE for a few times in a row now. I've tried the inputs in this thread and other inputs using udebug.com and my program got the right results and didn't crash. Please provide more tricky I/Os. If you can help in finding the bug, here's my code:

Code: Select all

Code deleted after AC

Posted: **Mon May 04, 2015 9:18 am**

How can I edit my post? I checked the FAQ and it said that there's a button for editing posts but I can't find it. I want to edit my code above.
I found a bug but it still gets RTE. I want to fix that bug (even though the program still doesn't work, it's still one less bug), but I can't
edit my post.

Posted: **Thu May 14, 2015 2:59 am**

There should be near the post.

Posted: **Thu May 14, 2015 3:02 am**

...which I also can't find. (along with delete).

Anyway, how come it's about big integer? I thought that "Z nor any prefix or suffix of Z will have more than 10100 distinct occurrences in X as a subsequence."

Posted: **Thu May 14, 2015 1:30 pm**

...which I also can't find. (along with delete).

So I'm not the only experiencing this problem.

Anyway, how come it's about big integer? I thought that "Z nor any prefix or suffix of Z will have more than 10100 distinct occurrences
in X as a subsequence."

That was also my question. But when I looked at the posts in this thread there were answers that are beyond the capacity of long long. I
tried udebug.com and it can also handle big values. So I made my code capable of handling large values.

Anyway, do you have any idea why I'm getting RTE? I now have 4 straight RTEs.

Posted: **Mon Jun 15, 2015 9:18 am**

Why WA?

Code: Select all

AC with Java BigInt

If we're following uDebug's cases, then it's the BigInt problem. I've coded it in python, and the same logic gives the same answer for the first case, and for the second, it gives off a RuntimeError, exceeding maximum recursion depth.

uDebug input:

Code: Select all

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccddddddddddeeeeeeeeeeffffffffffgggggggggghhhhhhhhhhiiiiiiiiiijjjjjjjjjjkkkkkkkkkkllllllllllmmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
abcdefghijklmnopqrstuvwxyz
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

uDebug output:

Code: Select all

66400000000000000000000000000
133352780953543421259359468955239189723988854631557625988982658421013199754408615273536

Posted: **Thu Jun 18, 2015 8:45 am**

According to Halim's book CP3, you really need to use BigInt.

Posted: **Tue Feb 14, 2017 4:01 am**

To clarify, the reason big int is required is because the statement is supposed to say 10^100, not 10100

Also the description of "subsequence" is cribbed directly & without credit from Intro to Algorithms, which is shameful to say the least.

OJ Board

10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences

Re: 10069 - Distinct Subsequences