Блог пользователя devdavethedev

Автор devdavethedev, 4 месяца назад, По-английски

The O(nlogn) Solution to 2250D - Permutation Cuts

The official editorial actually produces an elegant O(n) solution based on merges but this post describes a different approach I derived during the contest. Although it is slower, it was accepted and is based on a slightly different derivation. Unfortunately, I missed a couple of validity checks during the contest, so I didn't manage to get the AC in time.

Step 1: The value n-1

The first observation is that no value in a can be equal to n. Since the global maximum lies entirely on one side of every cut, the maximum opposite side is at-most n-1. Now consider the value n-1. Suppose a_i=n-1. Since a_i=min(max(left),max(right)), both sides of the cut must contain a value at least n-1.The only possibility is that one side contains n while the other contains n-1.

Therefore, every cut whose value is n-1 lies strictly between the positions of n-1 and n in the permutation p. Conversely, every cut between these two positions has a value n-1. Hence:
Lemma 1: The occurrences of n-1 form one contiguous block.
If no such blocks exists, or if the occurrences are not contiguous, the answer is 0. Let
- L be the first occurrence of n-1,
- R be the last occurrence.
Let us assume that n-1 appears before n in the permutation p. (The opposite direction is also possible and it contributes the same number of valid permutations. Hence the answer obtained here is multiplied by 2 at the end.)

Then
- position L of the permutation must contain n-1
- position R+1 must contain n
Thus the permutation naturally decomposes into
- a prefix
- the interval between n-1 and n
- a suffix

Step 2: Prefix and Suffix Structure

Before reaching n-1,every cut has n on its right. Therefore, a_i=max({prefix}) for every i<L. Hence the prefix of a must be non-decreasing. Similarly, after passing n, a_i=min({suffix}) for every i>R. Hence the suffix of a must be non-increasing. If a does not satisfy these, then the answer is 0.

Now we compress consecutive equal values into runs, where for each run we store the head (value of the run) and length. The suffix is first reversed.

Step 3: Maintaining Available Values

For every value x, we define availableLessThan[x] to be the number of currently unused values strictly less than x. Initially, availableLessThan[x]=x-1.
When processing a run with a head (h) and length (k):
- The position of the head itself is forced.
- The remaining k-1 positions should contain unused values smaller than h.
- Hence we need availableLessThan[h] >= k-1. Otherwise the construction is impossible.
The number of choices is availableLessThan[h]!/(availableLessThan[h]-k+1)!. After fixing this run, the head itself is removed and every chosen filler is removed from availableLessThan[x] by range updates. Thus the data structure to maintain this is easiest implemented with a segment tree with lazy propagation.
Additionally, a fixed[] array ensures that every head value is forced exactly once.

Step 4: Why Processing One Side First Fails ------------------ My first idea was the process the prefix and then the reversed suffix directly. But this is wrong because a larger head processed too early may consume values needed by a smaller head appearing on the other side. The correct algorithm is to process forced maxima globally in increasing order of their values.
Since both compressed prefix and reversed suffix are already increasing in terms of head value, this is simply a two-pointer approach.

Step 5: The Middle Interval

The elements lying strictly between n-1 and n never become maxima for either side. Once every forced value has been placed, these remaining values may appear in arbitrary order. If the interval contains R-L elements, it contributed a factor of (R-L)!.
Finally, multiply the answer by 2 to account for the symmetric orientation where n appears before n-1.

Complexity

  • Compressing Runs : O(n)
  • Two pointer processing : O(n)
  • Segment tree operations : O(log n) per run
  • Factorial precompute : roughly O(2e6)
    Overall complexity : O(nlogn) with O(n) memory.



Although the official O(n) solution is cleaner, I found this derivation interesting because it has come by identifying structural properties of the n-1 interval and maintaining a global invariant over forced maxima. I hope someone finds this viewpoint as an alternative way of thinking about the problem.
If you want to checkout my code that got accepted (C++), here you go:384432976

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by devdavethedev (previous revision, new revision, compare).

»
4 месяца назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

i had pretty much the same idea, figuring out where to place the n-1 and n and then the rest of array a must be nondecreasing prefix and nonincreasing suffix. however, we actually dont need a segtree, as we can just take the unused numbers as well as the bounds (produced from a value in array A that is the same as previous) and sort them, then go through and bin search how many can go in the location of a bound.