PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given an array A of length N, initially filled with zeros.
You can perform the following operation:
- Choose an index i and increment A_i by 1.
- Then, let Z denote the number of indices i such that A_i = A_{i+1} = 0.
Add Z to your score.
Compute the minimum possible score you can obtain, if the final array A needs to be a permutation of [1, 2, \ldots, N].
EXPLANATION:
Before any operations are performed, Z = N-1, i.e. there are N-1 pairs of adjacent zeros.
Each operation we perform can reduce Z by at most 2: if we increment A_i, then only the pairs (i-1, i) and (i, i+1) will no longer count - all other pairs will remain unchanged.
Since we want to minimize the total score, it’s clearly optimal to reduce Z by 2 in every move we can, till it reaches 0.
Once it reaches 0, our score will never change - so we can take our time forming a permutation.
It’s easy to see that Z can be always reduced by 2 till it reaches 0, by incrementing positions 2, 4, 6, 8, \ldots as our first move.
For example, when N = 9, the optimal sequence of moves is
The first move disables pairs (1, 2) and (2, 3), the second move disables pairs (3, 4) and (4, 5), and so on.
Once we reach the end with alternating zeros and ones, we can slowly convert the array into a permutation - say [1, 2, 3, \ldots, N] - without ever increasing our score.
Now that we know what’s optimal, let’s compute the final score.
We start with Z = N-1, and every move reduces Z by 2 till it reaches 0.
So, the overall sum is
till the term reaches 0.
Since the problem allows \mathcal{O}(N), the simplest solution is to just compute this using a loop.
Alternately, you can use the fact that this is an arithmetic progression to compute the answer using a formula in constant time.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
rem, ans = n-1, 0
for i in range(1, n, 2):
rem = max(0, rem-2)
ans += rem
print(ans)