×

# HIGHWAYBYPASS - Flaw in inductive step of solution?

 0 HIGHWAYBYPASS from INOI 2014. The solution on the INOI Practice Server goes something like this rght[r][c][x] = (rght[r][c-1][x-1] + down[r][c-1][d]); down[r][c][x] = (down[r-1][c][x-1] + rght[r-1][c][d]); 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]. But I think there is a flaw in this argument. I'll try to give a counterexample. Let the starting square be (0,0). I move 4 to the right, 2 down and 2 right, ending up at (2,6). 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). 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 3 segments. But while assuming this, the path we discussed above is omitted! That path provides a way to reach (2,5) from (2,4) using 4 segments. And it is also a way to reach (2,6) from (2,5), still using only 4 segments. Please let me know whether this is compensated for elsewhere in the algorithm. asked 23 Jan '15, 20:44 13●1●3 accept rate: 0%

 1 Hi, So seems like @superty also can't understand the solution. A bit disturbed by that, I decided to look it up. Kudos for ambiguous language, there. right[r][c][x] is the number of ways to reach r, c, where the last move was a right, and that contiguous sequence of right moves was at most x in length. Now, for a particular r, c, with at most x contiguous sequence of right moves done last, you can either come from the left cell with x - 1 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. The answer simply becomes down[R][C][d] + right[R][C][d]. Cheers. answered 24 Jan '15, 20:54 0★idraumr 246●3 accept rate: 45% Thanks for your help. Just curious, you don't seem to have participated in competitive programming anywhere. Do you go under a different username or do you just not do any contests? Edit: Other than the one topcoder SRM you did (I think) (24 Jan '15, 21:09) superty3★ I've been programming for quite some while, but never really understood the motivation behind competitive programming. Well, now I'm a bit older and medals somewhat matter to me more than my naive young self, so... But, no, I don't do any contests. I usually go by 'idraumr' or 'shikhin' everywhere. Cheers! Edit: Haha, yes. I joined it, but never bothered completing it. Let me wipe that off my record! (24 Jan '15, 21:14) idraumr0★ I wouldn't say medals not mattering is naive, maybe 'carefree' is a better word. (24 Jan '15, 21:15) superty3★ Indeed. I'm still carefree, but now there's additional pressure from peers and family (eh, re-read; I meant that for a general approach to life, my peers/family don't really care about IOI medals). (24 Jan '15, 21:17) idraumr0★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×933
×385
×154
×84
×55
×2
×1
×1

question asked: 23 Jan '15, 20:44

question was seen: 3,184 times

last updated: 29 Jan '15, 20:10