Person in Charge

• 035966_L3

Attention

Please strictly follow the submission instructions.

Problem Description

Main Statement

Sleeping Cat has invented a permutation-based algorithm called the Fast Permutation Transform (FPT). This algorithm can transform a permutation $p$ of $1 \sim n$ into any lexicographically larger permutation $q$.

The implementation of FPT is as follows: perform several operations on the permutation $p$, where each operation selects a contiguous subsequence of $p$ and calls the next_permutation function once.

The implementation of next_permutation for a permutation $\{r_k\}$ of length $k$ is as follows:

• Find the largest positive integer $i$ such that $r_i < r_{i+1}$;
• Find the largest positive integer $j$ such that $r_i < r_j$;
• Swap $r_i$ and $r_j$;
• Reverse the subsequence $r_{i+1} \sim r_k$;
• If no such integer $i$ exists, a runtime error will occur;
• Otherwise, the time cost of this call is $O(k - i + 1)$.

It can be proven that FPT can transform a permutation $p$ of $1 \sim n$ into any lexicographically larger permutation $q$ without runtime errors.

First Subproblem

Assume that FPT must call the next_permutation function on the entire permutation each time. Analyze the worst-case time complexity of FPT and provide a proof.

Second Subproblem

Assume that FPT can select any contiguous subsequence each time and always employs the optimal strategy (i.e., minimizing the total time cost, where the time cost of finding the optimal strategy is not counted). Analyze the worst-case time complexity of FPT and provide a proof.

Submission Method

## First Subproblem ($50$ points)

### Part 1 ($10$ points)

The worst-case time complexity of FPT is $O(n)$.

### Part 2 ($30$ points)

According to Sleeping Cat's Third Axiom (sufficiency part), the worst-case time complexity of FPT is clearly $O(n)$.

### Part 3 ($10$ points)

Here is a possible set of data:

- $p = \{1, 2, \ldots, n\}$.
- $q = \{n, n-1, \ldots, 1\}$.

## Second Subproblem ($50$ points)

### Part 1 ($10$ points)

The worst-case time complexity of FPT is $O(n)$.

### Part 2 ($30$ points)

According to Sleeping Cat's Third Axiom (necessity part), the worst-case time complexity of FPT is clearly $O(n)$.

### Part 3 ($10$ points)

Here is a possible set of data:

- $p = \{1, 2, \ldots, n\}$.
- $q = \{n, n-1, \ldots, 1\}$.

1. For each subproblem, you need to provide a proof in three parts (the above is an example proof, which is clearly incorrect):
   • Part 1: State the worst-case time complexity of FPT.
   • Part 2: Construct a strategy for calling the next_permutation function such that the total time cost of FPT does not exceed the time complexity you provided for any valid permutations $p$ and $q$ of $1 \sim n$.
   • Part 3: Construct a set of data such that, no matter which strategy for calling next_permutation is used, the total time cost of FPT degrades to the time complexity you provided.
2. You need to fill in your Sleeping Cup UID in the code below and submit it in C++.
3. The partial scoring design for this problem has been provided in the example proof above.
4. This problem will be manually graded after the contest, and the AC records will be updated accordingly. Therefore, it cannot be AC during the contest. If you submit multiple proofs, the last one will be used. Please strictly follow the above submission requirements; otherwise, you will bear the consequences.

#include <bits/stdc++.h>
using namespace std;
const int UID = /*Enter your UID here*/;
int main()
{
    freopen("proof.in", "r", stdin);
    freopen("proof.out", "w", stdout);
    cout << UID;
    return 0;
}

5. Do not maliciously fill in the UID. Violators will be warned or banned.
6. After the contest, the submission method is as follows, and the admin will grade it periodically.

#include <bits/stdc++.h>
using namespace std;
const int UID = (-1) * /*Enter your UID here*/;
int main()
{
    freopen("proof.in", "r", stdin);
    freopen("proof.out", "w", stdout);
    cout << UID;
    return 0;
}
/*
## First Subproblem ($50$ points)

### Part 1 ($10$ points)

The worst-case time complexity of FPT is $O(n)$.

### Part 2 ($30$ points)

According to Sleeping Cat's Third Axiom (sufficiency part), the worst-case time complexity of FPT is clearly $O(n)$.

### Part 3 ($10$ points)

Here is a possible set of data:

- $p = \{1, 2, \ldots, n\}$.
- $q = \{n, n-1, \ldots, 1\}$.

## Second Subproblem ($50$ points)

### Part 1 ($10$ points)

The worst-case time complexity of FPT is $O(n)$.

### Part 2 ($30$ points)

According to Sleeping Cat's Third Axiom (necessity part), the worst-case time complexity of FPT is clearly $O(n)$.

### Part 3 ($10$ points)

Here is a possible set of data:

- $p = \{1, 2, \ldots, n\}$.
- $q = \{n, n-1, \ldots, 1\}$.
*/

Official Solution

link