Sort 6 Discussions, By:
Please Login in order to post a comment
isn't this chalenge more about finding the good mathematic formula than a real programming chalenge ? :/
i also nearly wanted to quit.
Then i started to analyse with spreadsheet how numbers (count of paths) evolve using a simple, but slow solution just adding step by step, when adding n by n and m by m and how this relates to number of turns.
And then i got functions for 1,2,3,4,5,6,... turns and then i saw similarities from 8,9,10,11 turns and turned this into a recursion and voila ... finished.
... ok ... took a view weeks playing with a lot of numbers :)
True. You can do this without dynamic proggramming and approach it like a combinatorial counting problem. Beware for all the edge cases.
Well, you can find a DP solution by generalising. Instead of calculating the number of all pathes to (i, j), we can calculate the number of all pathes entering to (i, j) from a certain direction. And when does it exactly make a turn?
Input : for 2nd test case
2 3 1
you can not reach to 2,3 with 1 turn.
what ever the test case explanation is incorrect
Test Case #01: He can't reach (2, 3) with 0 turns. There are only two ways to reach (2, 3) with exactly 1 turn.
1.He starts from (1, 1) facing down and moves to (2, 1). Then he turns right and takes two steps forward to reach (2, 3).
2.He starts from (1, 1) facing right and moves two steps forward to reach (1, 3). Then he turns down and proceeds one step to (2, 3).
I have trouble with #5 in Erlang. It is aborted. I have tested it and it takes 0.643s and answer is correct. So I have tried to set memory limit ulimit -m to 512MB and it works. But I have noticed ulimit -v set to 512MB crashes. It doesn't make sense. The virtual memory is virtual because it is not a real memory but just virtual address space. Erlang uses many various allocators which I don't have control of and allocates more memory then really uses, but it is a virtual memory, not real memory. Those are memory pages which are not really allocated and used. Anyway ulimit -v should not be used for dynamic languages like Erlang.
He is free to face any direction before starting from (1, 1).
If he faces downwards direction but choose to move rightwards then he can reach(2,2) with 2 turns which contradicts the test case # 1. ?
What is the timeout for test case #5, i have verified the answer its correct and runs around 3 seconds on my laptop, it still timesout here
Ok, an update.. using double isn't helping as i lose precision its fast though, gets me answer in less than a second which takes 3 seconds using BigInt. Any tips from those who implemented the solution in scala?
Is there anything special about test case #1? My solution is giving the wrong answer for that one but fine for all the others.
same for me
No more comments