Editorial for HHPC1 P2 - Yuniformity Challenge
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
To make all numbers in the subarray the same in at most two steps, let's break down all situations:
Situation 1 (achieved in zero steps):
All numbers within the subarray are originally the same.
This can be checked using the Prefix Sum Array (PSA) by summing the absolute differences between each pair of adjacent numbers.
Situation 2 (achieved in one step):
Apply the second strategy to multiply all numbers within the subarray by
This can also be achieved using the PSA by counting the number of
Situation 3 (achieved in two steps):
If there is no zero, we can apply the first operation to add
Implementing this might be more complicated, but it can also be done using the PSA. Iterate through all
The intended time complexity is
Comments
I believe it should say you have to check whether the maximum value in the prefix from![pre[1]](https://static.dmoj.ca/static/blank.b44917055649.gif)
to ![pre[r]](https://static.dmoj.ca/static/blank.b44917055649.gif)
is greater than or equal to 
.