Answers to: HIGHWAYBYPASS - 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>enSat, 24 Jan 2015 20:54:59 +0530Answer by idraumrhttps://inoi15.discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solution/62598<p>Hi,</p>
<p>So seems like <a href="/users/66051/superty"><a href="/users/66051/superty">@superty</a></a> also can't understand the solution. A bit disturbed by that, I decided to look it up. Kudos for ambiguous language, there.</p>
<p><code>right[r][c][x]</code> is the number of ways to reach <code>r, c</code>, where the last move was a right, and that contiguous sequence of right moves was at most <code>x</code> in length. Now, for a particular <code>r, c</code>, with at most <code>x</code> contiguous sequence of right moves done last, you can either come from the left cell with <code>x - 1</code> right-contiguous moves done at most, OR, you can come from the left cell with any number of down-contiguous moves. I hope that's clear---it's tough to explain, but I tried.</p>
<p>The answer simply becomes <code>down[R][C][d] + right[R][C][d]</code>.</p>
<p>Cheers.</p>idraumrSat, 24 Jan 2015 20:54:59 +0530https://inoi15.discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solution/62598Answer by vikramnitin9https://discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solution/62564<p>Thanks, that makes things a lot clearer! Just one small thing - what would be the expression for the final answer? I guess that it would be</p>
<p>right[R][C][1] + right[R][C][2] + ------ + right[R][C][K] <br>
+ down[R][C][1] + down[R][C][2] + ------ + down[R][C][K]</p>
<p>(R,C is the final intersection)</p>
<p>By the way, the INOI Practice Server Solution is definitely wrong. I tried the following input.<br>
7 3 5 <br>
1 1 1 1 1 0 0<br>
0 0 0 0 1 0 0<br>
0 0 0 0 1 1 1<br></p>
<p>Answer : 0 (not 1)</p>
<p>You can make endless similar cases, for which it gives the wrong answer. However, your solution seems to be perfect.</p>vikramnitin9Sat, 24 Jan 2015 14:26:10 +0530https://discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solution/62564Answer by idraumrhttps://discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solution/62548<p>Hi,</p>
<p>I'm afraid I didn't go through the solution on the INOI practice server. I can tell you my approach though (and it's easy to prove inductively).</p>
<p>Let <code>right[r][c][x]</code> represent the number of paths to <code>(r, c)</code>, of which the last <code>x</code> consecutive moves are in the right direction. Same for <code>down[r][c][x]</code>.</p>
<p>Now, a particular <code>right[r][c][x]</code> is simply <code>right[r][c - 1][x - 1]</code> for every <code>x >= 2</code> and <code>x <= d</code>. Same for <code>down[r][c][x]</code> with the right adjustments. For <code>right[r][c][1]</code>, you add all the ways to reach <code>(r, c - 1)</code> only with consecutive down moves. Same goes for <code>down[r][c][1]</code>.</p>
<p>Cheers,
Shikhin</p>idraumrFri, 23 Jan 2015 21:48:04 +0530https://discuss.codechef.com/questions/62542/highwaybypass-flaw-in-inductive-step-of-solution/62548