## 10069 - Distinct Subsequences

Moderator: Board moderators

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

### 10069 - Distinct Subsequences

I really have no idea that why I got WA(I thought it was just a simple DP problem).
Is there any special test case?

I'll put my WA code below.

[cpp]
#include <stdio.h>
#include <string.h>
#define MAX 10000
#define max 100

#define _MAX_SIZE 101
#define BIGNUM

#ifndef stdio
#include <stdio.h>
#endif

#ifndef bool
#define bool int
#endif

class big
{
private:
int num[_MAX_SIZE];
public:
bool operator = (long a)
{
int i;
for(i=0;i<_MAX_SIZE;i++)
{
num=a%10;
a=a/10;
}
return 1;
}
big operator + (big a)
{
int i;
big tmp;
for(i=0;i<_MAX_SIZE;i++)
tmp.num=tmp.num+num+a.num;
for(i=0;i<_MAX_SIZE-1;i++)
{
tmp.num[i+1]=tmp.num[i+1]+tmp.num/10;
tmp.num=tmp.num%10;
}
return tmp;
};
big operator + (int a)
{
int i;
big tmp;
for(i=0;i<_MAX_SIZE;i++)
{
tmp.num=num+a%10;
a=a/10;
a=a+tmp.num[i]/10;
tmp.num[i]=tmp.num[i]%10;
if(a==0)
break;
}
return tmp;
};
big()
{
int i;
for(i=0;i<_MAX_SIZE;i++)
num[i]=0;
};
void print()
{
int i;
for(i=_MAX_SIZE-1;i>=0;i--)
if(num[i]!=0)
break;
if(i==-1)
printf("0");
for(;i>=0;i--)
printf("%d",num[i]);
}
};

big now[MAX];
big next[MAX];
char word[MAX+1];
char com[max+1];

void main()
{
int i,j,k;
int num;
int len1,len2;
scanf("%d",&num);
for(k=0;k<num;k++)
{
scanf("%s",&word);
scanf("%s",&com);
len1=strlen(word);
len2=strlen(com);
for(i=0;i<len1;i++)
{
now[i]=0;
next[i]=0;
}
for(i=0;i<len1;i++)
{
if(word[i]==com[0])
{
if(i==0)
now[i]=1;
else
now[i]=now[i-1]+1;
}
else
{
if(i==0)
now[i]=0;
else
now[i]=now[i-1];
}
}
for(i=1;i<len2;i++)
{
for(j=0;j<i;j++)
next[j]=0;
for(;j<len1;j++)
{
if(word[j]==com[i])
next[j]=now[j-1]+next[j-1];
else
next[j]=next[j-1];
}
memmove(now,next,sizeof(big)*MAX);
}
now[len1-1].print();
printf("\n");
}
}
[/cpp]

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

### 10069 why TLE || run time error

i don't know why my code gets tle or runtime error.
i just check all the combination and print the number.
2 avoid tle i set some condition ,but then got runtime error.
i don't know why.
need some sample input .
cuii e

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

### 10069 Distinct Subsequences

it looked simple, but getting WA . is there any input with null string or any thing special?
Rakeb

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
I was also getting WA in this problem, the cause was I used LONG LONG. but it is not enough to hold the result, then I used array to hold the result and got AC.

Hope this will help.
Where's the "Any" key?

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

### 10069 Distinct Subsequences I/O's please!!!

Please someone give me some valid big inputs for this problem because I'm getting RTE (invalid memory reference) no matter what I do, I'm solving it with DP and bigIntegers, the size of the array to represent each big Integer is 1000.

By the way what's the output for this input ?

Code: Select all

``````aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
``````
I got ...

Code: Select all

``````92045125813734238026462263037378063990076729140
``````

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
you ought be checking array bounds rather than I/O but anyway here are a couple of inputs. the ouptut for the one above is correct
Input:

Code: Select all

``````2

abcdefghijklmnopqrstuvwxyz

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa``````
Output :

Code: Select all

``````66400000000000000000000000000
19742748621859838806445290867590842097270339314978449118678002674641952503075171748033908989976400``````

remove the '\''s at the end
if u can think of it .. u can do it in software.

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:
It stopped giving me RTE but .. now I'm getting WA,

It passed the first input ... but the second I'm not sure how is it...
could you write it again ?

it suppoused that it was like this ....

Code: Select all

``````2
abcdefghijklmnopqrstuvwxyz
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
``````
And my program's output was ...

Code: Select all

``````66400000000000000000000000000
133677297192373932974692936003347684353208084884996763050657769696938808876594422224288
``````
Thanks for the help !

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

### I got Accepted thanks for the help!

hi there, thanks for the help I had a stupid mistake in my code, just corrected and got accepted ...
thanks again.

happy coding.

Yaron Wittenstein
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

Code: Select all

``````
#include <stdio.h>
#include <string.h>

#define MMAX 100    /* max size of Z */
#define NMAX 10000  /* max size of X */

#define MAXSIZE 100 /* max size of bignum* */

char Z[MMAX + 1];
char X[NMAX + 1];

unsigned int zlen;
unsigned int xlen;

typedef struct {
char digit[MAXSIZE];
unsigned int digitNum;
} bignum;

bignum A[2][NMAX + 1];

void zero_num(bignum* num)
{
num->digit[0] = 0;
num->digitNum = 1;
}

void copy_num(bignum* dst, bignum* src)
{
unsigned int i;
dst->digitNum = src->digitNum;
for(i = 0; i < src->digitNum; i++) {
dst->digit[i] = src->digit[i];
}
}

void set(bignum* a, unsigned int num) /* a = num */
{
a->digitNum = 0;
while (num != 0) {
a->digit[a->digitNum] = num % 10;
a->digitNum++;
num /= 10;
}
}

bignum* min_num(bignum* a, bignum* b)
{
return (a->digitNum < b->digitNum ? a : b);
}

bignum* max_num(bignum* a, bignum* b)
{
return (a->digitNum > b->digitNum ? a : b);
}

void add(bignum* a, bignum* b, bignum* c) /* c = a + b */
{
bignum* min = min_num(a, b);
bignum* max = max_num(a, b);
unsigned int i;
char carry = 0;
c->digitNum = max->digitNum;
zero_num(c);

for(i = 0; i < min->digitNum; i++) {
char t = a->digit[i] + b->digit[i] + carry;
c->digit[i] = t % 10;
c->digit[i + 1] = carry = (t / 10);
}

for( ; i < max->digitNum; i++) {
char t = max->digit[i] + carry;
c->digit[i] = t % 10;
c->digit[i + 1] = carry = (t / 10);
}

if (carry) {
c->digit[i] = 1;
c->digitNum++;
}
}

void print_num(bignum* a)
{
int i;
for(i = (a->digitNum) - 1; i >= 0; i--) {
printf("%c", a->digit[i] + '0');
}
printf("\n");
}

void solve()
{
unsigned int i, j, k, count;

zlen = strlen(Z);
xlen = strlen(X);

zero_num(&(A[0][0]));
count = 0;
for(i = 0; i < xlen; i++) {
if (Z[0] == X[i]) {
count++;
set(&(A[0][i + 1]), count);

}
else {
copy_num(&(A[0][i + 1]), &(A[0][i]));
}
}

k = 1;
for(i = 1; i < zlen; i++) {
zero_num(&(A[k][i]));
for(j = i; j < xlen; j++) {
if (Z[i] == X[j])  {
add(&(A[k][j]), &(A[1 - k][j]), &(A[k][j + 1]));
}
else {
copy_num(&(A[k][j + 1]), &(A[k][j]));
}
}
k = 1 - k;
}

print_num(&(A[1 - k][xlen]));
}

int main()
{
int case_num;
scanf("%d", &case_num);
while (case_num--) {
scanf("%s", X);
scanf("%s", Z);
solve();
}
}

``````
i have no idea whats the problem! please please try to help me here!!!!!!!!!!!

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
you could try a couple of inputs given here :
http://online-judge.uva.es/board/viewto ... ight=10069

if u can think of it .. u can do it in software.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
you'll never be able to check all combination, you have to do it with big integers and DP

qazxcvbn
New poster
Posts: 3
Joined: Mon Feb 06, 2006 6:41 am
what problem ????

I seem to encounter the same problem in it@@
thx!!

chuzpa
New poster
Posts: 33
Joined: Fri Jun 18, 2004 8:39 am
Location: Mexico
Contact:

### sorry

I'm not pretty sure I did this problem about 1 year and 6 months ago, if I can help you with i/o's or something please tell me.

tarzxvf
New poster
Posts: 5
Joined: Sun Apr 20, 2008 5:05 pm

### Re: 10069 - Distinct Subsequences

I have used this site to check my answers.
http://uva.xgd.dk/problemssolve.php
but still get WA again and again.
Thanks.

My code:

Code: Select all

``````#include <stdio.h>
#include <string.h>

#define X_MAXLEN 20000
#define Z_MAXLEN 100
#define BIGNUM_OVERFLOW -1

struct bignum{
unsigned char number[101];
int count;
};

void match(char *, char *, size_t, size_t);

void bignum_clear(struct bignum *);
void bignum_set(struct bignum *, int);
void bignum_copy(struct bignum *, struct bignum *);
int bignum_add(struct bignum *, struct bignum *);
void bignum_dump(struct bignum *);

struct bignum count[2][X_MAXLEN + 1];

int main()
{
int ncases, i, j;
size_t sizeX, sizeZ;
char X[X_MAXLEN + 1];
char Z[Z_MAXLEN + 1];

for(i = 0; i < X_MAXLEN + 1; i++)
bignum_clear(&count[0][i]);

scanf("%d", &ncases);
getchar();

while(ncases--){
fgets(X, sizeof(char) * (X_MAXLEN + 1), stdin);
fgets(Z, sizeof(char) * (Z_MAXLEN + 1), stdin);
sizeX = strlen(X) - 1;
sizeZ = strlen(Z) - 1;
match(X, Z, sizeX, sizeZ);

bignum_dump(&count[sizeZ % 2][sizeX]);
printf("\n");
}

return 0;
}

void match(char *X, char *Z, size_t sizeX, size_t sizeZ)
{
int i, j, sourceindex = 0, destindex = 0;

for(j = 0; j < sizeX + 1; j++)
bignum_set(&count[0][j], 1);

for(i = 0; i < sizeZ; i++){
destindex = (destindex + 1) % 2;
bignum_clear(&count[destindex][0]);

for(j = 1; j <= sizeX; j++){
bignum_copy(&count[destindex][j], &count[destindex][j - 1]);

if(Z[i] == X[j - 1]){
}
}

sourceindex = destindex;
}
}

void bignum_clear(struct bignum *dest)
{
int i;

for(i = 0; i < 101; i++)
dest->number[i] = 0;

dest->count = 0;
}

void bignum_set(struct bignum *dest, int value)
{
bignum_clear(dest);

while(value){
dest->number[dest->count] = value % 10;
value = value / 10;
dest->count++;
}
}

void bignum_copy(struct bignum *dest, struct bignum *src)
{
int i;

bignum_clear(dest);

for(i = 0; i < src->count; i++)
dest->number[i] = src->number[i];

dest->count = src->count;
}

int bignum_add(struct bignum *dest, struct bignum *src)
{
int i, ndigits, carry = 0, sum;

if(dest->count > src->count)
ndigits = dest->count;

else
ndigits = src->count;

for(i = 0; i < ndigits && i < 101; i++){
sum = (int)(dest->number[i] + src->number[i] + carry);
carry = (sum >= 10);
dest->number[i] = sum % 10;
}

dest->count = ndigits;

if(carry){
if(i == 101){
return BIGNUM_OVERFLOW;

}else{
dest->number[dest->count] = carry;
dest->count++;
return 0;
}
}
}

void bignum_dump(struct bignum *dest)
{
int i;

if(dest->count == 0){
printf("0");

}else{
for(i = dest->count - 1; i >= 0; i--)
printf("%u", dest->number[i]);
}
}
``````
My Input:

Code: Select all

``````3
abcdefghijklmnopqrstuvwxyz
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abcdefghijklmnopqrstuvwxyz
``````
My output:

Code: Select all

``````66400000000000000000000000000
133352780953543421259359468955239189723988854631557625988982658421013199754408615273536
1562342951323509290258052709071343422775
``````

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

### Re: 10069 - Distinct Subsequences

Jagadish's first set of input caused the uvatoolkit to break.

are there any more input sets to consider? I tried all the test cases posted here and seemingly the program passed.