Help for Wytherins in Paradise?

1

can anybody help with the idea for this problem i was not able to solve during the contest , after i have seen some submission but still not getting any accurate idea please help ?
problem: CodeChef: Practical coding for everyone

2

Hi,

You can refer to my solution: CodeChef: Practical coding for everyone

Logic behind the code is:

  1. If the difference between X and A is a multiple of S, we can make certain moves of S and reach X from A.
  2. Similarly, if the difference between B and Y is a multiple of S, we can reach Y from B.

For example, if I am at 7 and S is 3, I can reach 10, 13, 16, etc.

Now another case is that, if X or Y is at equal distance from the boundaries, for example if S=3. And X=1,4,7,10, etc.

In that case, no matter where I am on the grid. I can move to the boundaries and then reach X. Similarly for Y.

Both X and Y conditions are not dependent on each other. For example, if you are at (A,B) and want to reach (X,Y). A has to be able to reach column X and B has to be able to reach column Y.

Checking on these conditions will give full AC.

3

i understand first part when difference between ‘x’ and ‘a’ is multiple of ‘s’ and similarly for y
but i am not getting in case when we have to return after touching boundaries can you explain that little bit more?

4

Suppose, A=9 and S=5. We want to reach X=11.

It is not possible if we look at diff between A and X.
However, we can do the following operations:
9-4-1 (boundary touched)
1-6-11 (X reached)

Similarly, boundary of m and n has also to be checked.

5

thanks i understand if we can reach X from any boundaries and Y from any boundaries then it possible to reach (x,y) but in your code below can you explain x%s==1 and y%s==1?

bool poss_x=0, poss_y=0; //possible in x and y directions
if((a-x)%s==0 || (x-a)%s==0 || x%s==1 || (m-x)%s==0) poss_x=1;
if((b-y)%s==0 || (y-b)%s==0 || y%s==1 || (n-y)%s==0) poss_y=1;

6

It is because, the values of A and B are 1-indexed and not 0-indexed. Meaning, boundary is when A=1 or B=1.

If A % S ==1, A can be 1, S+1, 2S+1 and can be reached from starting point of 1 boundary.

7

thanks bro got it