Try this case: (your code gives fpe)
2 0 0
1 0 -1 0
Another case: (solution is 1 instead of -1)
3 3 3
3 3 -1 -1
-1 -1 2 2 6 6
Where are you doing the cycle detection mentioned in the editorial?
Thanks a lot for the explanation ,now I get it 
.The editorial mentions nothing of handling this case.
I will add it to the Editorial Thanks!
Please explain / give some reference for Bellman Ford + Dynamic Programming.
my solution id is CodeChef: Practical coding for everyone
i have done it in i different way and i know that i have missed some cases just want to know which one i meissed
please help
Will the links to the solution by tester and setter ever be updated ?
1 Like
Donāt think they exist. 
1 Like
@Sumudu Why canāt we do the same thing in case I.
The search space then would be 1000 X 10000 which should be acceptable. Weāll perform a dp (as you mentioned for case II) by traversing the DAG to count the number of ways and avoid those vertices from which the final destinal X,Y cannot be reached. In case a cycle is detected, the answer will be -1.
Why use Gaussian elimination ?
Testerās solution provided above fails on:
1
1 1 0
1 -1 -1 1
The answer is 0, e.g. because (x + y) is invariant and = 0 with the given transitions, but the target is at (1, 1) with x + y = 2.
Im getting a SIGSEGV error upon submission, although Iāve tested against almost 100000+ random test cases.
Inspired by and tested against Yeputonās Submission
Any help will be appreciated!
CMIIW but another test which testers solution fails:
1
-1 -1 1
4 -4 -1 1
-4 4
Should be 0 but gives -1.
I attempted this problem with graphs (SCC + DP) but didnāt manage to find the bug (CodeChef: Practical coding for everyone).
The idea is to work within a square of size 1000 x 1000 in the cartesian plane with its center at (0, 0). So you can work in [-500, 500] x [-500, 500] or shift all the coordinates by 500 and work in [0, 1000] x [0, 1000].
Consider each coordinate as a node and add the edges to the coordinates it can reach. Run tarjan for SCC, build the DAG and consider a SCC to allow a cycle if its size is >= 2.
Then check if there is a path from the SCC corresponding to node (0, 0) to the SCC corresponding to node(X, Y) with some SCC allowing a cycle in the middle. It there is, it means we can go to that SCC, cycle as much as we like and then arrive at the final node, so answer is -1. Otherwise it means that all paths going from node(0, 0) to node(X, Y) only have SCC with size 1. Therefore, we can just run a simple dp to calculate the number of ways to reach node (X, Y).
Obviously if there is no path from (0, 0) to (X, Y) answer is just 0.