•Tutorial•14 days ago

Educational Round #1 — Editorial

Hogwarts is hosting its traditional annual Magic Theory Olympiad for first-year students. The school's caretaker, Argus Filch, has been tasked with assigning students to classrooms.

Each of the four houses has sent its best students to the Olympiad: $g$ students from Gryffindor, $s$ from Slytherin, $h$ from Hufflepuff, and $r$ from Ravenclaw. Filch has $m$ classrooms at his disposal.

Each classroom is enchanted with an expansion charm, so it can accommodate any number of students. However, it must be taken into account that students from the same house, when placed in the same room, might take the opportunity to cheat by sharing ideas on how to solve the tasks. Therefore, the number of students from the same house in any single classroom should be minimized.

We define an optimal seating arrangement as one that minimizes the maximum number of students from the same house in any classroom.

Determine the minimum possible number of students from the same house that Filch will have to place in the same classroom, even under an optimal seating arrangement.

Input. The first line contains four integers $g, s, h,$ and $r (1 \leq g, s, h, r \leq 1000)$ — the number of students representing Gryffindor, Slytherin, Hufflepuff, and Ravenclaw, respectively.

The second line contains a single integer $m (1 \leq m \leq 1000)$ — the number of available classrooms.

Output. Print a single integer — the minimum possible number of students from the same house that will have to be placed in the same classroom, even with an optimal arrangement.

Open problem

Note that if the numbers $n$ and $n - 3$ are placed in one group, and $n - 1$ and $n - 2$ are placed in the other (so that the sum of numbers in each group is equal), the problem reduces to a similar problem of smaller size, namely, dividing the numbers $1, 2, ..., n - 4$ into two groups.

For $n \leq 3$ , the numbers are divided into groups as follows:

If three numbers $1, 2, 3$ remain, they can be divided into two groups: ${1, 2}$ and ${3}$ .
If two numbers $1, 2$ remain, they can be divided into groups: ${1}$ и ${2}$ . The difference between the sums of the groups will be $1$ .
If one number $1$ remains, it can be placed in either group. The difference between the sums of the groups will be $1$ .

If the sum of all numbers from $1$ to $n$ is even, they can be divided into two groups with equal sums.

If the sum of all numbers from $1$ to $n$ is odd, they can be divided into two groups with a sum difference of $1$ .

Example

Let $n = 10$ . The numbers are placed into groups as follows:

Let $n = 11$ . The numbers are placed into groups as follows:

To store the values $A_{i} (i < 5000000)$ , declare an array $m$ .

#define MAX 5000000
long long m[MAX];

The function f computes the value of $A_{n}$ .

long long f(long long n, long long p, long long q, 
            long long x, long long y)
{

If $n \leq 0$ , then $A_{n} = 1$ .

  if (n <= 0) return 1;

If $n < 5000000$ and the value $m [n]$ is already computed (is not zero), return it.

  if ((n < MAX) && m[n]) return m[n];

Perform a recursive computation of $A_{n}$ according to the formula provided in the problem statement.

  long long temp = f(n/p-x,p,q,x,y) + f(n/q-y,p,q,x,y);

If $n < 5000000$ , store the result $A_{n}$ in the array $m$ to avoid repeated computations in the future.

  if (n < MAX) m[n] = temp;
  return temp;
}

The main part of the program. Read the input data.

scanf("%lld %lld %lld %lld %lld",&n,&p,&q,&x,&y);

Compute and print the answer.

res = f(n,p,q,x,y);
printf("%lld\n",res);

Let’s consider the values that the expression $f (i, j) = i / n - j / m$ takes, where $i, j \in Z$ for fixed $n$ and $m$ . For example, $f (n, m) = n / n - m / m = 0$ .

Let’s consider, for instance, the function $f (i, j) = i /3 - j /5$ . Then

f (i, j) = \frac{5 i - 3 j}{15}

According to the extended Euclidean algorithm, there always exist integers $i$ and $j$ , such that $i /3 - j /5 = 1$ . Therefore, the smallest positive value that the expression $i /3 - j /5$ can take is $1/15$ . From this, it follows that this expression can take all possible values of the form $k /15$ , where $k \in Z$ .

Theorem. If $f (i, j) = i / n - j / m$ , then this function takes values of the form $k / L CM (n, m)$ , where $k \in Z$ .

Proof. Indeed,

f (i, j) = i / n - j / m = \frac{i \cdot m - j \cdot n}{n \cdot m} = \frac{( i \cdot m ) / GC D ( n , m ) - ( j \cdot n ) / GC D ( n , m )}{( n \cdot m ) / GC D ( n , m )} = \frac{i \cdot ( m / GC D ( n , m )) - j \cdot ( n / GC D ( n , m ))}{L CM ( n , m )}

Since the numbers $m / GC D (n, m)$ and $n / GC D (n, m)$ are coprime, there always exists integers $i$ and $j$ such that the numerator of the fraction equals $1$ . Therefore, the function $f (i, j)$ can take all possible values of the form $k / L CM (n, m)$ , where $k \in Z$ .

Now let's consider the original function

f (t) = mi n_{i, j \in Z} ∣ \frac{i}{n} - \frac{j}{m} + t ∣

Its values are the distances from the point $t$ to the nearest point of the form $k / L CM (n, m)$ , where $k \in Z$ . To maximize the function $f (t)$ , the value of $t$ should be chosen so that it is exactly in the middle between the neighboring points $k / L CM (n, m)$ and $(k + 1) / L CM (n, m)$ , where $k$ is an integer. The value of the function at such a point is $1/2 \cdot L CM (n, m)$ , which will be the answer.

Example

Let $f (t) = mi n_{i, j \in Z} ∣ \frac{i}{3} - \frac{j}{5} + t ∣$ . It is obvious that $f (0) = 0$ . The equality $f (1/15) = 0$ holds because there exist integers $i$ and $j$ such that $i /3 - j /5 = - 1/15$ (for example, $i = 1, j = 2$ ). From this, it also follows that $f (k /15) = 0$ , where $k \in Z$ .

However, $f (k /15 + 1/30) = 1/30$ , and this will be the maximum value of the function, as the point $k /15 + 1/30$ is at the maximum distance from the zeros of the function.

Divide the input array into two equal parts: $t_{1}, t_{2}, ..., t_{n /2}$ and $t_{n /2 + 1}, t_{n /2 + 2}, ..., t_{n}$ . Store the first part in array $a$ and the second in array $b$ .

First, solve the problem for sequence $a$ . Iterate over all possible subsets of $a$ (there will be at most $2^{20}$ of them). For each subset, calculate the sum of its elements $s$ , and increment the value $m [s]$ by $1$ . As the data structure $m$ , we can use, for example, an unordered_map. Thus, $m [s]$ will contain the number of ways to choose a subset from array $a$ whose elements sum to $s$ .

Then, iterate over all subsets of array $b$ . Let $s u m$ be the sum of elements in one such subset. If we combine this subset with all subsets of array $a$ whose sum is equal to $s - s u m$ , the result will be a subset of the original array whose elements sum to $s$ .

Example

Let's consider the second example. Divide the input sequence into two parts:

$a = (1, 3, 2)$ ,
$b = (2, 1, 4)$

Iterate over all subsets of the set $a = {1, 3, 2}$ :

${1} : s u m = 1, m [1] + +$ ;	${1, 2} : s u m = 3, m [3] + +$ ;
${3} : s u m = 3, m [3] + +$ ;	${3, 2} : s u m = 5, m [5] + +$ ;
${2} : s u m = 2, m [2] + +$ ;	${1, 3, 2} : s u m = 6, m [6] + +$ ;
${1, 3} : s u m = 4, m [4] + +$ ;	${} : s u m = 0, m [0] + +$ ;

The structure $m$ will contain the following values after processing:

Now, iterate over all subsets of the set $b = {2, 1, 4}$ . In this example, the target sum is $s = 7$ . For each sum $s u m$ corresponding to a subset of $b$ , add $m [s - s u m]$ to the final answer.

${2} : s u m = 2, m [7 - 2] = m [5] = 1$ ;
${1} : s u m = 1, m [7 - 1] = m [6] = 1$ ;
${4} : s u m = 4, m [7 - 4] = m [3] = 2$ ;
${2, 1} : s u m = 3, m [7 - 3] = m [4] = 1$ ;
${2, 4} : s u m = 6, m [7 - 6] = m [1] = 1$ ;
${1, 4} : s u m = 5, m [7 - 5] = m [2] = 1$ ;
${2, 1, 4} : s u m = 7, m [7 - 7] = m [0] = 1$ ;
${} : s u m = 0, m [7 - 0] = m [7] = 0$ ;

The target sum is $1 + 1 + 2 + 1 + 1 + 1 + 1 + 0 = 8$ , which is the final answer.

Declare the data structures.

vector<int> a, b;
unordered_map<long long, long long> m;

Read the input data. Store the first half of the sequence in array $a$ , and the second half in array $b$ .

scanf("%d %d", &n, &s);
a.resize(n / 2);
for (i = 0; i < n / 2; i++)
  scanf("%d", &a[i]);

b.resize(n - n / 2);
for (i = n / 2; i < n; i++)
  scanf("%d", &b[i - n / 2]);

Iterate over all subsets of sequence $a$ and compute the sum of their elements. In the unordered_map structure, keep track of how many times each sum occurs among these subsets. If $s u m$ is the sum of the current subset, then increment $m [s u m]$ by $1$ .

for (i = 0; i < (1 << a.size()); i++)
{
  sum = 0;

The variable $i$ contains the bitmask of the current subset of $a$ . The sum of its elements is computed in the variable $s u m$ .

      for (j = 0; j < a.size(); j++)
        if (i & (1 << j)) sum += a[j];

For each obtained sum $s u m$ , increment the value of $m [s u m]$ by $1$ .

  m[sum]++;
}

The number of ways to obtain the sum $s$ from the elements of the original array is counted in the variable $res$ .

res = 0;

Iterate over all subsets of sequence $b$ .

for (i = 0; i < (1 << b.size()); i++)
{
  sum = 0;

The variable $i$ contains the bitmask of the current subset of $b$ . The sum of the elements in this subset is computed in the variable $s u m$ .

  for (j = 0; j < b.size(); j++)
    if (i & (1 << j)) sum += b[j];

If we combine the current subset of set $b$ , whose sum of elements is $s u m$ , with all subsets of set a whose sum is $s - s u m$ , the result will be a subset of the original array whose sum of elements is equal to $s$ .

  if (m.count(s - sum) > 0) res += m[s - sum];
}

Print the answer.

printf("%lld\n", res);

Genetic scientists from the planet Olympia are once again conducting experiments with the DNA of primitive organisms. The genome of an organism is a sequence of genes, each of which can be encoded by a natural number. Genes encoded by the same number are considered identical, while genes encoded by different numbers are considered different.

The scientists have already created a primitive organism and want to modify its genome in such a way as to produce an ideal organism. They believe that this will help develop cures for many diseases in the future.

An organism is considered ideal if any two identical genes are either located on adjacent positions in the genome or have at least one identical gene between them.

In one operation, scientists can select one or more identical genes in the genome, remove them, and then place them back into the genome, possibly at different positions. Since each such operation weakens the organism, the scientists aim to minimize the number of operations needed to achieve their goal.

Write a program that, given a representation of the genome, determines the minimum number of operations required to create an ideal organism.

Input. The first line contains the number of genes $n (1 \leq n \leq 1 0^{5})$ in the genome of a primitive organism. The second line contains $n$ positive integers, each of which does not exceed $n$ — the sequence of genes in the genome.

Output. Print the minimum number of operations required to create an ideal organism.

Open problem

The gene rearrangement should be performed in such a way that identical genes are placed next to each other. At the same time, it is necessary to minimize the number of operations performed.

For each positive integer $a_{i}$ , we associate an interval $[s_{i}; e_{i}]$ , where $s_{i}$ is the position where $a_{i}$ first appears, and $e_{i}$ is the position where $a_{i}$ appears for the last time.

Let $res$ be the maximum possible number of non-overlapping intervals. This value can be found using the "activity-selection" algorithm, which means that each of the remaining intervals overlaps with at least one of the selected intervals. After this, the described procedure should be applied to the genes corresponding to these intervals.

If $k$ is the total number of constructed intervals, then the answer to the problem will be $k - res$ .

Example

For the given example, the intervals will look like this (position numbering starts from zero):

for $1 : [0; 4]$ ;
for $2 : [1; 6]$ ;
for $3 : [3; 5]$ ;
for $4 : [7; 7]$ ;
for $5 : [8; 8]$ ;

Let's sort the intervals by their end coordinate:

[0; 4], [3; 5], [1; 6], [7; 7], [8; 8]

The maximum number of non-overlapping intervals is $3$ . For example, we can select the intervals $[0; 4], [7; 7], [8; 8]$ . For the genes corresponding to the remaining intervals, the procedure described in the problem statement should be applied. The corresponding genes are $2$ and $3$ . Two rearrangements can be performed, for example, as follows:

Let $M A X$ be the maximum possible number of genomes in the input sequence.

#define MAX 100001

The vector of pairs $v$ stores the segments $[s_{i}; e_{i}]$ .

vector<pair<int, int> > v;
int s[MAX], e[MAX];

Read the input data. Initialize $s_{i} = - 1, e_{i} = - 1$ .

scanf("%d", &n);
memset(s, -1, sizeof(s));
memset(e, -1, sizeof(e));

for (i = 0; i < n; i++)
{
  scanf("%d", &x);

If the number $x$ appears for the first time, record its position in the input sequence in $s_{x}$ .

  if (s[x] == -1) s[x] = i;

If the number $x$ does not appear for the first time, record its position in $e_{x}$ , assuming that $x$ appears for the last time.

  if (i > e[x]) e[x] = i;
}

All the constructed intervals are stored in the vector $v$ .

for (i = 1; i <= n; i++) // numbers 1..n
  if (s[i] != -1) v.push_back(make_pair(e[i], s[i]));

The intervals are stored in the vector in reverse order (in the form $[e_{i}; s_{i}]$ ) so that, by default, the intervals are sorted in ascending order of their ends.

sort(v.begin(), v.end());

Find the maximum number $res$ of non-overlapping intervals.

i = res = 0;
while (i < v.size())
{

Add the $i$ -th interval to the set of non-overlapping intervals. The variable $t e m p$ holds the end of this interval (let's call it the current interval).

  res++; temp = v[i++].first; // end

As long as the start of the next interval is less than the end of the current interval, skip such an interval, as it overlaps with the current one.

  while (i < v.size() && v[i].second < temp) i++;
}

Print the answer.

printf("%d\n", v.size() - res);

The army of the Polish–Lithuanian Commonwealth is marching from the city of Kostroma to the village of Domnino. The army is led by two hetmans — Stefan and Konstantin.

Stefan has a map of the Kostroma region, which shows all the roads between villages. Each night, he leads the army from one village to another using one of these roads. Konstantin, on the other hand, has obtained a map of secret trails, and during the day, he leads the army along one of these paths. Before each movement, each hetman consults the guide, Ivan Susanin, to determine the best route.

Stefan's map shows the length of each road, so he can calculate the shortest distance from any village to Domnino using his map. Similarly, Konstantin knows the shortest distances according to his map of trails.

Ivan Susanin, being a secret agent, wants to avoid raising suspicion. Therefore, each time he selects a road (for Stefan) and a trail (for Konstantin) such that the shortest distance to the village of Domnino, according to the respective hetman's map, strictly decreases.

Help Ivan determine the maximum possible length of the route to the village of Domnino.

Input. The first line contains three integers $n$ , $s$ , and $t (2 \leq n \leq 1000, 1 \leq s, t \leq n)$ — the number of villages in the Kostroma region, the starting village number, and the village number of Domnino, respectively. Villages are numbered from $1$ to $n$ . It is guaranteed that $s \neq = t$ .

Then follow two blocks, each describing a map: the first block is Stefan’s map, the second one is Konstantin’s.

The first line of each block contains an integer $m (n - 1 \leq m \leq 1 0^{5})$ — the number of roads or trails. Each of the following $m$ lines contains three integers $a$ , $b$ , and $l (1 \leq a, b \leq n; 1 \leq l \leq 1 0^{6})$ describing a connection between villages $a$ and $b$ of length $l$ .

Movement along roads and trails is allowed in both directions. It is guaranteed that each map allows travel between any pair of villages. The army begins its journey in the evening from village $s$ , traveling one road per night and one trail per day.

Output. Print a single integer — the maximum possible length of the route to village Domnino (considering alternating road and trail movement). If Ivan Susanin can lead the army indefinitely without reaching Domnino, print " $- 1$ ".

Open problem

Сonstruct two graphs: the road graph $g [0]$ and the trail graph $g [1]$ . Next, compute the shortest distances from the village Domnino $t$ to all villages:

According to Stefan's map: $d [0] [i]$ — the minimum distance from $t$ to village $i$ ;
According to Konstantin's map: $d [1] [i]$ — the minimum distance from $t$ to village $i$ ;

Then consider a graph whose vertices are pairs $(v, p a r i t y)$ :

$v$ — the village number;
$p a r i t y = 0$ (night, movement along roads), $p a r i t y = 1$ (day, movement along trails).

The army starts its journey in the evening from the initial village, moving at night along a road $(p a r i t y = 0)$ . Run a depth-first search from the vertex $(s, 0)$ following these rules:

from $(v, 0)$ (night) go along a road to $(u, 1)$ if $d [0] [u] < d [0] [v]$ ;
from $(v, 1)$ (day) go along a trail to $(u, 0)$ if $d [1] [u] < d [1] [v]$ .

Being in the state $(v, p a r i t y)$ , consider only allowed transitions — that is, those for which the distance to Domnino strictly decreases. Among these, look for the path of maximum length.

Recall that each of the hetmans tries to move so that the distance according to their own map decreases (however, they are not required to follow the shortest path).

During the depth-first search, maintain the following dynamic programming state:

$d p [t y p e] [v]$ — the maximum length of a path from $v$ to $t$ , starting from phase $t y p e$ .

For each allowed transition:

Recursively call $df s (t o, t y p e \oplus 1)$ — transition to the opposite phase.
Update the value of $d p [t y p e] [v]$ :

d p [t y p e] [v] = ma x (d p [t y p e] [v], d p [t y p e \oplus 1] [t o] + w e i g h t);

Thus, we choose the best next move that leads to the maximum total path length. This is analogous to the standard longest path search in a DAG (directed acyclic graph), where the direction of edges is determined by the decrease in shortest distance.

Movement is allowed only along edges leading to vertices with a smaller distance to Domnino. However, the problem involves two graphs — two types of edges: roads and trails — and transitions between them alternate: night (road), day (trail), night, day, and so on. It is precisely because of this alternation of maps (roads and trails) that a cycle may arise between vertices, even though in each individual graph (for one map) the movement always goes along decreasing distances.

If during the depth-first search we encounter a vertex that is already in the processing stack, it means a cycle has been detected.

Declare the constants.

#define INF 2e18
#define MAXN 1005

Let's declare the data structures used:

$g [0]$ and $g [1]$ — adjacency lists for the road and trail graphs, respectively.
$d [0]$ and $d [1]$ — shortest distances from the village Domnino $t$ to all other villages.
$d p [0]$ and $d p [1]$ — the maximum path length from vertex $v$ to $t$ , if starting from $v$ along the road $(t y p e = 0)$ or along the trail $(t y p e = 1)$ .
$u se d [0]$ and $u se d [1]$ — vertex visitation markers for depth-first search in the road and trail graphs, respectively.

vector<pair<int, int>> g[2][MAXN];
long long d[2][MAXN];
long long dp[2][MAXN];
int used[2][MAXN];

The function dijkstra calculates the shortest distances from the village Domnino $t$ to all other villages either along the roads $(t y p e = 0)$ or along the trails $(t y p e = 1)$ .

void dijkstra(int type)
{
  for (int i = 1; i <= n; i++)
    d[type][i] = INF;

  d[type][t] = 0;

  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  pq.push({ 0, t });

  while (!pq.empty())
  {
    pair<long long, int> top = pq.top();
    pq.pop();

    long long dist = top.first;
    int v = top.second;

    if (dist > d[type][v]) continue;

    for (auto edge : g[type][v])
    {
      int to = edge.first;
      int w = edge.second;

      if (d[type][to] > d[type][v] + w)
      {
        d[type][to] = d[type][v] + w;
        pq.push({ d[type][to], to });
      }
    }
  }
}

The dfs function performs a depth-first search and finds the longest path while moving through alternating maps, starting from village $v$ along the road $(t y p e = 0)$ or along the trail $(t y p e = 1)$ . If during such alternating movement a cycle is detected, the function returns $- 1$ .

void dfs(int v, int type)
{

Vertex $v$ in the graph $g [t y p e]$ is marked as gray.

  used[type][v] = 1;

Initialize the dynamic programming state.

  dp[type][v] = 0;

Iterate over the edges outgoing from vertex $v$ in the graph $g [t y p e]$ .

  for (auto edge : g[type][v])
  {
    int to = edge.first;
    int weight = edge.second;

A transition from vertex $v$ to vertex $t o$ is allowed only if the distance from $t o$ to Domnino is less than the distance from $v$ to Domnino.

    if (d[type][to] < d[type][v])
    {

If the vertex $t o$ in the graph $g [t y p e \oplus 1]$ is already in the process of being visited (marked as "gray"), then a cycle has been detected — return $- 1$ .

      if (used[type ^ 1][to] == 1)
      {
        cout << -1 << endl;
        exit(0);
      }

If the vertex $t o$ in the graph $g [t y p e \oplus 1]$ has not yet been visited, continue the depth-first search from it.

      if (used[type ^ 1][to] == 0)
        dfs(to, type ^ 1);

After processing all allowed transitions, update the dynamic programming state by selecting the maximum path length from vertex $v$ in the graph $g [t y p e]$ to Domnino.

      dp[type][v] = max(dp[type][v], dp[type ^ 1][to] + weight);
    }
  }

Vertex $v$ in the graph $g [t y p e]$ is marked black.

  used[type][v] = 2;
}

The main part of the program. Read the input data and construct the road and trail graphs.

scanf("%d %d %d", &n, &s, &t);
scanf("%d", &m1);
for (i = 0; i < m1; i++)
{
  scanf("%d %d %d", &a, &b, &len);
  g[0][a].push_back({ b, len });
  g[0][b].push_back({ a, len });
}

scanf("%d", &m2);
for (i = 0; i < m2; i++)
{
  scanf("%d %d %d", &a, &b, &len);
  g[1][a].push_back({ b, len });
  g[1][b].push_back({ a, len });
}

Calculate the shortest distances from the village Domnino $t$ to all other villages — separately for the road map and for the trail map.

dijkstra(0);
dijkstra(1);

Using depth - first search, find the longest path while moving through alternating maps, starting from the village $s$ along the road.

dfs(s, 0);

Print the answer. The starting point is village $s$ , and the movement begins on the road.

printf("%lld\n", dp[0][s]);

Alice is a magician, and she creates a new trick. She has $n$ cards with different numbers from $1$ to $n$ written on them. First, she asks an audience member to shuffle the deck and put the cards in a row. Let the number on the $i$ -th card from the left be $a_{i}$ .

Then Alice selects two permutations $p$ and $q$ . There is a restriction on $p$ and $q$ : permutations can’t have fixed points. In other words, $\forall i : p_{i} \neq = i$ and $q_{i} \neq = i$ .

Once permutations are chosen, Alice shuffles the cards according to them. Now the $i$ -th card from the left becomes the card $a [p [q [i]]$ . The trick is considered successful if, after shuffling, the number on the $i$ -th card from the left is $i$ .

Help Alice choose the permutations $p$ and $q$ , or determine if it is impossible for the given starting permutation $a$ .

Input. The first line contains the number of test cases $t (1 \leq t \leq 1 0^{5})$ .

Each test is described in two lines. The first line contains one integer $n (1 \leq n \leq 1 0^{5})$ — the number of cards. The second line contains $n$ integers $a_{i} (1 \leq a_{i} \leq n, \forall i \neq = j : a_{i} \neq = a_{j})$ — the initial permutation of the cards.

It is guaranteed that the sum of $n$ over all tests does not exceed $1 0^{5}$ .

Output. Print the answer for each test case in the order they appear in the input.

For each test case, print “Impossible” on a single line if no solution exists.

Otherwise, print "Possible" on the first line, followed by two lines containing the permutations $p$ and $q$ .

Open problem

Let’s consider three permutations: $a, p$ , and $q$ . Let $I$ be the identity permutation. Consider the equation: $a (p (q (I))) = I$ . From this, we get $p (q (I)) = a^{- 1}$ . Using the fact that permutations are applied from right to left, this identity can be rewritten as: $p ° q = a^{- 1}$ . Therefore, $q = p^{- 1} ° a^{- 1}$ .

Generate a random permutation $p$ that has no fixed points. Then, compute the permutation $q = p^{- 1} ° a^{- 1}$ and check that it has no fixed points. The found permutations $p$ and $q$ are the required ones.

Example

Consider the permutation $a = (5, 1, 4, 2, 3)$ .

Its inverse will be $a^{- 1} = (2, 4, 5, 3, 1)$ .

Generate a random permutation $p$ with no fixed points. For example, let $p = (4, 1, 2, 5, 3)$ . Now, let's compute its inverse: $p^{- 1} = (2, 3, 5, 1, 4)$ .

Next, compute $q = p^{- 1} ° a^{- 1} = (2, 3, 5, 1, 4) ° (2, 4, 5, 3, 1) = (3, 1, 4, 5, 2)$ . The permutation $q$ has no fixed points, so it is valid.

The print function prints the elements of the array $a$ , starting from the first one.

void print(vector<int>& a)
{
  for (int i = 1; i < a.size(); i++)
    printf("%d ", a[i]);
  printf("\n");
}

The function is_valid checks whether the permutation $v$ contains any fixed points.

bool is_valid(vector<int>& v)
{
  for (int i = 1; i < v.size(); i++)
    if (v[i] == i) return false;
  return true;
}

Declare the arrays.

vector<int> a, p, p1, q;

The main part of the program. Read the input data.

scanf("%d", &tests);
while (tests--)
{
  scanf("%d", &n);

Initialize the arrays.

  a.resize(n + 1);
  p1.resize(n + 1);
  p.resize(n + 1);
  q.resize(n + 1);

Read the input permutation $a$ and immediately store its inverse in the array $a$ . That is, the array $a$ contains the permutation $a^{- 1}$ , where $a$ is the input permutation.

  for (i = 1; i <= n; i++)
  {
    scanf("%d", &x);
    a[x] = i;
  }

mt19937 is one of the standard pseudorandom number generators in C++ (Mersenne Twister with a period of 19937). It is very fast and has good statistical properties, making it an excellent choice for most tasks requiring random number generation.

  mt19937 gen(random_device{}());

In the variable $f o u n d$ , we'll mark whether a solution is found for the current test.

  found = false;

Perform $1000$ iterations.

  for (it = 0; it < 1000; it++)
  {

Generate a random permutation. To do this, populate the array $p$ with the numbers $0, 1, 2, ...$ , and use the shuffle function to shuffle the elements, starting from the first (non-zero) element. We work with permutations from $1$ to $n$ .

    iota(p.begin(), p.end(), 0);
    shuffle(p.begin() + 1, p.end(), gen);

Check whether the permutation $p$ is valid (i.e., it contains no fixed points).

    if (!is_valid(p)) continue;

Compute the permutation $p_{1} = p^{- 1}$ .

    for (i = 1; i <= n; i++)
      p1[p[i]] = i;

Compute the permutation $q = p_{1} ° a^{- 1} = p^{- 1} ° a^{- 1}$ .

    for (i = 1; i <= n; i++)
      q[i] = p1[a[i]];

If the permutation $q$ is valid, print the result.

    if (is_valid(q))
    {
      puts("Possible");
      print(p);
      print(q);
      found = true;
      break;
    }
  }

If no solution is found after $1000$ iterations, then no solution exists.

  if (!found) puts("Impossible");
}

Comments

Nothing yet

Be the first one to start the conversation!

Loading

Just a moment, getting data from the server