11081 - Strings

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

Moderator: Board moderators

New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET

I am getting WA

Post by tanaeem »

Can someone provide some large samle data?

Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm

Re: 11081 - Strings

Post by kbr_iut »

my runtime is 1.728 sec. I saw runtime like 0.152 sec in ranklist. Those who got better runtime ,can u share ur idea.
my dp is 3*N^3 with 4 recursive calls.
I think there is inclusion exclusion approach,,Have anyone found out?

thnx in advance.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

New poster
Posts: 2
Joined: Mon Oct 08, 2007 6:16 pm

Re: 11081 - Strings

Post by kevinufo »

Does anyone provide some hints about this problem?
I can't figure out the recurrence equation either in O(n^4) or O(n^3).
Any comment or example will help me a lot.

New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

Re: 11081 - Strings

Post by pdwd »

This is my solution:

Let a - first string, b - second string, c - third string.
I have dp[k][j] - number of ways to make c[1..k] using letters from a[1..i] and b[1..j]

dp[0][j] = always 1 (there is only one way to make empty string - remove all letters from a and b)

dp[k][j] = dp[k][i-1][j] + dp[k][j-1] - dp[k][i-1][j-1] //I dont take letter a, then don't take b[j] and I have to subtract common part that I added twice
if(a == c[k])
dp[k][j] += dp[k-1][i-1][j]; //I count all the ways to make c[1..k-1] and add the letter a at the end of each one
dp[k][j] -= dp[k-1][i-1][j-1] //I already added dp[k][j-1], which includes ways in dp[k-1][i-1][j-1] and also dp[k-1][i-1][j] includes dp[k-1][i-1][j-1], so they were added twice
I do something similar in case b[j] == c[k]

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11081 - Strings

Post by Jehad Uddin »

iterative dp is faster with same approach.
run time reduced to 0.256 from 1.088 sec.

A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11081 - Strings

Post by Obaida »

I used 60 x 60 x 60 x 2 Dp state and 6 recursive calls (Without Exclusion)
and my running time is .744sec :wink:
This may be the address of success.

Post Reply

Return to “Volume 110 (11000-11099)”