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
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
We also observe that since at most one modification can be made, the constructed array must either satisfy all
- 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
Subtask 3 Hint
What doesSubtask 3 and 4
We can extend the solution in subtask 2 by recognizing that
Once both arrays are constructed, we can check if they satisfy all the requirements in
For full marks, we can optimize checking if an array satisfies all requirements by using a BIT.
Time Complexity:
Comments