HIGHWAYBYPASS - Flaw in inductive step of solution?

general
, , , , , , ,
1

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.

2

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

3

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

right[R][C][1] + right[R][C][2] + ------ + right[R][C][K]

  • down[R][C][1] + down[R][C][2] + ------ + down[R][C][K]

(R,C is the final intersection)

By the way, the INOI Practice Server Solution is definitely wrong. I tried the following input.

7 3 5

1 1 1 1 1 0 0

0 0 0 0 1 0 0

0 0 0 0 1 1 1

Answer : 0 (not 1)

You can make endless similar cases, for which it gives the wrong answer. However, your solution seems to be perfect.

4

I think the INOI solution is correct, and your testcase is wrong. The first input should be the number of rows, and the second should be the number of columns. In your testcase, the number of columns is before the number of rows.

5

Indeed, that’d be the answer. Look at what @sampritipanda said, though.

6

The INOI solution does indeed give the correct answer if you give the input correctly. I still don’t get how their solution works though.

7

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.

1 Like
8

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)

9

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!

10

I wouldn’t say medals not mattering is naive, maybe ‘carefree’ is a better word.

11

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).

12

I’m not sure about that, I tried the INOI solution and it returned 1 as expected.

13

Yeah, I said that it was correct. (1 is the correct answer)

14

Oh never mind, I must have read your comment wrong!

15

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?

16

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.

17

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.

1 Like
18

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.

19

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.

20

Hey @superty You were right. That was the only mistake I had made! Thank you!

1 Like