0

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

closed as too broad by Jörg W Mittag, user22815, user40980, user53019, durron597 Nov 3 '15 at 23:27

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • why downvote? what's wrong? – Andrey Chernukha Nov 3 '15 at 6:53
  • As far as I can see your assumptions are correct. So 1) Yes, seems the test cases are only for one dimension. 2) If you have only one dimension (so just a single line) you only need one number for a position. 3) Same, yes only one dimension, so basically the length of the line/array. M is the number of steps. Assume the simple case where you just move one step forward and one step back repeatedly. That's one case where you won't leave the grid. Same for two steps forward, two steps back etc. – thorsten müller Nov 3 '15 at 8:37
  • Though I fail to see why they would talk about N dimensions at all if their test cases don't cover that case and they also do not provide any info what a valid move in higher dimensions would be. Can you walk diagonally? Can you walk left and right? Up and down? Once you are > 3 dimensions this would become increasingly difficult. (Also the number of possible moves would grow very fast up to a level where for larger grid even a fast computer would not be able to process it in any reasonable time scale (I think)) – thorsten müller Nov 3 '15 at 8:40
  • 1
    PS: The down vote and close vote (not by me) are because somebody thinks the question is 'too broad'. It's a bit chatty and you put in several questions at once (though I think more to make your point clear). Maybe the Whiteboard chat room would be a good place to start with such a question. Personally I think we could leave such questions as kind of 'algorithms and data structures' but I guess it will be closed sooner or later. – thorsten müller Nov 3 '15 at 8:48
1

For the first questions:

1) yes

2) yes

3) yes


For the others, you are right as well.

Apparently, all test cases have dimension 1. It's quite silly, indeed.

So the first of the 10 test cases would be:

1 287
44
78

Translated in english:

Given an array of dimension 1 and length 78. Assume you start at position 44. In how many ways can you take 287 steps such that you do not leave the array at any point?

Not the answer you're looking for? Browse other questions tagged or ask your own question.