PROBLEM STATEMENT
Here we describe a simplified protocol for N hosts sending packets through one
router.
The router behavior is the following. The router buffer capacity describes how
many packets the router can accept and store (it will be given as input). The
router forwarding rate describes how many packets it can forward per time unit.
The forwarding rate is constant and given as input. During each time unit the
router serves one host. All hosts are served in order: at the first time step
the first host is served, then the second, then the third, etc. then the last
(Nth), then the first one again and so on. At a specific time unit the router
receives packets from the host it currently serves. If the number of packets is
more than the current space available in the buffer, the router drops the
packets that do not fit in the buffer and accepts all packets that fit in the
buffer. After that it forwards the number of packets defined by the forwarding
rate or the number of packets in the buffer, whichever is smaller. If the
number of packets in the buffer is bigger than the forwarding rate, those
packets that were accepted for storage first are forwarded first. As you might
expect, packets that are successfully forwarded are removed from the buffer.
Then the next time unit starts and the router moves to the next host.
Each host behaves the same way. Each host tries to send an unlimited number of
packets. The rate at which it sends the packets is determined by a congestion
control protocol which works as follows. The host sends the packets to the
router only on its turn. The initial number of packets the host tries to send
is determined by input parameters. The next time the turn comes to this host
the number of packets is determined by the previous number of packets the host
sent and by whether or not the router dropped some of them. If none of the
packets were dropped, the host sends the same number of packets as before plus
one. If some of the packets were dropped, the host tries to resend them and the
number of packets it tries to send this time is the previous number divided by
2. (If the number is odd, round the answer up).
Your task is, given the buffer capacity and the forwarding rate of the router,
a number of time units, and the initial sending rate of each host, return the
number of packets from each host that was forwarded after the given time.
Return results for each host in the order corresponding to the input order.
Assume that the buffer is empty at the beginning.
DEFINITION
Class: Router
Method: forwarded
Parameters: int, int, int, int[]
Returns: int[]
Method signature (be sure your method is public): int[] forwarded(int
bufferCap, int forwRate, int time, int[] initialRates);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- bufferCap is between 1 and 100 inclusive
- forwRate is between 1 and 10 inclusive
- time is between 1 and 1000 inclusive
- initialRates has between 1 and 10 elements inclusive
- each element of initialRates is between 1 and 1000 inclusive
EXAMPLES
1. bufferCap = 10, forwRate = 5, time = 4, initialRates = {7, 2, 20, 1}. During
the first time unit all 7 packets from the first host are accepted, 5 of them
are forwarded and 2 packets are stored in the buffer. During the second time
unit all 2 packets from the second host are accepted, and 2 packets from the
first host and 2 packets from the second host are sent (the buffer is now
empty). During the third time unit 10 packets from the third host are accepted
and 5 of them are forwarded. During the fourth time unit 1 packet from the
fourth host is accepted and 5 packets from the buffer are sent. Return {7, 2,
10, 0}
2. bufferCap = 10, forwRate = 5, time = 20, initialRates = {1}, return {90}
3. bufferCap = 100; forwRate = 6, time = 20, initialRates = {1,1,1,1,1}, return
{10,10,10,10,10}
4. bufferCap = 10, forwRate = 6, time = 21, initialRates = {1,1,1,1,1}, return
{15,10,10,10,10}
5. bufferCap = 100, forwRate = 10, time = 1000, initialRates = {1000, 1000,
1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000}, return {1090, 1000, 1000, 988,
987, 987, 987, 987, 987, 987}