PLUS2MINUS1 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: jeevanjyot
Tester & Editorialist: iceknight1093

DIFFICULTY:

1098

PREREQUISITES:

None

PROBLEM:

Chef has an integer X, that’s initially 0. He can perform at most Y moves, each one as follows:

  • Increase X by 2; or
  • Decrease X by 1

How many distinct final values of X are possible?

EXPLANATION:

If Y = 0, no moves can be performed so the answer is just 1. Now let’s analyze Y \gt 0.

Since we’re allowed at most Y moves, we have some degree of freedom to stop when we want to.
Analyzing positive and negative numbers separately (since we can always have X = 0 by doing nothing):

  • We can use k moves of the second type to reach -k.
    This allows us to reach every number in the range [-Y, -1].
    It’s clear that no negative number that’s \lt -Y can be reached, since we have no other way of reducing X.
  • We can use k moves of the first type to reach 2k.
    This allows us to reach every even number in the range [2, 2Y]; and again clearly we can’t reach anything beyond 2Y.
  • As for odd positive numbers, note that if we reach 2k and have (at least) one move left, we can then reach 2k-1 by using the second move and subtracting 1.
    This allows us to reach every odd number in the range [1, 2Y-3] for sure; but we can’t reach 2Y-1 because we have no moves left after reaching 2Y.

Putting everything together, we can reach:

  • 0
  • [-Y, -1]: there are Y integers here
  • Even numbers from 2 to 2Y: another Y integers
  • Odd numbers from 1 to 2Y-3: there are Y-1 such integers

Note that the last two combined are just all the numbers in the range [1, 2Y], except for 2Y-1.

The total count is just 1 + Y + Y + Y-1 = 3Y.
So,

  • If Y = 0, the answer is 1.
  • Otherwise, the answer is 3Y.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    y = int(input())
    print(max(1, 3*y))
1 Like