TopCoder problem "ChatExit" used in SRM 249 (Division I Level Two)



Problem Statement

    A group of people have participated in an online chat session. Element i (0-based) of numSeen contains the number of lines of chat seen by person i before leaving (everyone arrives at the same time). More precisely, integer j in element i of numSeen is the exact number of lines written by person j that are seen by person i before leaving. Integer i of element i will always be 0, and should be ignored. You will return a int[] containing the order in which each person left. If multiple orders are possible, return the one that occurs first lexicographically. If none are possible, return an empty int[].
 

Definition

    
Class:ChatExit
Method:leaveOrder
Parameters:String[]
Returns:int[]
Method signature:int[] leaveOrder(String[] numSeen)
(be sure your method is public)
    
 

Notes

-Order A comes lexicographically before order B if A has a lower value than B in the first position that they disagree.
 

Constraints

-numSeen will contain between 2 and 25 elements inclusive.
-Each element of numSeen will contain between 3 and 50 characters inclusive.
-Each element of numSeen will be a single space delimited list of integers. Each integer will be between 0 and 100 inclusive, and will have no extra leading zeros.
-Each element of numSeen will contain exactly k integers, where k is the number of elements in numSeen.
-Integer i in element i of numSeen will always be 0.
 

Examples

0)
    
{
"0 1 1",
"2 0 0",
"3 1 0"
}
Returns: {1, 0, 2 }
A possible sequence of events is:

Person 0 writes a line.

Person 1 writes a line.

Person 0 writes a line.

Person 1 leaves.

Person 2 writes a line.

Person 0 writes a line.

Person 0 leaves.

Person 2 leaves.

1)
    
{
"0 1 1",
"4 0 0",
"3 1 0"
}
Returns: { }
No order is possible here due to the following requirements:
  1. Person 1 must see 4 lines from person 0, but person 2 must only see 3 lines from person 0.
  2. Person 0 must see 1 line from person 2, but person 1 must not see any.
The first item above forces person 1 to leave after person 2. The second item forces person 1 to leave before person 2.
2)
    
{
"0 100 100 100 100 100",
"100 0 100 100 100 100",
"100 100 0 100 100 100",
"100 100 100 0 100 100",
"100 100 100 100 0 100",
"100 100 100 100 100 0"
}
Returns: {0, 1, 2, 3, 4, 5 }
Everyone says exactly 100 lines. Any leaving order is possible. The lexicographically first order is returned.
3)
    
{
"0 1 0 0",
"1 0 0 0",
"0 0 0 0",
"0 0 0 0"
}
Returns: {2, 3, 0, 1 }
4)
    
{
"0 0 0 0 0",
"0 0 0 0 0",
"0 0 0 0 0",
"0 0 0 0 0",
"0 0 0 0 0"
}
Returns: {0, 1, 2, 3, 4 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4614

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7224&pm=4614

Writer:

AdminBrett

Testers:

PabloGilberto , lbackstrom

Problem categories:

Greedy