KNGHTMOV - Editorial

editorial
, , , ,
21

Please explain / give some reference for Bellman Ford + Dynamic Programming.

22

my solution id is http://www.codechef.com/viewsolution/1349935
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

23

please help

24

Will the links to the solution by tester and setter ever be updated ?

1 Like
25

Donā€™t think they exist. :stuck_out_tongue:

1 Like
26

The solution links have been fixed.

27

Thanks for the editorial, it was really helpful. Iā€™d just like to point out that I think thereā€™s a bug in the testerā€™s solution.

For example, for the input

1
1 0 0
1 -3 2 -6

it outputs 1, but the answer should be 0 because you canā€™t reach (1, 0). The problem is that the solution doesnā€™t really check if (X, Y) is on the line that is reachable by doing A and B moves when A and B are linearly dependent before discarding Y and just working on X. It attempts to check around line 108

if(AX == AY && X != Y){ puts("0"); continue; }

I assume the first condition is supposed to eliminate the case when one of AX or AY is 0, (otherwise they should be ā€œequalā€) and then X should be equal to Y. This might work if all these numbers were nonnegative, but the problem allows them to be negative. In the input I provided, at this point we get AX==1 and AY==-1 and the second test is never performed. After this, the Y coordinate is dropped and the program computes the answer 1 by using one A step (but that actually leads to (1, -3), not (1, 0)).

Also, if you reduce the problem to moving on the minor diagonal (i.e. ā€¦(-1, 1) -> (1, -1)ā€¦) the second test will sometimes return 0 when there are actually ways to get to (X, Y).

I assume this is because in some iteration of the problem, these numbers were not allowed to be negative and then no tests checked this problem and only the gcd function was fixed to allow negative numbers.

Anyway, itā€™s not too hard to fix. I think something like this should work

if (abs(AX)>0 && abs(AY)>0) {
  bool maindiag = (AX*AY>0); // signs match
  if (abs(X)!=abs(Y) || (maindiag && X*Y<0) || (!maindiag && X*Y>0)) {
    puts("0");
    continue;
  }
  // fix blocked points as well in the same way ...
}

I havenā€™t tested this or thought it trough completely, but it might work :). We donā€™t need to worry about the horizontal or vertical case because that is handled correctly in the surrounding code.

BTW, youā€™re probably aware of this, but the setterā€™s solution seems to be solving a different problem altogether because it doesnā€™t even read the same input.

28

What is the ā€œSETTERS SOLUTIONā€ actually about ā€¦ ? ā€¦

Is that a sub-task ? ā€¦ I didnā€™t find AX, AY, BX, BY or even X, Y ? ā€¦