Problem Statement
Time limit is 2.5 seconds.
There is a group of N people. The people are numbered from 0 to N-1. Each person in the group has a first name and a last name.
If a and b are two different people such that the last name of person a is the same as the first name of person b, the ordered pair (a, b) is called cool.
Each ordered pair of people has some weight. The weight of (a, b) is weight[a*N+b].
Given a group of people, Kaede's happiness is equal to the total weight of all cool pairs in that group.
You are given the String[]s firstname and lastname. These contain the first and last names of people in the group. However, some of these names may have been replaced by wildcards ("*"). The total number of wildcards does not exceed 17.
Kaede plans to replace each wildcard by some non-empty string of lowercase English letters. Different wildcards may be replaced by different strings.
She wants to do this in a way that will maximize her happiness. If there are multiple optimal solutions, she prefers the lexicographically smallest one among them, as defined below.
An assignment is the sequence of strings {F[0], L[0], F[1], L[1], ..., F[N-1], L[N-1]}, where F[i] and L[i] are the names assigned to person i. (F is obtained from firstname and L from lastname by replacing each wildcard.)
Given two distinct assignments, the lexicographically smaller one is the one that has a lexicographically smaller string at the smallest index at which the two assignments differ.
Return the lexicographically smallest among all assignments that maximize Kaede's happiness.
Definition
- Class:
- CoolPairs
- Method:
- smallest
- Parameters:
- String[], String[], int[]
- Returns:
- String[]
- Method signature:
- String[] smallest(String[] firstname, String[] lastname, int[] weight)
- (be sure your method is public)
Notes
- Please note that weight does not have to be symmetrical: the values weight[a*N+b] and weight[b*N+a] may differ.
- Given two distinct strings S and T we say that S is lexicographically smaller than T if and only if either S is a prefix of T or the character S[i] has a smaller ASCII value than the character T[i] for the smallest i such that S[i] and T[i] differ.
- Given two distinct arrays of strings P and Q of the same length, we say that P is lexicographically smaller than Q if and only if the string P[i] is lexicographically smaller than the string Q[i] for the smallest i such that P[i] and Q[i] differ.
Constraints
- N will be between 2 and 50, inclusive.
- firstname and lastname will contain exactly N elements each.
- weight will contain exactly N*N elements.
- Each element in firstname and lastname will have between 1 and 10 characters, inclusive.
- Each element in firstname and lastname will either be "*" or it will consist of lowercase English letters ('a'-'z') only.
- The total number of "*"s in firstname and lastname together will be between 0 and 17, inclusive.
- Each element in weight will be either -1 or between 0 and 10000, inclusive.
- weight[a*N+b] will be equal to -1 if and only if a = b.
Examples
{"*", "john"}{"*", "smith"}{ -1, 1, 1, -1 }Returns: {"smith", "john", "john", "smith" }For any assignment the total weight of all cool pairs will be at most 2; {"smith", "john", "john", "smith"} is the only valid assignment that has total weight = 2.{"*", "john"}{"*", "smith"}{ -1, 0, 0, -1 }Returns: {"a", "a", "john", "smith" }The total weight of all cool pairs will be always 0. So, lexicographically smallest one is {"a", "a", "john", "smith"}. (You should take care not to assign empty string to *.){"*", "bob", "*", "alice", "tom"}{"bob", "*", "david", "*", "*"}{ -1, 1943, 0, 39, 2494, 0, -1, 2934, 0, 0, 3848, 9394, -1, 341, 2239, 9394, 39, 0, -1, 929, 2, 230, 0, 234, -1 }Returns: {"david", "bob", "bob", "a", "a", "david", "alice", "david", "tom", "alice" }{"e", "*", "c", "b"}{"*", "e", "d", "c"}{ -1, 2, 100, 101, 0, -1, 0, 0, 0, 101, -1, 0, 0, 100, 0, -1 }Returns: {"e", "b", "d", "e", "c", "d", "b", "c" }{"*","x","*","griystxs","*","x","ikqise","ikqise","*","zuhhj","l","l","xhympzktz","lzpbc","qfqghcctv","lgjmp","*","griystxs","ikqise","*","ikqise","*","*","l","lgjmp"}{"zuhhj","lzpbc","ikqise","*","lgjmp","ikqise","xrp","x","lzpbc","l","xrp","griystxs","l","*","zuhhj","*","*","*","g","xhympzktz","*","*","*","*","xrp"}{ -1,0,0,0,7,0,0,0,0,0,6,0,4,0,0,0,0,0,4,0,0,0,3,0,0, 0,-1,0,7,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,10,0,0,0, 0,0,-1,0,0,0,0,0,0,7,6,8,0,0,0,0,0,0,0,0,10,9,0,0,0, 0,0,0,-1,0,1,0,0,5,0,4,0,1,0,6,0,7,6,0,0,4,0,0,0,0, 0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,5,0,0,0, 0,0,1,0,0,-1,0,0,0,0,0,1,0,9,0,0,0,0,0,2,0,0,0,8,0, 0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,5,0,5,0,0,0,6,0, 0,4,0,0,0,0,0,-1,10,0,5,2,2,0,0,0,0,0,0,0,0,0,0,0,0, 0,9,0,0,10,0,2,0,-1,0,0,0,7,10,9,0,0,8,0,0,0,7,0,0,0, 0,0,4,10,6,0,0,0,0,-1,0,2,0,0,0,0,9,0,0,0,0,0,5,0,0, 0,0,0,0,7,0,0,0,0,0,-1,8,0,0,2,0,0,7,0,0,0,0,0,0,2, 0,1,0,9,0,0,0,1,8,10,5,-1,0,10,5,8,0,0,0,0,5,0,6,0,0, 1,0,0,4,6,0,0,0,6,10,0,0,-1,0,0,0,0,0,0,10,0,10,0,0,0, 0,0,0,6,0,0,0,0,0,0,8,0,8,-1,0,0,0,0,2,0,0,0,0,7,0, 6,0,0,8,0,0,0,1,4,0,0,0,0,0,-1,0,5,0,3,0,0,10,0,0,0, 0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,-1,5,10,0,0,0,0,0,0,0, 0,0,0,0,9,5,0,0,0,0,1,2,0,0,0,0,-1,0,0,0,0,0,7,0,0, 0,0,0,0,0,0,9,0,0,0,0,0,0,0,0,6,0,-1,5,0,0,10,0,0,0, 0,0,4,5,0,0,0,0,7,0,0,0,0,3,0,0,0,0,-1,0,0,0,0,0,0, 5,0,0,0,0,0,0,3,0,8,2,10,0,1,0,0,5,0,0,-1,0,0,0,0,0, 0,4,0,9,0,0,0,0,0,0,3,0,0,0,0,0,0,0,5,0,-1,0,0,9,0, 0,0,0,0,0,0,0,0,0,2,0,3,0,0,0,0,0,2,0,0,0,-1,0,0,0, 0,0,5,0,1,0,0,0,0,2,1,0,0,0,0,0,0,0,0,0,1,1,-1,0,0, 0,0,4,9,0,0,0,0,0,0,0,0,0,3,2,0,0,0,0,0,0,4,0,-1,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,0,0,0,0,0,0,0,1,0,-1 }Returns: {"zuhhj", "zuhhj", "x", "lzpbc", "l", "ikqise", "griystxs", "griystxs", "l", "lgjmp", "x", "ikqise", "ikqise", "xrp", "ikqise", "x", "griystxs", "lzpbc", "zuhhj", "l", "l", "xrp", "l", "griystxs", "xhympzktz", "l", "lzpbc", "l", "qfqghcctv", "zuhhj", "lgjmp", "griystxs", "griystxs", "l", "griystxs", "ikqise", "ikqise", "g", "l", "xhympzktz", "ikqise", "l", "ikqise", "l", "l", "l", "l", "griystxs", "lgjmp", "xrp" }