There's a problem on hackerrank.com called Grid Walking.
Here is its description:
You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,...DN). In one step, you can walk one step ahead or behind in any one of the N dimensions. (So there are always 2×N possible different moves). In how many ways can you take M steps such that you do not leave the grid at any point? You leave the grid if at any point xi, either xi≤0 or xi>Di.
I'm not looking for the solution, no. I'm looking for the explanation of the statement. I need to confess that I don't understand the problem (maybe due to my poor English). For me it feels like the task is about being situated in a multidimensional array (and the phrase here are always 2×N possible different moves seems to confirm that) and walking inside it without going out of its boundaries. Yet, some points need clarification for me and some just contradict this idea of mine. So here I have few questions:
1) What is N dimensional grid? Is it simply N dimensional array? Am I right?
2) What is position (x1,x2,...,xN)? Is it simply current position in the array like [3][4][5]?
3) What is dimensions of the grid are (D1,D2,...DN)? Is it simply lengths for every dimension of the array?
If all my assumptions are correct then the task seems to be more or less understandable, but it seems like they are totally incorrect because input format description breaks everything I have assumed and brings me into absolute confusion:
The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and M, the second line contains x1,x2,…,xN and the 3rd line contains D1,D2,…,DN.
Let's have a look at the sample input:
10
1 287
44
78
1 236
25
87
1 122
41
63
1 260
7
64
1 127
3
73
1 69
6
68
1 231
14
63
1 236
13
30
1 259
38
70
1 257
11
12
Here I have few more questions:
1) As you can see all the test cases have 1 for N. But... why? Does it mean that the array(grid) has just one dimension? Or what? I'm completely lost at this point.
2) the second line contains x1,x2,…,xN. And for the first test case it is 44. For the rest of the test cases it is also just one number. What? How can it represent a position? Does it mean that x1,x2,…,xN is something completely different from what I thought it is? Then what does it mean?
3) the 3rd line contains D1,D2,…,DN. As I know from the statement D1, D2, ..., DN is the dimensions of the grid. And again, just like with the previous question it is just one number. 78 for the first test case. But how 78 can represent the dimensions? for 1 dimensional array? Maybe it just means that indeed the array is 1 dimensional, its only dimension is 78 in length and I'm situated on the 44th position? But M which is 287 breaks this assumption too.
As you can see I'm totally confused and really need your help. Would anyone clarify this for me? Thanks a lot
