You are attempting to decipher a message that is being received over an error prone communication line. All or part of the message may be received incorrectly. (See below for description of how errors are generated.)
Your class should implement one method, getTransmission, which takes two ints, N and C, the length of the message, and the number of distinct characters which may occur in the message (the first C uppercase letters). It will also take a double[], states, describing each possible state of the transmitter (explained below). Your getTransmission method may call the static method getMessage in class Message with two ints, beginPos and length, to request that a portion of the message be transmitted. You may call the getMessage method a maximum of N/4 times (except for the first 4 examples, where you are allowed 100 calls). (More calls than this will result in a 0 for the test case.) The getTransmission method should return a String containing the original message with as few errors as possible.
You will be allowed a total of 20 seconds execution time. There is a slight overhead during calls to getMessage, which is included in the runtime. However, you may have other threads running during the calls to the getMessage method.
Your score will be based upon count, the number of times the Message.getMessage method is called, transmit, the total number of characters that you request to be transmitted, and errors, the number of characters in your final return that are incorrect. The returned string must be the correct length or you will get a 0 for that test case. The raw score for each test case will be equal to 100 * N / (transmit + 10 * count + 1) / 2errors. In addition, a 2% penalty for each second of execution time will be applied to your score. In other words, if your program ran for 10 seconds, your final score would be your raw score minus 20%. Your total score will be the sum of your scores for each test case.
The manner in which errors are introduced into the transmission will be controlled by a finite state machine. At any given time, the communications line will be in one of several states each with an associated probability. If, when a character c is transmitted, the line is in a state with associated probability p, then the character c will be faithfully transmitted with probability p. With probability 1-p, however, one of the C characters (possibly c) will be transmitted at random (each with equal probability 1/C). After each character is transmitted, the communications line may switch into a different state or stay in the same state.
You will be given a double[] states indicating the associated probabilities for each of the communications line's states. The starting state for each transmission is equally likely to be any of the states. For each test, one additional value (not given), pChange, is the probability that, after a character is transmitted, the communications line changes to a different state (chosen randomly).
For example, imagine that states = { 0.1, 0.9 }. In this case, when the communications line is in state 0, characters are only transmitted correctly on occasion, while when the line is in state 1, they are almost always tranmitted correctly. If pChange were 0.01, then after each character was transmitted, the line would toggle to the other state with probability 0.01.
|