Maximal Order of Permutations

Pista 1

Como en muchos problemas que involucran permutaciones, podemos tratar los elementos de una permutación como nodos de un grafo y dibujar aristas entre $i$ y $\pi_i$ para cada $i$ .

Notemos cómo estas aristas forman varios ciclos disjuntos. ¿Qué se puede decir sobre el orden de una permutación a partir de los ciclos que forma?

Pista 2

Para alguna permutación, sea $l_i$ la longitud del $i$ -ésimo ciclo. El orden de la permutación es simplemente $\text{lcm}(l_1, l_2, \dots)$ , ya que el ciclo $i$ arreglará periódicamente sus elementos de forma correcta cada $l_i$ composiciones.

Además, notemos que el orden maximal de una permutación con $n$ elementos nunca es menor que el orden maximal de una permutación con $n - 1$ elementos.

Pista 3

Para hallar la permutación lexicográficamente más pequeña dadas las longitudes de sus ciclos, un enfoque voraz funciona. Además, los ciclos más cortos resultan en permutaciones lexicográficamente más pequeñas.

Pista 4

Todos los $l_i$ de una permutación óptima son coprimos dos a dos.

Demostración

Asumamos por contradicción que en una permutación óptima hay dos ciclos $i$ y $j$ con $l_i$ , $l_j$ tales que $g = \gcd(l_i, l_j) > 1$ . Podemos reemplazar esos dos ciclos por tres ciclos más pequeños de longitudes $l_i / g$ , $l_j / g$ y $g$ .

La permutación resultante es más corta, tiene el mismo orden que la original, pero es lexicográficamente más pequeña, lo que contradice nuestro supuesto.

Pista 5

Todos los $l_i$ de una permutación óptima son potencias de primos.

Demostración

Asumamos por contradicción que en una permutación óptima hay un ciclo $i$ con $l_i = p^a q^b x$ donde $p$ y $q$ son primos distintos. Podemos reemplazar ese ciclo por dos ciclos más pequeños de longitudes $p^a$ y $q^b x$ .

La permutación resultante es más corta, tiene el mismo orden que la original, pero es lexicográficamente más pequeña, lo que contradice nuestro supuesto.

Pista 6

Logaritmos.

Solución

Sea $dp[i][j]$ el orden maximal de una permutación con $i$ elementos con todas las longitudes de ciclo siendo potencias de los primeros $j$ primos. Vale la siguiente recurrencia:

dp[i][j] = \max(dp[i][j - 1], \max_{1 \leq p_j^k \leq i}(dp[i - p_j^k][j - 1] \cdot p_j^k))

El problema de este estado de DP es que los números pueden volverse demasiado grandes para guardarlos en un long long. Por suerte, como estamos trabajando con productos, podemos guardar logaritmos de los órdenes maximales. Nuestra recurrencia entonces se convierte en:

dp'[i][j] = \max(dp'[i][j - 1], \max_{1 \leq p_j^k \leq i}(dp'[i - p_j^k][j - 1] + \log(p_j^k)))

Podemos usar backtracking para restaurar la permutación óptima.

Hay 1229 primos menores que 10000, así que podemos implementar esta DP en un poco menos de $\mathcal{O}(1229 n)$ tiempo y memoria. Sin embargo, este enfoque usa demasiada memoria.

Intuitivamente, necesitamos limitar la cantidad de potencias de primos que intentamos: después de todo, es muy improbable que una permutación de longitud $\approx$ 10000 tenga un ciclo grande de longitud $\approx$ 9000.

¡Resulta que solo necesitamos usar los primeros 70 números primos!

Demostración

La siguiente demostración está traducida del editorial oficial polaco:

Definición 1: Sea $K_n$ el menor $k$ tal que para cada $k' \geq k$ , tenemos $dp[n][k'] = dp[n][k]$ .

Definición 2: Sea $\overline{K_n}$ el menor $k$ tal que para cada $k' \geq k$ y cada $n' \leq n$ , tenemos $dp[n'][k'] = dp[n'][k]$ .

Podemos expresar $\overline{K_n}$ en términos de $K_n$ así:

\overline{K_n} = \max_{0 \leq n' \leq n}(K_{n'})

Claramente, si $k \ge \overline{K_n}$ , entonces usar solo los primeros $k$ primos es suficiente.

Lema: Sea $n \geq 1$ . Si $h$ satisface al menos una de las siguientes condiciones:

$p_{h + 1} > n$ .
$h \geq \overline{K_{n-1}}$ y $dp[n][h] \geq n \cdot dp[n - p_{h + 1}][h]$ .

entonces sabemos que $K_n \leq h$ .

Demostración: Claramente, si $p_{h + 1} > n$ , no podemos usarlo ni ninguno de los primos siguientes, así que $dp[n][h + 1] = dp[n][h]$ . Asumamos en cambio que solo se cumple la segunda condición.

Ahora demostraremos por inducción que para $k' > h$ , tenemos $dp[n][k'] = dp[n][h]$ . Asumamos que $dp[n][k' - 1] = dp[n][h]$ . Si $p_{k'} > n$ , entonces hemos terminado. Asumamos que $p_{k'} \leq n$ . Consideremos algún $\alpha$ tal que $p_{k'}^\alpha \leq n$ . Como $h \geq \overline{K_{n - 1}}$ , tenemos:

p_{k'}^\alpha \cdot dp[n - p_{k'}^\alpha][k' - 1] = p_{k'}^\alpha \cdot dp[n - p_{k'}^\alpha][h]

$k' > h$ , así que sabemos que $n - p_{k'}^\alpha \leq n - p_{h + 1}$ . Además, como $dp[n][k] \leq dp[n'][k]$ cuando $n \leq n'$ , tenemos:

p_{k'}^\alpha \cdot dp[n - p_{k'}^\alpha][h] \leq p_{k'}^\alpha \cdot dp[n - p_{h + 1}][h]

Así obtenemos:

p_{k'}^\alpha \cdot dp[n - p_{h + 1}][h] \leq n \cdot dp[n - p_{h + 1}][h] \leq dp[n][h]

Por la hipótesis inductiva, tenemos $dp[n][h] = dp[n][k' - 1]$ , así que obtenemos:

p_{k'}^\alpha \cdot dp[n - p_{k'}^\alpha][k' - 1] \leq dp[n][k' - 1]

y por lo tanto podemos concluir que $dp[n][k'] = dp[n][k' - 1] = dp[n][h]$ . Por lo tanto, por inducción, $K_n \leq h$ .

Usando este lema, podemos escribir un algoritmo auxiliar para hallar que $\overline{K_n} = 70$ .

Esto mejora significativamente nuestro uso de memoria, así que nuestra solución ahora usa solo $\mathcal{O}(70 n)$ tiempo y memoria.


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 1e4, MAX_P = 70;
 
bool composite[MAX_N + 1];
vector<int> primes = {2,   3,   5,   7,   11,  13,  17,  19,  23,  29,  31,  37,
                      41,  43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89,
                      97,  101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
                      157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
                      227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
                      283, 293, 307, 311, 313, 317, 331, 337, 347, 349};
 
double mem[MAX_N + 1][MAX_P];
bool visited[MAX_N + 1][MAX_P];
int backtrack[MAX_N + 1][MAX_P];
 
double dp(int n, int pos = 0) {
	if (pos == primes.size() || primes[pos] > n) return 0;
	if (visited[n][pos]) return mem[n][pos];
 
	double ans = dp(n, pos + 1);
	backtrack[n][pos] = 0;
	for (int p_pow = primes[pos], expo = 1; p_pow <= n; p_pow *= primes[pos], expo++) {
		double potential = expo * log(primes[pos]) + dp(n - p_pow, pos + 1);
		if (ans < potential) {
			ans = potential;
			backtrack[n][pos] = p_pow;
		}
	}
	visited[n][pos] = true;
	return mem[n][pos] = ans;
}
 
int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		int m;
		scanf("%d", &m);
		dp(m);
		vector<int> lens;
		for (int pos = 0; pos < primes.size(); m -= backtrack[m][pos++]) {
			if (backtrack[m][pos]) lens.push_back(backtrack[m][pos]);
		}
		while (m--) lens.push_back(1);
		sort(lens.begin(), lens.end());
		for (int i = 0, j = 1; i < lens.size(); j += lens[i++]) {
			for (int k = 1; k < lens[i]; k++) printf("%d ", j + k);
			printf("%d ", j);
		}
		printf("\n");
	}
	return 0;
}

Alternativamente, se puede notar que se puede eliminar la segunda dimensión del arreglo de DP y que los bitsets usan 8 veces menos memoria que los arreglos de booleanos. Esto significa que se puede recortar el uso de memoria sin limitar la cantidad de números primos que se comprueban.

Aquí está el código de Ben, que implementa esta idea:


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define tcT template <class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT > using V = vector<T>;
tcT, size_t SZ > using AR = array<T, SZ>;
tcT > using PR = pair<T, T>;
 
// pairs
#define mp make_pair
#define f first
#define s second
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
tcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
 
// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define trav(a, x) for (auto &a : x)
 
const int MOD = 1e9 + 7;  // 998244353;
const int MX = 2e5 + 5;
const ll INF = 1e18;  // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};  // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
 
// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); }  // # of bits set
constexpr int bits(int x) {  // assert(x >= 0); // make C++11 compatible until
	                         // USACO updates ...
	return x == 0 ? 0 : 31 - __builtin_clz(x);
}  // floor(log2(x))
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }
 
ll cdiv(ll a, ll b) {
	return a / b + ((a ^ b) > 0 && a % b);
}  // divide a by b rounded up
ll fdiv(ll a, ll b) {
	return a / b - ((a ^ b) < 0 && a % b);
}  // divide a by b rounded down
 
tcT > bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }  // set a = min(a,b)
tcT > bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
tcTU > T fstTrue(T lo, T hi, U f) {
	hi++;
	assert(lo <= hi);  // assuming f is increasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo) / 2;
		f(mid) ? hi = mid : lo = mid + 1;
	}
	return lo;
}
tcTU > T lstTrue(T lo, T hi, U f) {
	lo--;
	assert(lo <= hi);  // assuming f is decreasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo + 1) / 2;
		f(mid) ? lo = mid : hi = mid - 1;
	}
	return lo;
}
tcT > void remDup(vector<T> &v) {  // sort and remove duplicates
	sort(all(v));
	v.erase(unique(all(v)), end(v));
}
tcTU > void erase(T &t, const U &u) {  // don't erase
	auto it = t.find(u);
	assert(it != end(t));
	t.erase(it);
}  // element that doesn't exist from (multi)set
 
// INPUT
#define tcTUU tcT, class... U
tcT > void re(complex<T> &c);
tcTU > void re(pair<T, U> &p);
tcT > void re(V<T> &v);
tcT, size_t SZ > void re(AR<T, SZ> &a);
 
tcT > void re(T &x) { cin >> x; }
void re(db &d) {
	str t;
	re(t);
	d = stod(t);
}
void re(ld &d) {
	str t;
	re(t);
	d = stold(t);
}
tcTUU > void re(T &t, U &...u) {
	re(t);
	re(u...);
}
 
tcT > void re(complex<T> &c) {
	T a, b;
	re(a, b);
	c = {a, b};
}
tcTU > void re(pair<T, U> &p) { re(p.f, p.s); }
tcT > void re(V<T> &x) { trav(a, x) re(a); }
tcT, size_t SZ > void re(AR<T, SZ> &x) { trav(a, x) re(a); }
tcT > void rv(int n, V<T> &x) {
	x.rsz(n);
	re(x);
}
 
// TO_STRING
#define ts to_string
str ts(char c) { return str(1, c); }
str ts(const char *s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) {
#ifdef LOCAL
	return b ? "true" : "false";
#else
	return ts((int)b);
#endif
}
tcT > str ts(complex<T> c) {
	stringstream ss;
	ss << c;
	return ss.str();
}
str ts(V<bool> v) {
	str res = "{";
	F0R(i, sz(v)) res += char('0' + v[i]);
	res += "}";
	return res;
}
template <size_t SZ> str ts(bitset<SZ> b) {
	str res = "";
	F0R(i, SZ) res += char('0' + b[i]);
	return res;
}
tcTU > str ts(pair<T, U> p);
tcT > str ts(T v) {  // containers with begin(), end()
#ifdef LOCAL
	bool fst = 1;
	str res = "{";
	for (const auto &x : v) {
		if (!fst) res += ", ";
		fst = 0;
		res += ts(x);
	}
	res += "}";
	return res;
#else
	bool fst = 1;
	str res = "";
	for (const auto &x : v) {
		if (!fst) res += " ";
		fst = 0;
		res += ts(x);
	}
	return res;
 
#endif
}
tcTU > str ts(pair<T, U> p) {
#ifdef LOCAL
	return "(" + ts(p.f) + ", " + ts(p.s) + ")";
#else
	return ts(p.f) + " " + ts(p.s);
#endif
}
 
// OUTPUT
tcT > void pr(T x) { cout << ts(x); }
tcTUU > void pr(const T &t, const U &...u) {
	pr(t);
	pr(u...);
}
void ps() { pr("\n"); }  // print w/ spaces
tcTUU > void ps(const T &t, const U &...u) {
	pr(t);
	if (sizeof...(u)) pr(" ");
	ps(u...);
}
 
// DEBUG
void DBG() { cerr << "]" << endl; }
tcTUU > void DBG(const T &t, const U &...u) {
	cerr << ts(t);
	if (sizeof...(u)) cerr << ", ";
	DBG(u...);
}
#ifdef LOCAL  // compile with -DLOCAL, chk -> fake assert
#define dbg(...)                                                                       \
	cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define chk(...)                                                                       \
	if (!(__VA_ARGS__))                                                                \
		cerr << "Line(" << __LINE__ << ") -> function(" << __FUNCTION__                \
		     << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n",                   \
		    exit(0);
#else
#define dbg(...) 0
#define chk(...) 0
#endif
 
void setPrec() { cout << fixed << setprecision(15); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
// FILE I/O
void setIn(str s) { freopen(s.c_str(), "r", stdin); }
void setOut(str s) { freopen(s.c_str(), "w", stdout); }
void setIO(str s = "") {
	unsyncIO();
	setPrec();
	// cin.exceptions(cin.failbit);
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) setIn(s + ".in"), setOut(s + ".out");  // for USACO
}
 
array<ld, 10001> ans, tmp;
bitset<10001> z[1300];
bool pri[10001];
vi co, CO;
 
void fin(int x) {
	pi cur = {x, sz(co) - 1};
	vi zz;
	int lastUse = 0;
	while (cur.s != -1) {
		if (z[cur.s][cur.f] && lastUse != CO[cur.s]) {
			lastUse = CO[cur.s];
			cur.f -= co[cur.s];
			zz.pb(co[cur.s]);
		}
		cur.s--;
	}
	sort(all(zz));
	int sum = 0;
	trav(t, zz) sum += t;
	vi ret;
	sum = x - sum;
	F0R(i, sum) ret.pb(i + 1);
	trav(t, zz) {
		FOR(j, sum, sum + t - 1) ret.pb(j + 2);
		ret.pb(sum + 1);
		sum += t;
	}
	trav(z, ret) pr(z, ' ');
	ps();
}
 
int main() {
	setIO();
	int d;
	re(d);
	vi v(d);
	re(v);
	int mx = 0;
	trav(t, v) ckmax(mx, t);
	FOR(i, 2, mx + 1) pri[i] = 1;
	F0R(i, mx + 1) ans[i] = 1;
	FOR(i, 2, mx + 1) if (pri[i]) {
		tmp = ans;
		for (int j = 2 * i; j <= mx; j += i) pri[j] = 0;
		for (int j = 1; pow(i, j) <= mx; j++) {
			int x = pow(i, j);
			FOR(k, x, mx + 1) {
				if (x * ans[k - x] > tmp[k]) {
					tmp[k] = x * ans[k - x];
					z[sz(co)][k] = 1;
					// ps("WUT",sz(co),k);
				}
			}
			co.pb(x);
			CO.pb(i);
		}
		swap(ans, tmp);
	}
	trav(x, v) fin(x);
}