StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POCodechef: Longest Weird Subsequence
text
Body
copied!<p>The question can be found at <a href="http://www.codechef.com/MARCH12/problems/LWS/" rel="nofollow">http://www.codechef.com/MARCH12/problems/LWS/</a></p> <p>This problem can be solved using dynamic programming. The trick to this problem was to come up with a good dp state. We can make use of the fact that the only allowed characters in the input string S[1..n] are the lowercase Latin letters i.e. 'a' – 'z'. Thus, the distinct number of characters that can appear cannot be greater than 26. </p> <p>Hence we come up with the following dp state: dp[k][c1][c2] = length of the LWS for the substring S[1..k] such that the non-decreasing subsequence ends with c1 and the non-increasing subsequence ends with c2. Once we have decided the state, we can easily come up with the following recurrence: To calculate dp[k][c1][c2] we try to add the lowercase letter S[k] to either non-increasing subsequence or non-decreasing subsequence or we do not add it to any of them. </p> <p>Thus, if c1<=S[k]: dp[k][S[k]][c2] = max(dp[k][S[k]][c2], dp[k-1][c1][c2]+1) and similarly if c2>=S[k] dp[k][c1][S[k]] = max(dp[k][c1][S[k]], dp[k-1][c1][c2]+1) The final answer can be found out by iterating over c1 and c2 and finding the maximum value out of all dp[n][c1][c2]. We can see that we have to calculate 26 * 26 states for every possible length of a substring from 1 to n where n is the length of the string. Thus, the order of the solution is O(26*26*n).</p> <p>However, am in a fix when we need to solve it for when the elements in the list are numbers between 0 and 10^6</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload