Join Us
Loading Similar Posts
Entering edit mode
Question 1
Piggy Bank
Daniel has 2 piggy banks. A bigger one and a smaller one. He has divided the bigger piggy bank in X slots and smaller piggy bank in Y slots, X > Y.
He has some money deposited in both of them. He chooses Y slots from the bigger piggy bank and transfers their money to Y slots of smaller piggy bank in respective order. He wants that the amount in slot n+1 should always be greater than or equal to that in the slot n, of the smaller piggy bank, after the transfer from the bigger piggy bank. You have to help Daniel to count the number of ways he can transfer the money.
Input Specification:
input1: Number of slots in bigger piggy bank.
input2: Number of slots in smaller piggy bank.
input3: Amounts in slots of bigger piggy bank.
input4: Amounts in slots of smaller piggy bank.
Output Specification:
Return the number of ways to transfer amount
Example 1:
input1: 5
input2: 3
input3: {1,5,2,4,7}
input4: {7,9,6}
Input Specification:
input1: Number of slots in bigger piggy bank.
input2: Number of slots in smaller piggy bank.
input3: Amounts in slots of bigger piggy bank.
input4: Amounts in slots of smaller piggy bank.
Output Specification:
Return the number of ways to transfer amount.
Example 1:
input1: 5
input2: 3
input3: {1,5,2,4,7}
input4: {7,9,6}
Output: 4
Explanation: The slots from the bigger piggy bank can be selected as {1,2,7}, {1,4,7}, {5,4,7} and {2,4,7}; ie, 4 ways to transfer the amount.
Example 2:
input1: 4
input2: 2
input3: {7,7,7,7}
input4: {3,4}
Question 2
Alex's Love for Letters
Alex had written all the 26 letters from a to z on a board initially. Later, he rearranged those letters forming a new sequence. Alex gives you this new sequence of 26 letters, another string S of length N and a number K. Your task is to find and return the lexicographically smallest subsequence of length K formed from string S, in accordance with the new sequence of letters provided to you.
Note: A subsequence of a string is formed by deleting a few (possibly 0) characters from string. Given two strings, a string will be lexicographically smaller than other string, if it comes first in the dictionary
Input Specification:
input1: A string denoting the new sequence of letters.
input2: An integer value N denoting the length of string S.
input3: An integer value K denoting the length of the subsequence which you would be required to return.
input4: The string S.
Output Specification:
Return the lexicographically smallest subsequence as per the sequence of letters in input1.
Example 1:
input1: abcdefghijklmnopqrstuvwxyz
input2:4
input3:2
input4: rfov
Output: fo
Explanation: Here, we need to form subsequences of length 2 from the given string, rfov. The possible subsequences are rf, ro, rv, fo, and so on. Considering the sequence of letters in input1, fo is lexicographically the smallest. Therefore, fo is returned as the output
Example 2:
input1: zyxwvutsrqponmlkjihgfedcba
input2: 4
input3: 2
input4: ehkx
Output: kx
Entering edit mode
Solution for Question 2
def AlexLoveLetter(input1, input2, input3, input4):
test_str = input4
K = input3
res = [test_str[i: j] for i in range(len(test_str)) for j in range(i + 1, len(test_str) + 1) if len(test_str[i:j]) == K]
res.sort()
ans=[]
for i in res:
t=[]
for k in i:
t.append(input1.find(k))
ans.append([i, t])
ans.sort(key = lambda x: x[1])
return ans[0][0]
print(AlexLoveLetter(input1, input2, input3, input4))
Entering edit mode
Solution to Question 2
We can use a simple greedy strategy here to constuct the answer string. Since, we need to choose a subsequence of length exactly k, we start building the result string from left to right by taking the minimum character such that after adding the mentioned character to out result string, it is still possible to select the remaining characters and form a subsequence of length k. So, when chossing the i-th character, we find the minimum character such that it's possibe to select k-i characters after appending the minimum character to our result string.
Code
void solve()
{
int n,k;
cin>>n>>k;
string sp,s;
cin>>sp>>s;
vector<int> pos[26];
for(int i=0;i < n;i++){
pos[s[i]-'a'].pb(i);
}
string ans="";
int tk=-1;
while(ans.length() < k){
for(int i=0;i < 26;i++){
int pl=sp[i]-'a',xt=k-ans.length();
int idx=upper_bound(all(pos[pl]),tk)-pos[pl].begin();
if(idx==pos[pl].size()) continue;
int rp=pos[pl][idx];
if(rp > tk && n-rp >= xt){
ans+=sp[i],tk=rp;;
break;
}
}
}
cout << ans;
Entering edit mode
Solution to Question 1
This can be solved using dynamic programming. We can choose a 2-d state (i,j) where dp(i,j) denotes the number of ways to form an increasing array of the first i elements in b is we add the j-th element of a to the i-th element of b. Thus, now we can only add elements whose index k is less than j and a[k]<=a[j]+b[i]-b[i-1]. So, we can calculate dp[i][j] by summing over the dp values of all indices k which satisfy the above mentioned property. However, this would take O(n^3). So, we can speed up this process by calculating the value of dp[i][j] in O(logn) time by using fenwick tree or segment tree. So, the overall complexity becomes O(n^2 * logn).
