TopCoder problem "MessageDispatcher" used in MessageDispatcher (Division I Level One)



Problem Statement

    In this problem your task is to simulate a message dispatching system in a most efficient way. The system consists of a set of channels (identified by 64-bit ID numbers) and a set of listeners (identified by 32-bit ID numbers). Each listener can be subscribed to a set of channels. The incoming messages are sent to some subset of channels and forwarded to listeners who are subscribed to at least one of these channels.

Incoming events

The system must handle three types of incoming events:
  • incoming message consists of its content and a set of channel IDs it is sent to.
  • listener subscription consists of listener ID and a range of channel IDs [A, B], meaning that channels with IDs between A and B, inclusive, are added to the set of channels this listener is subscribed to.
  • listener unsubscription consists of listener ID and a range of channel IDs [A, B], meaning that channels with IDs between A and B, inclusive, are removed from the set of channels this listener is subscribed to.

Input format

You will be given a int[] x, which should be treated as unsigned integers and can be converted to the sequence of incoming events using the following pseudocode:
for (i=0; i<N; i++)
{   if (x[i] > 0)
    {   //incoming message
        content = x[i];
        n_channels = x[++i];
        for (j = 0; j<n_channels; j++)
            channels[j] = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
        incoming_message(content, n_channels, channels);
    }
    else
    if (x[i] == -1)
    {   //listener subscription
        listener = x[++i];
        A = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
        B = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
        listener_subscription(listener, A, B);
    }
    else
    if (x[i] == -2)
    {   //listener unsubscription
        listener = x[++i];
        A = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
        B = (((unsigned long long)x[++i])<<32) | ((unsigned long long)x[++i]);
        listener_unsubscription(listener, A, B);
    }
}

Output format

You must return a int[] representing the sequence of outgoing events initiated by the given sequence of incoming events. There are five types of outgoing events, and each of them is described with a sequence of integers in the following way:
  • message delivery is described with a pair (listener ID, message content). Note that each listener should receive a particular message only once (per incoming event) even if it is subscribed to several of the channels the message is being sent to.
  • for listener subscription and listener unsubscription the first integer in the sequence should be -1 or -2, respectively, followed by listener ID and four integers (Ahigh, Alow, Bhigh, Blow), indicating that this listener subscribed to or unsubscribed from a range [A, B] of channel IDs. These events should be initiated only by actual changes in the current subscriptions. Thus, if a listener subscribes to the same channel ID twice, the event should be initiated only for the first subscription (unless the listener has unsubscribed between the subscriptions). Unsubscription from a channel which didn't belong to subscription set before shouldn't initiate an outgoing event as well.
  • for channel subscription and channel unsubscription the first integer in the sequence should be -3 or -4, respectively, followed by four integers (Ahigh, Alow, Bhigh, Blow), representing a range [A, B] of channels which had no listeners before and got their first listener, or lost their last listener.
Each channel ID in the output is represented with a pair of integers in a same way as in input:
A = (((unsigned long long)Ahigh)<<32) | ((unsigned long long)Alow)

Scoring

First of all, your return will be checked for correctness. This will be done by comparing the sequence of outgoing events to a precomputed reference one. Note that in most cases the correct sequence of events can be written in several ways. Thus, if one incoming event initiates several outgoing events, the order in which they are mentioned in the sequence is not important, as long as all events initiated by earlier imcoming events are mentioned before the events initiated by later incoming events. Besides, ranges of channel IDs can be given as any set of non-intersecting ranges as long as they combine to the reference set of ranges.

If your return is correct, the score for this test case will be the execution time in milliseconds, otherwise the score will be 0. Your overall score will be computed by finding the minimum time out of all submissions, MIN, for each test case. If your time for a testcase was YOU, that test will contribute MIN/YOU to your final score.

A tester is available for checking the correctness of your return offline.
 

Definition

    
Class:MessageDispatcher
Method:getEvent
Parameters:int[]
Returns:int[]
Method signature:int[] getEvent(int[] x)
(be sure your method is public)
    
 

Notes

-The examples are available for download at http://www.topcoder.com/contest/problem/MessageDispatcher/manual.html.
-The final tests are all generated in the same way (except for test 0, which is an example only). They are randomly generated in one of three different ways. Tests 1, 4, and 7 were generated using one method; tests 2, 5 and 8 were generated using another method; tests 3, 6 and 9 were generated using the third and final method.
-The time limit is 60 seconds. The memory limit is 2048M. There are 10 provisional test cases.
 

Examples

0)
    
"1"
Returns: "seed = 1"
1)
    
"2"
Returns: "seed = 2"
2)
    
"3"
Returns: "seed = 3"
3)
    
"4"
Returns: "seed = 4"
4)
    
"5"
Returns: "seed = 5"
5)
    
"6"
Returns: "seed = 6"
6)
    
"7"
Returns: "seed = 7"
7)
    
"8"
Returns: "seed = 8"
8)
    
"9"
Returns: "seed = 9"
9)
    
"10"
Returns: "seed = 10"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13953&pm=10621

Writer:

Unknown

Testers:

Problem categories:

Simulation