StRings
TCO12 Semifinal 1 · 2012-03-27 · by snuke
TCO12 Semifinal 1 · 2012-03-27 · by snuke · Graph Theory, Greedy, Math
Problem Statement
Problem Statement
This problem statement contains images that may not display properly outside the applet.
There are N characters in the Ninja language. As the number of different characters can be very large, we will use numbers from 1 to N to represent the individual characters in Ninja language. The characters are numbered in alphabetical order. That is, whenever i < j, character i is earlier in the alphabet than character j. Each string in Ninja language can now be seen as a sequence of integers. When comparing two different strings of the same length, the lexicographically smaller one is the one with a smaller integer on the first place where they differ.
Ninja Ren has a string R of length N that contains each character exactly once. Then she converted the string R to the string S using the following method:
First, Ren takes her string R and writes it onto a circular piece of paper. The paper can now be cut at one of N possible positions, each time producing a different string of length N. Ren takes those N different strings and sorts them into lexicographical order (starting with the lexicographically smallest one). The string S is obtained by taking the last characters of the N sorted strings, in order. In other words, Ren takes the N cyclic rotations of R, sorts them, and then only looks at their last letters.
For example, when R is "2 4 5 1 3", S will be "5 3 1 2 4". The following picture shows how the conversion works.
You are given theint N and a int[] first. containing a prefix of the string S. More precisely, for each valid index i, element i of first is the i-th character of S. (Both indices are 0-based.)
Find the lexicographically smallest possible string S. If N is less than or equal to 50, return the entire string S. If N is greater than 50, return just the last 50 characters of S. If there is no such S, return an emptyint[] instead.
There are N characters in the Ninja language. As the number of different characters can be very large, we will use numbers from 1 to N to represent the individual characters in Ninja language. The characters are numbered in alphabetical order. That is, whenever i < j, character i is earlier in the alphabet than character j. Each string in Ninja language can now be seen as a sequence of integers. When comparing two different strings of the same length, the lexicographically smaller one is the one with a smaller integer on the first place where they differ.
Ninja Ren has a string R of length N that contains each character exactly once. Then she converted the string R to the string S using the following method:
First, Ren takes her string R and writes it onto a circular piece of paper. The paper can now be cut at one of N possible positions, each time producing a different string of length N. Ren takes those N different strings and sorts them into lexicographical order (starting with the lexicographically smallest one). The string S is obtained by taking the last characters of the N sorted strings, in order. In other words, Ren takes the N cyclic rotations of R, sorts them, and then only looks at their last letters.
For example, when R is "2 4 5 1 3", S will be "5 3 1 2 4". The following picture shows how the conversion works.
You are given the
Find the lexicographically smallest possible string S. If N is less than or equal to 50, return the entire string S. If N is greater than 50, return just the last 50 characters of S. If there is no such S, return an empty
Constraints
- N will be between 1 and 100,000 inclusive.
- first will contain between 1 and 50 elements, inclusive.
- Each element of first will be between 1 and N, inclusive.
- Elements of first will be pairwise distinct.
- The constraints above guarantee that the number of elements of first will be less than or equal to N.
Examples
0)
5
{2, 4}
Returns: {2, 4, 1, 5, 3 }
{2, 4, 1, 5, 3} is the lexicographically smallest possible string S.
1)
5
{1}
Returns: { }
There is no S that starts with 1.
2)
10
{3, 8, 6}
Returns: {3, 8, 6, 1, 2, 5, 4, 9, 10, 7 }
3)
100
{34, 68, 97, 87, 47, 39, 50, 59, 4, 7, 29, 91, 1, 80, 90, 95,
60, 40, 43, 73, 54, 69, 32, 31, 53, 11, 84, 3, 28, 77, 44, 86,
2, 75, 85, 52, 93, 81, 70, 89, 19, 67, 98, 100, 41, 65, 57, 27, 33, 49}
Returns: {5, 6, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 30, 35, 36, 37, 38, 42, 45, 46, 48, 51, 55, 56, 58, 61, 62, 63, 64, 71, 66, 72, 74, 76, 78, 79, 82, 88, 83, 94, 96, 92, 99 }
If N is greater than 50, return just the last 50 characters of S.
4)
100000
{43944, 17163, 51303, 35965, 62699, 240, 9126, 95755, 2360, 12009, 99627, 8620, 84125, 10442, 10317, 10312, 6460, 27176, 69518, 42992, 67864, 35645, 96294, 67654, 89899, 53536, 59109, 94700, 55223, 29878, 12818, 82748, 1672, 82520, 88871, 3209, 14106, 84525, 64060, 17190, 24618, 24194, 45307, 50960, 39259, 80618, 19590, 72792, 89475, 63508}
Returns: {99952, 99953, 99954, 99955, 99956, 99957, 99958, 99959, 99960, 99961, 99962, 99963, 99964, 99965, 99966, 99967, 99968, 99969, 99970, 99971, 99972, 99973, 99974, 99975, 99976, 99977, 99978, 99979, 99980, 99981, 99982, 99983, 99984, 99985, 99986, 99987, 99988, 99989, 99990, 99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999, 100000, 99626 }
Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StRings with a public method vector<int> getSmallest(int N, vector<int> first) · 122 test cases · 2 s / 256 MB per case