JOIN
Get Time

   Problem Statement  

 Problem Statement for CandidatesSelection

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 a String[] 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 a int[] 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".
 

Definition

    
Class:CandidatesSelection
Method:possible
Parameters:String[], int[]
Returns:String
Method signature:String possible(String[] score, int[] result)
(be sure your method is public)
    
 

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.
5)
    
{"ZYYYYX","YXZYXY","ZZZZXX","XZXYYX","ZZZYYZ","ZZXXYZ","ZYZZXZ","XZYYZX"}
{3,7,1,0,2,5,6,4}
Returns: "Possible"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 620 Round 1 - Division I, Level Two