Editorial for The Contest Contest 1 P3 - A Typical WAC Problem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: rickyqin005

Subtask 1

It suffices to brute force all possible arrays, where we can check if the array violates at most 1 requirement in O(N2) time.

Time Complexity: O(NN+2)
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 i,j such that xi>xj. This implies that bi,cj>0. However since bi=cj=0, this would require at least 2 modifications which is not allowed.

We also observe that since at most one modification can be made, the constructed array must either satisfy all ai or satisfy all di. Hence, we can build 2 possible arrays, where the first one satisfies all ai and the second one satisfies all di. For the former, we construct the array from left to right. At each index i, there are two possibilities:

  • Case 1: ai=ai1
    This means the current element must be equal to the previous element.
  • Case 2: aiai1
    Observe that for a solution to exist, ai must equal i1, since the preceeding elements must be less than xi. We set the value of xi to be the next smallest value.

After constructing the first array, we then have to check if it violates at most one di

We build the second array using all di in a similar manner. If both arrays can be built, we pick the lexicographically smaller one.

Time Complexity: O(N)
Subtask 3 Hint What does ai+bi and ci+di give you?
Subtask 3 and 4

We can extend the solution in subtask 2 by recognizing that ai+bi and ci+di gives the rank of the ith element in ascending and descending order respectively. Using ai+bi as an example, notice if we process elements in increasing order of ai+bi, we see that the values in the constructed array are uniquely determined based on whether or not the current and previous value of ai+bi are equal.

Once both arrays are constructed, we can check if they satisfy all the requirements in O(N2) time.

For full marks, we can optimize checking if an array satisfies all requirements by using a BIT.

Time Complexity: O(NlogN)

Comments

There are no comments at the moment.