10069 - Distinct Subsequences

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 10069 - Distinct Subsequences

Post by amishera » Fri Jun 11, 2010 12:17 am

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

xander7b
New poster
Posts: 3
Joined: Wed Aug 25, 2010 4:57 pm

Re: 10069 - Distinct Subsequences

Post by xander7b » 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 ? :-?

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10069 - Distinct Subsequences

Post by Imti » 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... :D

Ahmad
New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

Re: 10069 - Distinct Subsequences

Post by Ahmad » 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 :D

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

Re: 10069 - Distinct Subsequences

Post by oja » 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
Last edited by oja on Fri Nov 27, 2015 2:33 pm, edited 2 times in total.

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

Re: 10069 - Distinct Subsequences

Post by oja » 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.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10069 - Distinct Subsequences

Post by jddantes » Thu May 14, 2015 2:59 am

There should be near the post.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10069 - Distinct Subsequences

Post by jddantes » 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."

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

Re: 10069 - Distinct Subsequences

Post by oja » 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.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10069 - Distinct Subsequences

Post by jddantes » 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
Last edited by jddantes on Tue Jun 23, 2015 10:19 am, edited 1 time in total.

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10069 - Distinct Subsequences

Post by jddantes » Thu Jun 18, 2015 8:45 am

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

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Re: 10069 - Distinct Subsequences

Post by Quantris » 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.

Post Reply

Return to “Volume 100 (10000-10099)”