Answers to: Help needed with this Dynamic Programming Questionhttps://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-question<p>I am preparing for INOI and am stuck on this problem here: <a href="http://acm.timus.ru/problem.aspx?space=1&num=1081">http://acm.timus.ru/problem.aspx?space=1&num=1081</a></p>
<p>I am just a beginner with DP so I am not getting any idea on how we will solve this question. Can anyone explain me the proper logic of the solution to this problem instead of just giving the code?</p>enTue, 06 Jan 2015 13:57:23 +0530Comment by idraumr on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-question#60889<p><a href="/users/51798/ketanhwr">@ketanhwr</a> -- proper enough?</p>idraumrTue, 06 Jan 2015 13:57:23 +0530https://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-question#60889Comment by ketanhwr on idraumr's answerhttps://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-question#60887<p>I need a proper explanation but thanks!</p>ketanhwrTue, 06 Jan 2015 13:20:30 +0530https://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-question#60887Answer by idraumrhttps://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-question/60884<p>Hi,</p>
<p>(Let's call the least significant element to be element number 0.) </p>
<p>For each element, starting with element number 0, you can calculate the number of sequences starting from there, that begin with a 0, and those that begin with a 1. Basically, <code>sequences_starting_with_zero[i] = sequences_starting_with_zero[i - 1] + sequences_starting_with_one[i - 1]</code>, and <code>sequences_starting_with_one[i] = sequences_starting_with_zero[i - 1]</code>. Do note that the starting condition is <code>sequences_starting_with_one[0] = sequences_starting_with_zero[0] = 1</code>.</p>
<p>Once you've such a table, calculating the <code>K</code>th sequence should be simple. For starters, if <code>K > sequences_starting_with_zero[N - 1] + sequences_starting_with_one[N - 1]</code>, then you can't form the required lexicographical order. If you can form one, then, in a loop starting from the most significant element, if <code>K > sequences_starting_with_zero[i]</code>, you output a <code>1</code>, subtract <code>sequences_starting_with_zero[i]</code>, and move further on. Else you output a <code>0</code>, and move further on.</p>
<p>Cheers!</p>idraumrTue, 06 Jan 2015 13:17:16 +0530https://inoi15.discuss.codechef.com/questions/60875/help-needed-with-this-dynamic-programming-question/60884