### sandeep.gprs's blog

By sandeep.gprs, history, 4 years ago, , Hi, I have been trying hard to solve the subtask 3 (for 30 points) of the problem []( https://www.codechef.com/problems/ADDMUL)

I have implemented segment tree with lazy propogation and everything seems fine..But still getting WA. Can anyone find a test case where the solution not works or any mistake in the code? (Please keep in mind that the solution is targeted for Subtask 3 only i.e queries of type 3 will not be there).

My solution goes here https://www.codechef.com/viewsolution/10636427 By sandeep.gprs, history, 4 years ago, , # Printing all the ways to transform S to T.

Recently in a Technical Interview,I was asked this question.. Given a String S and another string T,You have to change S to T using following steps only - You can push a character from S to the stack and pop an element from the stack...

Now if a push operation is denoted by 0 and pop is denoted by 1, generate all possible valid strings that can transform S to T.

Given that transformation will always be possible and |S| = |T| <= 15.

For Ex - S = "MADAM" T = "ADAMM" The steps to convert will be - push M (0) push A (0) pop A (1) push D (0) pop D (1) push A (0) pop A (1) push M (0) pop M (1) pop M (1)

So "0010101011" is a valid string,I need to generate all the valid strings.. All i can come up with was this code,which was able to generate a single valid string..Can anyone help me out in how to generate each valid string. (Note: Bitmasking approach is not allowed)

Printing all the ways to transform S to T.
==========================================
Recently in an Interview,I was asked this question..
Given a String S and another string T,You have to change S to T using following steps only -
You can push a character from S to the stack and pop an element from the stack...

Now if a push operation is denoted by 0 and pop is denoted by 1,
generate all possible valid strings that can transform S to T.

Given that transformation will always be possible and |S| = |T| <= 15.

For Ex -
The steps to convert will be -
push M (0)
push A (0)
pop A  (1)
push D  (0)
pop D   (1)
push A  (0)
pop A    (1)
push M   (0)
pop M   (1)
pop M   (1)

So "0010101011" is a valid string,I need to generate all the valid strings..
All i can come up with was this code,which was able to generate a single valid string..Can anyone help me out in how to generate each valid string.
(Note: Bitmasking approach is not allowed)

#include<bits/stdc++.h>
using namespace std;
// i -> upto what position in S we are done
// j -> upto what position in T we have completed
// o for push
//1 for pop
bool temp = {0};
stack<char> st;
int l = 0,k = 0;

void solve(string& S,string& T,int i,int j)
{
if(k == 2*l - 1)
{
for(int i = 0;i <= k;i++)
cout << temp[i] << " ";
cout << endl;
return ;
}

if(i < 0	||	j < 0	||	i > l ||	j > l)
return;
if(st.size())
if(T[j] == st.top())
{
st.pop();
temp[k++] = 1;
solve(S,T,i,j + 1);
k -= 1;
}

if(T[j] == S[i])			// Both current charcters matches each other
{
st.push(S[i]);
temp[k++] = 0;
st.pop();
temp[k++] = 1;
solve(S,T,i+1,j+1);
k -= 2;
}

if(T[j] != S[i])
{
// Keep pushing characters from S,and increase i until they do not matches
st.push(S[i]);
temp[k++] = 0;
solve(S,T,i+1,j);
k -= 1;

}

}

int main()
{
ios_base::sync_with_stdio(0);
string S,T;
cin >> S;
cin >> T;
//	cout << st.top();
l = S.length();
solve(S,T,0,0);
return 0;
}



I am new to codeforces,sorry if i have done some terrible formatting :| 