SIGNMOVE Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Soumyadeep Pal
Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Initially, Chef is at coordinate 0 on X-axis. For each i=1,2,…,N in order, Chef does the following operation:

  • If Chef is at a non-negative coordinate, he moves i steps backward (i.e, his position’s coordinate decreases by i), otherwise he moves i steps forward (i.e, his position’s coordinate increases by i).

You are given the integer N. Find the final position of Chef on the X-axis after N operations.

EXPLANATION:

Note the following:

  1. Chef always starts at the origin.
  2. i always begins at 1.
  3. Chef’s action depends on the previous state and i.

The above statements are enough to prove that chef’s position is a function of i alone, i.e it can be written as position = p(i).

p(0) = 0
p(1) = -1
p(2) = 1
p(3) = -2
p(4) = 2
p(5) = -3
p(6) = 3
and so on …

Note that:
At even i's, p(i) = \frac{i}{2}
At odd i's, p(i) = \frac{-(i+1)}{2}

Thus, Chef’s position at N = p(N).

p(N) = \begin{cases} \frac{N}{2} \;\;\;\;if \; N\; is\; even \\ \frac{-(N+1)}{2} \;\;\;\;if \; N\; is\; odd \end{cases}

TIME COMPLEXITY:

The above calculation can be done in constant time. Hence, the solution has a time complexity of O(1).

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

1 Like