Questions Tagged With numberhttps://inoi15.discuss.codechef.com/tags/number/?type=rssquestions tagged <span class="tag">number</span>enFri, 23 Jan 2015 20:44:03 +0530HIGHWAYBYPASS - Flaw in inductive step of solution?https://inoi15.discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solution<p>HIGHWAYBYPASS from INOI 2014.</p>
<p>The solution on the INOI Practice Server goes something like this</p>
<p>rght[r][c][x] = (rght[r][c-1][x-1] + down[r][c-1][d]);<br>
down[r][c][x] = (down[r-1][c][x-1] + rght[r-1][c][d]);</p>
<p>Where rght[r][c][x] is the number of paths to (r,c) that use at most 'x' consecutive moves in some direction (at some point in the path), and similarly for down[r][c][x].</p>
<p>But I think there is a flaw in this argument. I'll try to give a counterexample.</p>
<p>Let the starting square be (0,0). I move 4 to the right, 2 down and 2 right, ending up at (2,6).</p>
<p>This is one of the ways that corresponds to rght[2][6][4] (Since the maximum number of consecutive segments is 4). Note that this path passes through (2,5) and (2,4).</p>
<p>Now according to the inductive step of the DP solution, the number of ways to reach (2,6) from (2,5) using at most 4 segments is the number of ways to reach (2,5) from (2,4) using at most<b> 3 segments. <i> But while assuming this, the path we discussed above is omitted! </i></b></p>
<p>That path provides a way to reach (2,5) from (2,4) using <b><i>4 segments.</i></b> And it is also a way to reach (2,6) from (2,5), still using only 4 segments.</p>
<p>Please let me know whether this is compensated for elsewhere in the algorithm.</p>vikramnitin9Fri, 23 Jan 2015 20:44:03 +0530https://inoi15.discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solutionpathsprogrammingofdynamicnumberbypassinoihighway