z-board

I would like to know in wich test cases and why my code failed

i didn't solve the task so i don't know how you solved it, but if you were calculating the number of possibilities to go from 0,0 to r,c then this number was to big to put it in 64bit int

There is no need to calculate exact amount of ways we can get to a square as long as we know that the value is bigger than k, and instead or percise numbers we could just store 1E9 for example. Or maybe there is something I haven't considered, as there are two cases my solution fails. Maybe someone with 100 points could share ideas?

Check situations where first or last cell contain '#'. That's where my solution kept failing.

Yes, that was the case. I hadn't considered the situation where the end point was '#'.

But in addition i would like to criticise the tests a bit. Because of the mistake described above I failed 3 test cases. Friend of mine submitting the same solution but using long long and percise value calculation only failed one more test - because of the time limit. I think there should have been some test cases involving the amount of ways to go from one square to another exceeding 64bit limits, where the assumption of not calculating exact values would have been sufficient. In addition, for a nxn board with no '#' these values considerably big very soon - for about n = 40 they become too big to for 64bit. So it would have been just natural to have about 10 to 20% of tests having such values as n, m <= 500. But in reality there were none and people with actually wrong solutions could have got 100/100 points.

But the problem itself I liked very much. Thank you for that.

What do you think when you say "actually wrong solutions"? There are at least 10 test cases where number of possible paths doesn't fit in 64bit. Ordinary number of path that should be found is given by constraints, so simply, that is just part of the problem.

Test case where you have failed I have generated manually, so I was thinking about such situation, but didn't want to add to many them.

EDIT: Can you send me a link of "wrong solution", please? Thanks.

http://www.z-trening.com/new/www/html/submit.php?submit=7100028910&subm_stat=1

As you see this solution failed the 3 tests that had '#' at the end point and exceeded time limit at one (I guess because of 64bit processing). Therefore I do not see any mistakes occured because of exceeding 64bit. Could it be a coincidence and the incorrect values remained "correct" (I mean, they produced correct answers to "<=" etc) where they were checked?

On another note, why are there so many test cases with answer "impossible"? You could have gotten 42 / 100 points during the competition by just printing "impossible". :D

See frost_nova's results for an example:
http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100028461

On a related note, you might notice that tjhance's results are the exact opposite:
http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100028749
He printed "IMPOSSIBLE" instead of "impossible". :(

@n.vilcins: I am not sure why his solution passes some test cases when it overflow unsigned long long. There are test cases for which number of possible paths is very large, if you want I can share them with you?

@neal_wu: Well, I have generated more test cases then usual and I have decided to make about 20 of them to contain impossible. Some of them were kind of tricky, some manually generated and some randomly generated, so in total about 20 of them :)

Well actually it might have passed the 64bit overflow tests. As mentioned before, the thing that matters is whether the value is bigger than k and no need to be percise if so, and while suming many very huge numbers they produce wrong, but anyway large number, therefore that caused no problems. I guess many results would have been wrong if 32bit was used instead of 64bit.

Changing constraints to something like k <= 1E18 or even more (approximately 2^64 / 2) could totally change the scene.