Ahmad's blog

Minimum number of moves to jump from start to end?
By Ahmad, history, 8 years ago, In English

Let's say you're given a string where the start point is the beginning of the string and the end point is the end of the string. For each turn, you can jump at most s positions in the string but there are obstacles in the string which you are not allowed to land on.

So for example a string like "SOOOXOE" (where "O" represents a free space and "X" represents an obstacle) and there's an s value of 3. The minimum number of moves in this case to get from S to E is 2. But in a case like "SOOOXXOE" with the same s value, the minimum number of moves is 3.

I came up with a greedy where you jump as far as possible as long as it's valid position each turn and it works. But I need to calculate the minimum number where the difference between S and E is at most 1,000,000,000 so simulating the jumping is too slow. Does anyone have any ideas about how to solve this efficiently?

*Note that I'm not actually given a string of length 1,000,000,000 but I visualized it as a string so it's easier to understand. Also if it helps, there will be at most 40 obstacles per string and s is always greater than 1 and less than or equal to 6. It is always possible to reach E from S.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Let more formal.

You have sequence of n. and there m — obstacles, p[i] — position of i-th obstacle. and s — jumping step. first letter of sequence is 'S', last is 'E', obstacle position's 'X' and others are 'O' — means empty.

There no i with p[i] = 1 and p[i] = n.

Limits: 1<=n <= 10^9, 0 <= s < n. 0<= m < M. (M ~ 10^5).

Required number of jumps from position 1 to n where not land on obstacles.

Heah ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah that's a much better way to say it.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think there O(m) solution. We assume p[] array is sorted, otherwise required O(mlog(m)) operations to sort p[] array.

      Let p[0] = 0, p[m+1] = n+1.

      //Let i - current position (initially i= 1), and 
//j - first p[] element which p[j] >= i+s (initially j = 0).
//k - first p[] element which k <= j and p[k] - 1 is empty (initially k = 0).
// ans - current number of jumps , (initially ans = 0).

//each step:
//  1. if i + s >=n -->  return ans+1.
//  2. while( p[j] < i + s) {
//         ++j; 
//          if ( p[ j-1 ] < p[ j ] - 1) // so p[j]- 1 position is empty
//              k = j ;
//      
//   }
//  3. if (p[j] > i + s) // so i + s position is empty
//       {  i = i + s; ans =ans+1; go to step 1.}
//  4. p[j] == i + s // need find that k <= j, which p[k] - 1 is empty, we already //                     //have it..
//         i = p[k] - 1, ans = ans + 1, go to step 1.
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Only need optimize step-3.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks! And I think a way to optimize step 3 would just be to divide p[j] by s and that'll tell how many moves it'll take to get through all of it.

          → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

greedy solution is correct but to avoid simulating jumping, you have to find for every posing the closest obstacle for it.
lest consider you're on posing x and the obstacle is on posing y then you can jump (y-x-1)/s step before reaching the obstacle, so add to the answer (y-x-1)/2+1 and move directly to the position y+s-1 because in (y-x-1)/2 jumps you will reach position y-1 then you have to just one more jump to reach position y+s-1, do those steps until you reach the end
to get the closest obstacle, simply put all the obstacles positions in a set and use LOWER_BOUND to get the closet one for a fixed position

→ Reply