### R.A.N.K.A.'s blog

By R.A.N.K.A., history, 14 months ago,

Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , with the exception that she cannot move left from point 0 or right from point n. In other words, if Jamie is standing at point i,she can move to either i-1 or i+1 as long as her destination exists in the inclusive range [0,n]. She has a string ,s , of movement instruction consisting of the letters 1 and r , where 1 is an instruction to move one step left and r is an instruction to move one step right. Jamie followed the instructions in s one by one and in order .For Example if s=‘rrlr’,she performs the following sequence of moves :one step right ->one step right ->one step left -> one step right .Jamie wants to move from point x to point y following some subsequence of string s instruction and wonders how many distinct possible subsequence of string s will get her from point x to point y. recall that a subsequence of a string is obtained by deleting zero or more characters from string .

it has four parameters A String , s giving a sequence of eduction using the characters l( i.e. move left one unit ) and r (i.e. move right one unit) An integer n, denoting the length of the number line. An integer x, denoting jamie’s starting point on the number line An integer y , denoting Jamie’s enidng point on the number line. The function must return an integer denoting the total number of distinct subsequence of string s that will lead Jamie from point x to point y as this value cab be quite large .

Sample Input rrlrlr 6 1 2

out put =7

r
rrl
rlr
lrr
rrlrl
rlrlr
rrllr



• +8

 » 14 months ago, # |   +8 Auto comment: topic has been updated by R.A.N.K.A. (previous revision, new revision, compare).
 » 14 months ago, # |   0 If the constraints allow, you can do a knapsack-style dp considering r to be +1, and l to be -1, and also adding the boundary conditions.
•  » » 6 weeks ago, # ^ |   0 you will be counting repititions that way.
 » 14 months ago, # |   0 Can you give link to submit the solution?
 » 14 months ago, # | ← Rev. 4 →   0 This Problem Can be solved using dphere is my solution :- Code#include using namespace std; #define mod 1000000007 int dp[1001][2501][2]; int solveUtil( string moves, int n, int start, int end, int idx, bool flag ){ if(start < 0 || start >n ) return 0; if(start == end && idx == moves.size() ) return 1; if(idx>= moves.size()) return 0; int &ans=dp[idx][start][flag]; if(ans!=-1) return ans; ans=0; if( (moves[idx] == 'l' && flag) || (moves[idx] == 'r' && !flag) ) { int change = moves[idx] == 'l' ? -1 : 1; int x=solveUtil( moves, n, start+change, end, idx+1, flag ); int y=solveUtil( moves, n, start+change, end, idx+1, !flag ); ans=(x+y)%mod; } else ans = solveUtil( moves, n, start, end, idx+1, flag ); return ans; } int solve( string moves, int n, int start, int end ){ memset(dp,-1,sizeof(dp)); return solveUtil( moves, n, start, end, 0, false ) + solveUtil( moves, n, start, end, 0, true ); } int main() { string step; cin >> step; int n,s,e; cin >> n >> s >> e; cout << solve( step, n, s, e ) << endl; return 0; } 
•  » » 14 months ago, # ^ |   -13 Hide your code under a spoiler or give link to your code, thought a orange would know better
•  » » 3 months ago, # ^ |   0 Hi, thanks for this solution, can you explain how you are using flag here to avoid duplicates? I spent a lot of time on this yet I am still finding it hard to understand.
•  » » 3 months ago, # ^ |   0 yranka309 what does the flag mean here? please explain.
 » 14 months ago, # | ← Rev. 2 →   +3 A simple DP would work. Code#include using namespace std; const int mod = 1e9 + 7; int main() { string s; int N, from, to; cin >> s >> N >> from >> to; int n = s.length(); vector nxtl(n, -1), nxtr(n, -1); int lastl = -1, lastr = -1; for (int i = n - 1; i >= 0; i--) { if (s[i] == 'l') lastl = i; else lastr = i; nxtl[i] = lastl; nxtr[i] = lastr; } vector> dp(n + 1, vector(N + 1)); dp[0][from] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j <= N; j++) { if (j + 1 <= N and nxtr[i] != -1) { dp[nxtr[i] + 1][j + 1] += dp[i][j]; dp[nxtr[i] + 1][j + 1] %= mod; } if (j - 1 >= 0 and nxtl[i] != -1) { dp[nxtl[i] + 1][j - 1] += dp[i][j]; dp[nxtl[i] + 1][j - 1] %= mod; } } } int ans = 0; for (int i = 0; i <= n; i++) { ans += dp[i][to]; ans %= mod; } cout << ans << endl; return 0; }