Dirty Path - WA


I’m trying to solve Dirty Path problem for some time…

My solution is very the same as described in editorial.

My main() starts with init() which generated good numbers - I started with fibonachi numbers and then I multiply those with each other getting all good numbers. For each good number if it’s not fibonacci number, I remember the lower good number current one was created from. So for example 1 2 3 5 8 13 are fibonacci and also good numbers, 15 is also good, because 15 = 3 * 5, so in prev[15] there is 3 or 5, but it doesn’t really matter which one of those, that way I can reconstruct, that for example 30 = 2 * 15 = 2 * 3 * 5 … From this reconstruction I’m creating the path - ...#....#...... and while we can print any of the valid paths I’m adding #. at the end (just for coding simplification).

What I tried was, that I downloaded some working Java solution, this time I liked @junior94 's (link) and tried my program whether it returns same results for some random inputs (a lot of them) - one just need to generate three numbers L, R and N and check results.

For this random tests I’m getting same Nth number as junior is printing. I assume there only two possibilities - my path is wrong or there is some corner case (which is not easy to find by random tests). According to the input also 0 0 1 is correct input - but I do not know from problem statement, what is the answer - is 0 a good number? If it is, what is the path, junior94’s solution prints 0 .#… The path checking is not easy, but probably I overlooked something.

My last submission link

The path doesn’t matter as long as the number of ways to traverse it is correct. And for 0 my first solution prints 0 .# (I checked it now) notice that there’s no way to reach the second point if it’s blocked. A valid solution could print 0 # or 0 ###… as long as the number of ways to go to the last point is 0 the solution is correct.

A good number n is a number for which there is any path that has n ways to go from the first point to the last one. 0 is a good number because # for example has 0 ways to go from the first point to the last one. 1 is also a good number because of “.”, “…#.”, etc… doesn’t really matter as long as the path is correct. Of course the shorter the path you find the faster your solution will be.

You solution works for the example case but it prints -1 for 0 0 1 (I had to resize some of your arrays but I don’t think this has changed the result). 0 0 1 is a valid input because it respects the constraints. Even if 0 wasn’t a good number it would still be a valid input. Notice that since 0 is the 1st good number and we want the 1st number in the range [0 - 0] the solution has to print 0 and some path that has 0 ways to be traversed for example #.

1 Like

I checked in it works fine with “#” for 0, so probably this was my problem - returning -1 for good number 0. Thanks :wink: