Connection Status:
Competition Arena > RandomFA

RandomFA

SRM 178 · 2004-01-07 · by brett1479

SRM 178 · 2004-01-07 · by brett1479 · Dynamic Programming, Graph Theory, Math
Class Name: RandomFA
Return Type: double
Method Name: getProbability
Arg Types: (vector<string>, vector<string>, vector<string>, int, int)
Problem Statement

Problem Statement

A Randomized Finite Automaton (RFA) works as follows. The RFA maintains a variable, called its state, which is initially set to 0. When an input character ('a', 'b', or 'c') is fed into the RFA, it must determine which new value is to be assigned to its state. This determining process is governed by a list of rules stored in the RFA. For example, if the RFA is in state 2 and has received an 'a' as input, the RFA would consult element 2 of rulesa. Each element of rulesa is of the form "st:prob st:prob ...", where st denotes a value to be assigned to the state variable, and prob denotes the percentage (out of 100) of such an assignment occurring. If the given probabilities do not add up to 100, the remaining probability is the chance of changing state to 999. If a state (not 999) is missing from a rule, then its prob is assumed to be 0. Once state is 999, regardless of future input, it remains on 999. The machine has analogously defined rulesb, and rulesc defining what to do on 'b' or 'c' accordingly.

When processing an input string, each character is processed in order, left to right, one at a time. Assuming all input strings of length maxLength or fewer (including the string of length 0) are equally likely, return the probability the RFA will be on state finalState once the string is completely processed. The probability returned will be a double, between 0 and 1 inclusive. Results must be accurate to 1e-9.

Constraints

  • rulesa will contain between 1 and 50 elements inclusive.
  • rulesa, rulesb, and rulesc all contain the same number of elements.
  • Each element of rulesa, rulesb, and rulesc contain between 0 and 50 characters inclusive.
  • Each element of rulesa, rulesb, and rulesc is a single space delimited list of pairs. Each pair is of the form (quotes for clarity) "st:prob" where,st is an integer, with no extra leading zeros, between 0 and (size of rulesa-1) inclusive, andprob is a positive integer, with no leading zeros.
  • The prob values in a single element of rulesa, rulesb, or rulesc will sum up to a value between 0 and 100 inclusive.
  • No 2 pairs in a single element of rulesa, rulesb, or rulesc will have the same st value.
  • finalState will be between 0 and (size of rulesa-1) inclusive, or 999.
  • maxLength will be between 0 and 10 inclusive.
Examples
0)
{"0:100"}
{""}
{""}
999
1
Returns: 0.5

The 4 strings that need to be considered are (quotes for clarity) "", "a", "b", and "c". Of those 4, the first 2 will end up on state 0, while the latter 2 will end up on state 999. 2 out of 4 produces a probability of .5 .

1)
{"1:100","0:100"}
{"1:100","0:100"}
{"1:100","0:100"}
1
3
Returns: 0.75

Here all even length strings will result in state 0, and odd length strings will result in state 1. Of the 40 strings considered, 1 has length 0, 3 have length 1, 9 have length 2, and 27 have length 3. Thus 30/40=.75 of them have odd length.

2)
{"1:25 2:25 3:25 4:25","0:100","0:100","0:100","0:100"}
{"","","","",""}
{"","","","",""}
3
5
Returns: 0.0020604395604395605

All strings that contain a 'b', or 'c' are sent to 999. The strings containing only 'a's begin on state 0, and are evenly distributed between states 1,2,3 and 4 after the first 'a'. After the second 'a' they are all returned to state 0. Examining this pattern, we see that strings that end on state 3 must contain only 'a's and have odd length. Of those, only a quarter of them actually make it to state 3. There are 3 strings consisting of only 'a's that have odd lengths less than or equal 5. This makes 3 out of the total 364 strings. The returned probability is thus 3/364*.25 = .0021 approx.

3)
{"1:25 2:25 3:25 4:25","0:100","0:100","0:100","0:100"}
{"","","","",""}
{"","","","",""}
999
5
Returns: 0.9835164835164837

The same problem as before, but now we want the strings that will end on 999. This will be any string of positive length that has a 'b' or 'c'. There are 358 of these, resulting in a probability of 358/364 = .984 approx.

4)
{"2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35",
 "2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35",
 "2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35"}
{"0:10 4:7 5:1","0:10 4:7 5:1","0:10 4:7 5:1",
 "0:10 4:7 5:1","0:10 4:7 5:1","3:79 2:10"}
{"1:100","2:100","3:100","4:100","5:100","0:100"}
3
10
Returns: 0.002676338903044717

A more complex example.

5)
{"2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35",
 "2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35",
 "2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35"}
{"0:10 4:7 5:1","0:10 4:7 5:1","0:10 4:7 5:1",
 "0:10 4:7 5:1","0:10 4:7 5:1","3:79 2:10"}
{"1:100","2:100","3:100","4:100","5:100","0:100"}
3
0
Returns: 0.0

Same as before, but only the empty string is considered.

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

Coding Area

Language: C++17 · define a public class RandomFA with a public method double getProbability(vector<string> rulesa, vector<string> rulesb, vector<string> rulesc, int finalState, int maxLength) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous