×

# 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★
 0 Hi, 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). Let right[r][c][x] represent the number of paths to (r, c), of which the last x consecutive moves are in the right direction. Same for down[r][c][x]. Now, a particular right[r][c][x] is simply right[r][c - 1][x - 1] for every x >= 2 and x <= d. Same for down[r][c][x] with the right adjustments. For right[r][c][1], you add all the ways to reach (r, c - 1) only with consecutive down moves. Same goes for down[r][c][1]. Cheers, Shikhin answered 23 Jan '15, 21:48 0★idraumr 246●3 accept rate: 45% https://www.dropbox.com/s/lommwt8ijplif6k/Bypass%20Highway.cpp?dl=0 The above link is an attempt at implementing of your algorithm which I have attempted. Unfortunately, it is giving an error: "Reference to right is ambiguous" and is not even compiling. I am unable to fix this error. What could be the problem in my code that is giving rise to this? (28 Jan '15, 16:48) sandy9992★ Most of the time if you get an error like this it means your name is clashing with some variable name used in some header file. This can be fixed by changing the name to, say, rght or something. (28 Jan '15, 17:31) superty3★ 1 Ohh never even thought of the possibility of 'right' clashing with a variable name in a header file. Thanks @superty @all Please don't attempt to open my code. It's too buggy and I am still working on it. (28 Jan '15, 18:53) sandy9992★ Ok, now could someone please help me understand the error in my code, as in which part is not handled correctly? 1) Consecutive segments part 2) Holes part 3) Number of paths mod part (overflow) 4)Initialization of down and rght array elements to 0 etc. I have edited the code in the same link posted in my previous comment. (29 Jan '15, 15:54) sandy9992★ I've only glanced at your code, so I might have missed something else as well. You need to take mod at every stage, in all the loops. Not just at the end. (29 Jan '15, 18:33) superty3★ 1 Hey @superty You were right. That was the only mistake I had made! Thank you! (29 Jan '15, 20:10) sandy9992★ showing 5 of 6 show all
 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:

×916
×380
×145
×84
×54
×2
×1
×1

question asked: 23 Jan '15, 20:44

question was seen: 3,109 times

last updated: 29 Jan '15, 20:10