CandidatesSelection
SRM 620 · 2013-12-22 · by cgy4ever
SRM 620 · 2013-12-22 · by cgy4ever · Greedy
Problem Statement
Problem Statement
Fox Ciel wants to hire a new maid.
There are n candidates for the position.
There are m different skills a maid should have, such as cooking, cleaning, or discreetness.
Ciel numbered the candidates 0 through n-1 and the skills 0 through m-1.
Ciel evaluated the level each candidate has in each of the skills. You are given this information encoded in aString[] score with n elements, each consisting of m characters.
For each i and j, the character score[i][j] represents the level candidate i has in skill j.
Said character will always be between 'A' and 'Z', inclusive, where 'A' means the best possible and 'Z' the worst possible candidate.
Immediately after the reviews, the order of the candidates was {0, 1, ..., n-1}. Then, Ciel spent several days thinking about whom to hire. On each day, she chose one skill and reordered the candidates according to their level in that skill, from the best to the worst one. Whenever two candidates had the same level in the currently considered skill, she kept them in the order in which they were after the previous day. (Formally, the sorting algorithm she used was stable.)
You are given aint[] result containing a permutation of 0 through n-1.
Return "Possible" (quotes for clarity) if it is possible that after zero or more days the order of candidates was precisely the one given in result.
Otherwise, return "Impossible".
Ciel evaluated the level each candidate has in each of the skills. You are given this information encoded in a
Immediately after the reviews, the order of the candidates was {0, 1, ..., n-1}. Then, Ciel spent several days thinking about whom to hire. On each day, she chose one skill and reordered the candidates according to their level in that skill, from the best to the worst one. Whenever two candidates had the same level in the currently considered skill, she kept them in the order in which they were after the previous day. (Formally, the sorting algorithm she used was stable.)
You are given a
Constraints
- n will be between 1 and 50, inclusive.
- m will be between 1 and 50, inclusive.
- score will contain exactly n elements.
- Each element of score will contain exactly m characters.
- Each character in each element of score will be an uppercase English letter ('A'-'Z').
- result will be a permutation of 0 through n-1.
Examples
0)
{"CC", "AA", "BB"}
{1,2,0}
Returns: "Possible"
You can sort them by any skill to get the result.
1)
{"BAB", "ABB", "AAB", "ABA"}
{2,0,1,3}
Returns: "Possible"
We can first sort them by skill 0 to get {1, 2, 3, 0}, then sort them by skill 1 to get {2, 0, 1, 3}.
2)
{"BAB", "ABB", "AAB", "ABA"}
{0, 1, 3, 2}
Returns: "Impossible"
3)
{"AAA", "ZZZ"}
{1, 0}
Returns: "Impossible"
4)
{"ZZZ", "AAA"}
{0, 1}
Returns: "Possible"
Ciel can do no operation at all.
Submissions are judged against all 163 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CandidatesSelection with a public method string possible(vector<string> score, vector<int> result) · 163 test cases · 2 s / 256 MB per case