Reference no: EM132400873

Aisha is playing a game where she controls a character to catch pancakes falling onto a stage.

• The character can move left and right on a stage of length n. The character's location x is in the range {1, 2, ....., n}. Let Xt by the location of the character at time t. At each second, Aisha can move the character to the left (Xt + 1 = Xt - 1) one step, to the right (Xt+1 = Xt +1) one step, or stay in the same spot (Xt+1 = Xt).

(Exceptions: can't move left when current X = 1 and can't move right when X = n.)

• The game lasts m seconds.
• Aisha knows the game really well, so she knows when and where pancakes will fall, i.e. pairs (t,p), which means at t seconds, a pancake will be at position p. You are given this, and assume lookup of this information in constant time.

The character starts at location 1 at time 0. Please design an algorithm to find out the most pancakes Aisha can catch. It should run in O(mn) time - please also justify why.

Example: (t, p) sequence: (1, 1), (2, 2), (3, 4), (3, 5), (4, 3), (4,4), (5, 2)). Optimal solution: 4 pancakes. Aisha can stay still for first step (X1 = 1) and catch pancake, move right (X2 = 2) and catch pancake, stay still (X3 = 2) then move right (X4 = 3) and catch pancake, and move left at (X5 = 2) and catch pancake.