DANCEMOVES - Editorial

PROBLEM LINK:

Contest

DIFFICULTY:

CAKEWALK

PROBLEM:

Given integers X and Y. Determine the minimum number of moves required to change X to Y, where in one move, you can either add 2 or subtract 1 from X.

EXPLANATION:

A simple problem, with a little casework:

Y \le X - In this case, Chef has to go X-Y steps backwards, from his current position. Since he can go only one step backwards in each move, the minimum number of moves required is thus X-Y.

Y > X - Here, Chef has to go Y-X steps forward, from his current position.
When Y-X is even, Chef can make exactly \frac{Y-X}{2} forward moves (since each forward move takes him two steps ahead) to reach Y.
When Y-X is odd, Chef can make \frac{Y-X+1}{2} forward moves (taking him to Y+1), followed by 1 backward move (taking him to Y).

It can be trivially deduced that no better sequence of moves exists.

TIME COMPLEXITY:

O(1)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here


Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters