may be unable to make even a single move. Design an algorithm which runs in O(n log
Alice writes n distinct integers on a blackboard, and picks a positive integer K.
She then allows Bob to make moves, each of which consist of the following steps.
1. Identify two integers x and y on the blackboard which differ by at most K, i.e. |x − y| ≤ K.
2. Erase the smaller of the two chosen integers.
Bob’s task is to make moves in this way until he is no longer able to do so.
Note that in some cases, Bob may be unable to make even a single move.
Design an
If there are several sequences of maximum length, you may find any of them.
Do not write the code, give steps and methods. Explain the steps of algorithm, and the logic behind these steps in plain English
Bob makes several moves, each consisting of the two steps above, until no more valid moves are available. The problem asks you to design an algorithm which finds the greatest number of consecutive moves that Bob can make from the initial state, and what moves should be made to achieve this number.
In some initial states, Bob has no valid moves. For example, if n = 5, K = 1 and the numbers are 1, 3, 5, 7, 9, then Bob cannot make any moves and the longest sequence of moves is simply the empty sequence.
Use the greedy method.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
