SWPG - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: hellolad
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Alice and Bob play a game with N rounds, alternating turns between them.
Initially, the score is 0. On the i-th turn, the current player must either add or subtract 2^{i-1} from the score.
The final value of the game is the difference between the maximum and minimum values attained by the score at any point.

Alice wants to minimize the final value, Bob wants to maximize it.
Find the final value if both players play optimally.

EXPLANATION:

We’re dealing with powers of two, and they increase extremely rapidly (exponentially, if you will).
This means that the current score depends greatly on the last power of two used.

Let’s define a few quantities:

  • S_i will denote the score after i rounds.
  • X_i will denote the maximum score after i rounds, i.e. X_i = \max(0, S_1, S_2, \ldots, S_i).
  • Y_i will denote the minimum score after i rounds, i.e. Y_i = \min(0, S_1, S_2, \ldots, S_i).

The quantity we care about is X_N - Y_N.
Now, as noted above, the score depends heavily on the last power of two used.
In fact, we can prove the following facts:

  1. For any i, no matter what Alice and Bob do, either S_i = X_i or S_i = Y_i.
    That is, the current score will always be either the minimum or the maximum seen so far.
  2. It is also not possible for the difference between minimum and maximum to be too large or too small: for any i, 2^{i-1} \leq X_i - Y_i \lt 2^i will hold.
Proof

Let’s imagine the score in terms of distance: there’s a person starting at point 0 on the number line, and they walk either left or right 2^{i-1} steps, on the i-th move.

With this perspective, the second fact is fairly easy to see:

  1. The last move made is moving $2^{i-1} steps either left or right.
    Either way we get a distance of at least 2^{i-1} between the minimum and maximum point reached.
  2. Second, the furthest distance that can possibly be traveled is by repeatedly moving in the same direction, giving a maximum of 2^0 + 2^1 + 2^2 + \ldots + 2^{i-1} \lt 2^i.
    “Turning around” is not really helpful in this regard, since we’ll just end up walking through some points we’ve already walked past.

Once this is established, the first point, that the current score is always either the maximum or minimum, is fairly easy to show too.
We use induction:

  • It’s clearly true after the very first move has been made.
  • Next, suppose it’s true after i moves have been made.
    Without loss of generality, suppose S_i = X_i, i.e. the current score is the maximum.
    Then, upon making the (i+1)-th move,
    • If 2^i is added, then the maximum increases, and the current score remains a maximum.
    • If 2^i is subtracted, the new score is X_i - 2^i.
      This is the minimum seen so far, because as established earlier X_i - Y_i \lt 2^i, meaning X_i - 2^i \lt Y_i.
  • So, the new score is either a maximum or a minimum, as claimed.

Now, we can use this information to solve the problem.

First, suppose N is odd, so that Alice gets the last move.
From above, we know that no matter what she does, the absolute minimum possible difference is 2^{N-1}.
Alice can always attain exactly this difference, as follows:

  • First, do anything for the first N-1 rounds. Bob can never get the difference higher than 2^{N-1} anyway.
    Alice only needs to play the last round carefully.
  • If S_{N-1} = X_{N-1} (i.e. before the last move, the score was the maximum), subtract 2^{N-1}.
    This will set X_N = X_{N-1} and Y_N = X_{N-1} - 2^{N-1}, which gives us what we want.
  • If S_{N-1} = Y_{N-1}, add 2^{N-1} instead to attain the same difference.
    As noted above, one of these two cases must definitely hold after the (N-1)-th move so we’re done.

Next, let’s look at even N.
This time, Bob gets the last move.
He can follow a similar (but opposite) strategy to Alice on his last move:

  • If S_{N-1} = X_{N-1}, add 2^{N-1} to the score.
    This will set X_N = X_{N-1} + 2^{N-1} and Y_{N} to Y_{N-1}, so the difference is 2^{N-1} + (X_{N-1} - Y_{N-1}).
  • If S_{N-1} = Y_{N-1}, subtract 2^{N-1} instead, and once again the difference becomes 2^{N-1} + (X_{N-1} - Y_{N-1}).

Since Alice wants to minimize the final difference, her aim will thus be to make X_{N-1} - Y_{N-1} as small as possible.
However, that’s just the first case above, where we know the answer is 2^{N-2}.
So, in this case the answer is 2^{N-1} + 2^{N-2}.

In summary,

  • If N is odd, the answer is 2^{N-1}.
  • If N is even, the answer is 2^{N-1} + 2^{N-2}.

The constraints are small enough that the powers of 2 can just be computed in linear time each.
Make sure to reduce the product modulo 998244353 after every multiplication, and not just at the end - otherwise it will overflow.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase, though \mathcal{O}(\log N) (with binary exponentiation) or \mathcal{O}(1) (with precomputed powers of two) are also possible.

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
for _ in range(int(input())):
    n = int(input())
    if n%2 == 1: print(pow(2, n-1, mod))
    else: print((pow(2, n-1, mod) + pow(2, n-2, mod)) % mod)
2 Likes