BOP3 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given an integer N which is even.
Starting with S = \{0, 1, \ldots, N\}, you must do the following:

  • Choose two distinct elements X, Y \in S
  • Add \max(X, Y) to your score.
  • Insert X \ \& \ Y to S if it’s not already present.

Operations must be performed till it’s impossible to perform any more.
Find the minimum possible final score.

EXPLANATION:

Note that the process will stop only when there exists exactly one element in S.

Now, we must certainly perform an operation involving the value N at some point of time; because if we never touch it, the set will contain both N and some value in [0, N-1] in the end.
Whenever we perform the operation using N, we’ll definitely add N to our score.

Suppose we pair N with x.
We are then able to functionally eliminate x from ever being chosen by an operation; as long as we ensure x is never added into the set again.

What’s the optimal choice of x?
Well, x = N-1 of course!

Consider what happens when we pair N with N-1 in the first operation.
We add N to the score, and then insert (N \ \& \ (N-1)) to the remaining set.
Now,

  • N is even, so N \ \& \ (N-1) must also be even (it cannot have the lowest bit set because it’s not set in N.)
  • But, N \ \& \ (N-1) is also by definition a submask of N-1, i.e. its only possible set bits are some of those set in N-1.
    Since N-1 is odd, this means N \& (N-1) cannot equal N-1.
  • So, N \ \& \ (N-1) is strictly smaller than N-1.
    Since we performed this operation as our very first move, we still have all values \lt N-1 remaining with us.
    Thus, we don’t need to insert any new elements into the set - we just delete both N and N-1.

Observe that we’ve functionally paid a cost of N to delete N and N-1 from the array; which just leaves us with the same problem but with N-2 instead.
Applying the same idea over and over again, we see that the final score we end up with is

N + (N-2) + (N-4) + \ldots + 6 + 4 + 2

i.e. the sum of all even numbers \le N.

It’s not hard to prove that this is optimal: using N we can eliminate at most one element smaller than it and so it’s optimal to eliminate N-1; then N-2 can eliminate at most one smaller element so it’s optimal to eliminate N-3, and so on.

The answer is hence, quite simply, the sum of all even numbers from 2 to N.

This can be computed in \mathcal{O}(N) time by running a loop (which the constraints do allow for), or you can compute it in \mathcal{O}(1) by noting that

2 + 4 + 6 + \ldots + N = 2\cdot \left(1 + 2 + 3 + \ldots + \frac{N}{2}\right)

And we have

1 + 2 + \ldots + \frac{N}{2} = \frac{1}{2}\cdot \frac{N}{2} \cdot \left(\frac{N}{2} + 1\right)

So combining both the answer just becomes

\frac{N}{2} \cdot \left(\frac{N}{2} + 1\right)

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    print(n//2 * (n//2 + 1))