Answers to: ASTRING - Editorialhttps://discuss.codechef.com/questions/81637/astring-editorial<h1>PROBLEM LINK</h1>
<p><a href="http://www.codechef.com/problems/ASTRING">Practice</a><br>
<a href="http://www.codechef.com/LTIME36/problems/ALOST">Contest</a><br></p>
<h1>Contributors</h1>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a><br>
<strong>Tester & Editorialist:</strong> <a href="http://www.codechef.com/users/prateekg603">Prateek Gupta</a><br></p>
<h1>DIFFICULTY:</h1>
<p>Easy </p>
<h1>PREREQUISITES:</h1>
<p>Sets, Implementation</p>
<h1>PROBLEM:</h1>
<p>Find the smallest lexicographical subsequence of length $K$ from a given string of length $N$</p>
<h1>EXPLANATION</h1>
<p><br>
<strong>Solution for Subtask 1:</strong><br>
The smallest subtask can indeed be solved by dynamic programming. Basically, you have a choice at every position of the string $S$ i.e, whether to include a character at particular position in final subsequence of $K$ characters or not. Now, let's define a DP state as $dp(i,\ j)$ denoting the smallest lexicographical subsequence of length $j$ formed from first $i$ characters of the original string $S$. Hence, the following equations hold true.
$$dp(0,\ 0)\ =\ null$$
$$dp(0,\ j)\ =\ INF\quad \forall\quad j\ \in\ (1,\ N)$$ $$dp(i,\ j)\ =\ min(\ dp(i\ -\ 1,\ j)\ ,\ s_i + dp(i\ -\ 1,\ j\ -\ 1)$$</p>
<p><br>Let's have a look at the pseudo code for the bottom up solution of the above approach.</p>
<pre><code> dp[0][0] = ""
for ( j = 1 to K ) dp[0][j] = "INF"
for ( i = 1 to N ) {
for ( j = 1 to K ) {
dp[i][j] = "INF"
if ( dp[i - 1][j] != "INF" ) dp[i][j] = dp[i - 1][j]
if ( dp[i - 1][j - 1] != "INF" ) {
if ( dp[i][j] == "INF" ) dp[i][j] = dp[i - 1][j - 1] + s[i - 1]
else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + s[i - 1])
}
}
}
print(dp[N][K])
</code></pre>
<p><br>The same thing can be implemented by recursive memoization solution. You might like to read <a href="https://tp-iiita.quora.com/Dynamic-Programming-Part-1">this</a> blog post to know more about Dynamic Programming. The time complexity for the above approach is $\mathcal{O}(N^{2})$ but the space complexity is around $\mathcal{O}(N^{3})$. Due to the higher space complexity, it won't be possible to implement the same solution for subtask 2 as it can cause memory overflow leading to Runtime Error.</p>
<p><br><strong>Solution for subtask 2:</strong><br>
The approach for this subtask is based on the fact that the subsequence formed at last has to be of length $K$ exactly. Having said that, it is not difficult to realize that the first character of the smallest lexicographical subsequence has to be from substring $s[0,\ n\ -\ k]$. Why? If the first character is not from this substring, then it would not be possible to form a subsequence of length $K$. Similarly, the $i^{th}$ character should be from the substring $s[prev\ +\ 1,\ n\ -\ k\ +\ i]$, where $prev$ is the position found for $(i - 1)^{th}$ character of the subsequence. Hence, we should always choose the smallest characters in the substrings. And in case, there are two smallest characters, we should choose the one with leftmost position, since it will give a larger substring to choose from, for the rest of the characters in the subsequence. Let us look at the pseudo code for this greedy approach.</p>
<pre><code> subseq = ""
prev_pos = -1
for ( i from 0 to k - 1 ) {
for ( j from last_pos + 1 to n - k + i ) {
if ( j == last_pos + 1 ) smallest_char = s[j], leftmost_pos = j
else if ( smallest_char > s[j] ) smallest_char = s[j], leftmost_pos = j
}
prev_pos = leftmost_pos
subseq.append(smallest_char)
}
print(subseq)
</code></pre>
<p>Since, for all $K$ characters of the subsequence, it traverses the whole string in the worst case to find the smallest character, the time complexity for this pseudo code is $\mathcal{O}(N*K)$. But, this does not yet suffice to pass all the input files.</p>
<p><br><strong>Solution for subtask 3:</strong><br>
The logical approach for the problem remains the same as mentioned in the subtask $2$. But, the implementation can be optimized to reduce the overall time complexity. For this, we can maintain a data structure that will give the smallest character in a range and in case, there are several smaller characters, it can give us the position of the leftmost smallest character in that range. The data structure which seems most easier ti implement at this stage is a $set$ of pairs. Hence, the pairs of (characters, indexes) will be inserted into the set when required and removed when they go outside the current range. The first element of the set will give us the required character and it's corresponding index for that particular position. Let's denote $pos[x]$ as the index where the $x^{th}$ character of the $K$-length subsequence was found. <br><br>
To calculate the $pos[i]$, the range that to be considered will be $(pos[i\ -\ 1]\ +\ 1,\ n\ -\ k\ +\ i)$. Hence, the pairs within the range $(pos[i\ -\ 2]\ +\ 1,\ pos[i\ -\ 1])$ are removed and a new pair of $(s_{n\ -\ k\ +\ i},\ n\ -\ k\ +\ i)$ should be inserted into the set. This would allow you to remove and insert each pair exactly once. Let us now have a look at the pseudo code for the same.</p>
<pre><code> for ( i = 0 to n - k ) Set.insert(make_pair(s[i], i))
subseq.append(Set.top().character)
a = 0, b = Set.top().index
for (i = n - k + 1 to n - 1 ) {
while ( a <= b ) Set.erase(make_pair(s[a], a)), a++
Set.insert(make_pair(s[i], i))
b = Set.top().second
subseq.append(Set.top().character)
}
print(subseq)
</code></pre>
<p>For more details on the implementation of any subtasks, have a look at the tester's solution.</p>
<h1>COMPLEXITY</h1>
<p>The overall complexity necessary to pass all the input files should be $\mathcal{O}(N*logN)$.</p>
<h1>SOLUTIONS</h1>
<p><a href="http://www.codechef.com/download/Solutions/LTIME36/Setter/ASTRING.cpp">Setter</a><br>
<a href="http://www.codechef.com/download/Solutions/LTIME36/Tester/ASTRING_subtask1.cpp">Tester's solution to Subtask 1</a><br>
<a href="http://www.codechef.com/download/Solutions/LTIME36/Tester/ASTRING_subtask2.cpp">Tester's solution to Subtask 2</a><br>
<a href="http://www.codechef.com/download/Solutions/LTIME36/Tester/ASTRING_subtask3.cpp">Tester's solution to Subtask 3</a> </p>enMon, 03 Sep 2018 15:43:49 +0530Answer by adityamittal25https://discuss.codechef.com/questions/81637/astring-editorial/134817<p>I just sorted the string and took the substring from 0 to k. But it shows wrong answer. Can someone please highlight the mistake in my code.</p>
<p>int main()
{</p>
<pre><code>int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int k;
cin>>k;
sort(s.begin(),s.end());
string s1=s.substr(0,k);
cout<<s1<<endl;
}
</code></pre>
<p>}</p>adityamittal25Mon, 03 Sep 2018 15:43:49 +0530https://discuss.codechef.com/questions/81637/astring-editorial/134817Answer by sreeram14https://discuss.codechef.com/questions/81637/astring-editorial/122378<p>int main()
{char a[100005],b[100005];
int t,i,m;
scanf("%d",&t);
for(m=0;m<t;m++) {int="" k,len;="" scanf("%s",a);="" scanf("%d",&k);="" len="strlen(a);" int="" p="len-k;" int="" j="0;" for(i="0;i&lt;len;i++)" {="" while(j!="0" &&="" b[j-1]="">a[i] && p!=0)
{
j--;
p--;
}
b[j]=a[i];
j++;
}
b[k]='\0';
printf("%s\n",b);</p>
<pre><code>}
return 0;
}
</code></pre>sreeram14Thu, 01 Feb 2018 11:04:39 +0530https://discuss.codechef.com/questions/81637/astring-editorial/122378Comment by debjitdj on debjitdj's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81818<p>You have to update $prev$ correctly. I have edited (only one small change) your code, check it here-</p>
<p><a href="https://www.codechef.com/viewsolution/10252513">https://www.codechef.com/viewsolution/10252513</a></p>debjitdjTue, 31 May 2016 17:11:45 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81818Comment by anviv on debjitdj's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81817<p><a href="https://discuss.codechef.com/questions/81637/astring-editorial/81765">my solution is exact same as yours but that is giving only 30 points after submition. please check my solution.
</a><a href="https://www.codechef.com/viewsolution/10207113">https://www.codechef.com/viewsolution/10207113</a></p>anvivTue, 31 May 2016 16:19:16 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81817Answer by stellar97https://discuss.codechef.com/questions/81637/astring-editorial/81809<p>I too solved it using segment trees. First idea that came to my mind was using RMQ. Here's my solution <a href="https://www.codechef.com/viewsolution/10243834">https://www.codechef.com/viewsolution/10243834</a></p>stellar97Mon, 30 May 2016 23:45:04 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81809Comment by c1_6 on shubham_43's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81806<p>Same here - <a href="https://www.codechef.com/viewsolution/10206467">https://www.codechef.com/viewsolution/10206467</a></p>c1_6Mon, 30 May 2016 20:35:15 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81806Comment by debjitdj on debjitdj's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81805<p>Sorry, that's a typo...I meant to say $O(N^2)$</p>debjitdjMon, 30 May 2016 20:26:54 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81805Comment by code_hard123 on debjitdj's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81804<p>no its not O(N)</p>
<p>Consider case when : K = N / 2
It goes O(N * N)</p>code_hard123Mon, 30 May 2016 19:05:29 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81804Comment by debjitdj on debjitdj's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81791<p>It is actually $O( K*(N-K+1) )$ which is approximately $O(N)$</p>debjitdjMon, 30 May 2016 04:57:00 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81791Comment by geek_geek on debjitdj's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81782<p>complexity?</p>geek_geekSun, 29 May 2016 18:08:38 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81782Comment by prateekg603 on peluche's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81771<p>Since, you are storing a string at each dp[i][j], basically you are storing another array of characters in a 2D array. Hence, the space complexity is O(N^3).</p>prateekg603Sun, 29 May 2016 09:23:26 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81771Answer by debjitdjhttps://discuss.codechef.com/questions/81637/astring-editorial/81765<p><a href="https://www.codechef.com/viewsolution/10206440">https://www.codechef.com/viewsolution/10206440</a></p>
<p>Here is what I did. Just searched for the best possible element of the substring from left to right.</p>debjitdjSun, 29 May 2016 02:00:16 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81765Answer by peluchehttps://discuss.codechef.com/questions/81637/astring-editorial/81762<blockquote>
<p>"[...] The time complexity for the
above approach is O(N^2) but the space
complexity is around O(N^3). [...]"</p>
</blockquote>
<p>I do not understand this statement, how can the space complexity ever be bigger than the time complexity, how would you generate O(n) memory in O(1) time ?</p>pelucheSun, 29 May 2016 01:32:12 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81762Answer by gannu_rajhttps://discuss.codechef.com/questions/81637/astring-editorial/81758<p>We can do it by using stack overall complexity O(n).My Solution link : <a href="https://www.codechef.com/viewsolution/10214056">https://www.codechef.com/viewsolution/10214056</a></p>gannu_rajSun, 29 May 2016 00:51:22 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81758Answer by anmol137dh08https://discuss.codechef.com/questions/81637/astring-editorial/81754<p>Can anyone explain what's wrong with my code or any tricky test case?
<a href="https://www.codechef.com/viewsolution/10212069">my code</a></p>anmol137dh08Sat, 28 May 2016 23:29:17 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81754Answer by shubham_43https://discuss.codechef.com/questions/81637/astring-editorial/81752<p>Even the O(N*K) algorithm with pruning worked for all test cases.
Code in C : <a href="https://www.codechef.com/viewsolution/10209119">https://www.codechef.com/viewsolution/10209119</a></p>shubham_43Sat, 28 May 2016 23:18:02 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81752Answer by rachitjainhttps://discuss.codechef.com/questions/81637/astring-editorial/81750<p>I also first implemented using segment tree but got TLE. Then I finally got AC using sparse table with O(NlogN) space and O(1) per query.
<a href="https://www.codechef.com/viewsolution/10207906">Click here to see the solution</a></p>rachitjainSat, 28 May 2016 22:47:46 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81750Answer by sk1sk09_3134https://discuss.codechef.com/questions/81637/astring-editorial/81749<p>I did it by greedy implementation with worst case complexity O(N*26).</p>
<p>Here is the link to my solution: <a href="https://www.codechef.com/viewsolution/10207247">https://www.codechef.com/viewsolution/10207247</a></p>sk1sk09_3134Sat, 28 May 2016 22:44:25 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81749Comment by anupam_datta on geek_geek's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81747<p><a href="https://www.codechef.com/viewsolution/10208562">https://www.codechef.com/viewsolution/10208562</a></p>
<p>my this soln passed... i thought of using segment tree had it failed....</p>anupam_dattaSat, 28 May 2016 22:40:12 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81747Comment by amitpandeykgp on geek_geek's answerhttps://discuss.codechef.com/questions/81637/astring-editorial#81746<p>Yes, but that would be too much for this problem. :P</p>amitpandeykgpSat, 28 May 2016 22:38:18 +0530https://discuss.codechef.com/questions/81637/astring-editorial#81746Answer by geek_geekhttps://discuss.codechef.com/questions/81637/astring-editorial/81745<p>We can also use a segment tree to find the position and smallest character in the string in the required range</p>
<p>Code in C++ : <a href="https://www.codechef.com/viewsolution/10207142">https://www.codechef.com/viewsolution/10207142</a></p>geek_geekSat, 28 May 2016 22:37:07 +0530https://discuss.codechef.com/questions/81637/astring-editorial/81745