Hi,
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.