# 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:

- Chef always starts at the origin.
- i always begins at 1.
- 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