Connection Status:
Competition Arena > ChatExit

ChatExit

SRM 249 · 2005-06-29 · by AdminBrett

SRM 249 · 2005-06-29 · by AdminBrett · Greedy
Class Name: ChatExit
Return Type: int[]
Method Name: leaveOrder
Arg Types: (vector<string>)
Problem Statement

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[].

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: Person 1 must see 4 lines from person 0, but person 2 must only see 3 lines from person 0. 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 1 1 0",
"1 0 1 0",
"0 0 0 0",
"0 0 0 0"
}
Returns: {3, 2, 0, 1 }

Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ChatExit with a public method vector<int> leaveOrder(vector<string> numSeen) · 94 test cases · 2 s / 256 MB per case

Submitting as anonymous