Editorial for The Contest Contest 1 P3 - A Typical WAC Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
It suffices to brute force all possible arrays, where we can check if the array violates at most requirement in
time.
Subtask 2
We observe that the constructed array must always be non-decreasing. To see this, suppose this wasn't the case and so there exists two indices such that
. This implies that
. However since
, this would require at least
modifications which is not allowed.
We also observe that since at most one modification can be made, the constructed array must either satisfy all or satisfy all
. Hence, we can build
possible arrays, where the first one satisfies all
and the second one satisfies all
. For the former, we construct the array from left to right. At each index
, there are two possibilities:
- Case 1:
This means the current element must be equal to the previous element. - Case 2:
Observe that for a solution to exist,must equal
, since the preceeding elements must be less than
. We set the value of
to be the next smallest value.
After constructing the first array, we then have to check if it violates at most one
We build the second array using all in a similar manner. If both arrays can be built, we pick the lexicographically smaller one.
Subtask 3 Hint
What doesSubtask 3 and 4
We can extend the solution in subtask 2 by recognizing that and
gives the rank of the
element in ascending and descending order respectively. Using
as an example, notice if we process elements in increasing order of
, we see that the values in the constructed array are uniquely determined based on whether or not the current and previous value of
are equal.
Once both arrays are constructed, we can check if they satisfy all the requirements in time.
For full marks, we can optimize checking if an array satisfies all requirements by using a BIT.
Time Complexity:
Comments