CompanyMessages
TCO05 Sponsor 4 · 2005-08-16 · by AdminBrett
TCO05 Sponsor 4 · 2005-08-16 · by AdminBrett · Dynamic Programming
Problem Statement
Problem Statement
Character j in element i (both 0-based) of messages denotes how many messages employee i sent to employee j. You will return a int[] containing the hierarchy of the employees within the company. Element 0 is the highest ranked employee, and so forth. The returned ranking should minimize the number of messages sent from lower ranked employees to higher ranked employees. If multiple solutions are possible, return the one with element 0 minimal. If there are still ties, minimize element 1, etc.
Constraints
- messages will contain between 2 and 15 elements inclusive.
- Each element of messages will contain exactly N characters, where N is the number of elements in messages.
- Each character in messages will be a digit ('0'-'9').
- Character i in element i of messages will be '0'.
Examples
0)
{
"09999999",
"00999999",
"00099999",
"00009999",
"00000999",
"00000099",
"00000009",
"00000000"
}
Returns: {0, 1, 2, 3, 4, 5, 6, 7 }
1)
{
"00000999",
"00000099",
"00000009",
"00909999",
"00090999",
"00009099",
"00000000",
"09999990"
}
Returns: {0, 1, 3, 2, 4, 5, 7, 6 }
2)
{
"044444",
"404444",
"440444",
"444044",
"444404",
"444440"
}
Returns: {0, 1, 2, 3, 4, 5 }
3)
{
"044454",
"404434",
"140444",
"443044",
"244404",
"443440"
}
Returns: {0, 2, 3, 4, 1, 5 }
4)
{
"010",
"001",
"110"
}
Returns: {2, 0, 1 }
29)
{"000",
"000",
"000"}
Returns: {0, 1, 2 }
Here no messages are sent.
30)
{"000",
"100",
"010"}
Returns: {2, 1, 0 }
Person 2 sends a message to person 1 and person 1 sends one to person 0. The hierarchy is clear.
31)
{"03434",
"10231",
"12039",
"92402",
"92310"
}
Returns: {3, 2, 4, 0, 1 }
A lot of messages being sent around.
45)
{"06805","00145","19043","09902","48640"}
Returns: {0, 4, 3, 2, 1 }
A lot of messages sent around.
64)
{"012105","601745","830479","043086","349904","649810"}
Returns: {4, 2, 1, 5, 0, 3 }
A lot of messages sent around.
Submissions are judged against all 89 archived test cases, of which 10 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CompanyMessages with a public method vector<int> getRank(vector<string> messages) · 89 test cases · 2 s / 256 MB per case