I’m trying to solve Dirty Path problem for some time…
My solution is very the same as described in editorial.
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 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.