Connection Status:
Competition Arena > PerfectPermutationHard

PerfectPermutationHard

SRM 441 · 2009-05-27 · by giolekva

SRM 441 · 2009-05-27 · by giolekva · Greedy, Simple Math, Simple Search, Iteration
Class Name: PerfectPermutationHard
Return Type: int[]
Method Name: reorder
Arg Types: (vector<int>)
Problem Statement

Problem Statement

A permutation A[0], A[1], ..., A[N-1] is a sequence containing each integer between 0 and N-1, inclusive, exactly once. Each permutation A of length N has a corresponding child array B of the same length, where B is defined as follows:
  1. B[0] = 0
  2. B[i] = A[B[i-1]], for every i between 1 and N-1, inclusive.
A permutation is considered perfect if its child array is also a permutation.

Below are given all permutations for N=3 with their child arrays. Note that for two of these permutations ({1, 2, 0} and {2, 0, 1}) the child array is also a permutation, so these two permutations are perfect. 
Permutation		Child array
{0, 1, 2}		{0, 0, 0}
{0, 2, 1}		{0, 0, 0}
{1, 0, 2}		{0, 1, 0}
{1, 2, 0}		{0, 1, 2}
{2, 0, 1}		{0, 2, 1}
{2, 1, 0}		{0, 2, 0}
You are given a int[] P containing a permutation of length N. Find a perfect permutation Q of the same length such that the difference between P and Q is as small as possible. The difference between P and Q is the number of indices i for which P[i] and Q[i] are different. If there are several such permutations Q, return the one among them that has the lexicographically smallest child array.

Notes

  • int[] A comes before int[] B (with the same length) lexicographically if A has a smaller integer at the first position where the arrays differ.

Constraints

  • P will contain between 1 and 50 elements, inclusive.
  • P will contain each integer between 0 and N-1, inclusive, exactly once, where N is the number of elements in P.
Examples
0)
{2, 0, 1}
Returns: {2, 0, 1 }

This permutation is already perfect.

1)
{4, 0, 5, 2, 1, 3}
Returns: {2, 0, 5, 4, 1, 3 }

Here the smallest possible difference between P and Q is 2. There are 9 possible choices for Q: {2,0,5,4,1,3}, {3,0,5,2,1,4}, {4,0,1,2,5,3}, {4,0,5,1,2,3}, {4,0,5,2,3,1}, {4,2,5,0,1,3}, {4,3,5,2,1,0}, {4,5,0,2,1,3} and {5,0,4,2,1,3}. Among them, {2,0,5,4,1,3} has the lexicographically smallest child array (this array is {0,2,5,3,4,1}).

2)
{2, 7, 3, 0, 6, 4, 5, 1}
Returns: {1, 7, 3, 0, 6, 2, 5, 4 }
3)
{11, 8, 10, 1, 5, 4, 0, 7, 3, 9, 12, 6, 2}
Returns: {1, 8, 10, 2, 5, 7, 0, 9, 3, 11, 12, 6, 4 }
4)
{0, 1, 4, 2, 3, 5}
Returns: {1, 2, 4, 5, 3, 0 }

Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PerfectPermutationHard with a public method vector<int> reorder(vector<int> P) · 69 test cases · 2 s / 256 MB per case

Submitting as anonymous