Back
Close

Monte Carlo Tree Search exercise

Statement

 Goal

Assume we are dealing with (nondeterministic) one-player game. To find an optimal sequence of movements we could use Monte Carlo Tree Search algorithm (https://en.wikipedia.org/wiki/Monte_Carlo_tree_search).

Thus, we perform a number of so-called playouts, and gradually build an MCTS tree that will help us choosing statistically best choices for each turn of the game. A playout is a sequence of moves reaching the game tree leaf, so it has assigned a true score. It consists of two parts: the beginning, which is selected by the algorithm using the UCT formula; and the remaining part which is usually a random sequence of movements.

In this puzzle, we are given a list of playouts (encoded as words, where each letter is a single move) with assigned scores, that should be used to build an MCTS tree. After building a tree, the task is to return the sequence of moves, reaching the MCTS tree leaf, that will be chosen using UCT policy given exploration/exploitation constant C.

For given node N visited N.v times, according to the UCB1 formula we should choose a child M that maximizes the value given by: M.s/M.v + C*sqrt(ln(N.v)/M.v), where M.v is number of visits in node M and M.s is sum of scores obtained for this node (so the first component of the sum is average score for node M).

Final remarks:
- Note that this puzzle differs form the real-life-scenario where the playouts are not given, but they are also computed using UCT+random policies.
- In standard implementations you are forced to choose an unexplored move if such exists. Here we assume that after reading the playout data we do not have such moves in the non-leaf nodes of the MCTS tree.
- A tie-breaking rules when comparing UCT values is the ordering on letters (i.e. smaller letter should be chosen).

Example explanation:
- Reading baa 30 will create child node labeled b with avg. score 30 and one visit. The MCTS tree root will have the same statistics. Note that we are adding only one new node at a time.
- Reading ab 20 will create another child node for the root, updating its statistics.
- Finally, reading bbb 4 will create a new node on a path bb from the root, updating all statistics on a way to the root, so the root will have 3 visits, and b node 2 visits.
- Choosing move from the root based on the UCB1 formula will favor move a (average score 20), instead of move b (average score 17). This is because the small value of constant C, makes the exploration part of the equation not significant.
- As there are no further nodes in MCTS tree along that paths, the 1-move sequence a is the answer.
Input
Line 1: 2 space-separated values:
an integer N - the number of performed playouts
a real number C - the constant C (the exploration parameter)

Next N lines: Sequence of movements performed in this playout, followed by a space, followed by the playout's result
Output
Sequence of movements that will be chosen in the MCTS tree using UCB1 selection.
Constraints
0 < N < 500
0 < playout length < 50
1 < branching factor < 10
-100.1 < score (playout's result) < 100.1
Example
Input
3 0.1
baa 30
ab 20
bbb 4
Output
a

Tags
Monte Carlo tree searchUCTUCB1

Difficulty
Hard

Test cases
Tiny tree test Test
Input
3 0.1 baa 30 ab 20 bbb 4
Output
a

Tiny tree validator Validator
Input
3 0.1 baa 30 ab 20 aaa 4
Output
b

Nondeterministic scores test Test
Input
5 0.5 aaa 0.6 baa 1.0 aab 0.1 baa 0.2 aaa 0.2
Output
ba

Nondeterministic scores validator Validator
Input
6 0.6 bbb 0.6 baa 0.8 aab 0.1 baa 0.2 bbb 0.1 abba 0.5
Output
ab

Significant exploration test Test
Input
3 1.0 ac 1.0 bc 1.0 ad 1.1
Output
b

Significant exploration validator Validator
Input
4 15.0 acde 20 badc 17 ad 25 aca 24.6
Output
b

UCB1-tie test Test
Input
4 0.5 dda 20 dad 21 cba 20 chb 21
Output
ch

UCB1-tie validator Validator
Input
6 0.23 dda 30 dda 30 dda 30 cba 20 ceaa 35 cfa 35
Output
ce

Small random test Test
Input
10 0.3 bbbaa -7.35 aabab -0.76 bbaa 14.81 bbaa 18.51 aabaa 16.46 bbabb 15.25 bbabb 5.71 babb -1.89 ababa -5.15 aaaa -7.90
Output
bbabb

Small random validator Validator
Input
10 0.5 ccaab -8.85 acaccb -1.05 cbcccc 18.03 baccb 16.53 babbc 17.40 abbaa -8.89 cbccbcb 1.34 bbbbbcc 13.51 cbaccac 5.95 cbcb -5.37
Output
ba

Large test Test
Input
250 4.4 baabbabbaacbacabccc 2.15 acacabbbccbcbbac 6.29 cbbabacacabbaaacbbbbccb 15.98 abbcbcbcbbbccbacbacbac 7.45 cabbbbbccbaabbbaaaba 9.61 caabcacbbcabbaccaaaabcca 2.65 baabbabaaacaabccaaacbbca 16.38 abaabbacbbaacaabccccbaab 5.69 bbbcaaacbcaabbbbcabaab 2.52 bbbccabccbaacbbc 14.52 acbbbbcccccabcaabbcbbbccc 11.86 bbbccaacacabaaacaccbcbbcc 11.05 caaccccbccbcacbcbabbab 12.77 cbbbaababcbacaca 3.98 ccbaacabbbbabba 12.16 bacbbbaaaaabbcbccaccccabb 3.08 baaabbccbbbabbcccabac 6.20 bbabcaabaccbcaaacabbbcb 11.04 aaccbbbbaaaabaaacba 8.71 acabbabbacbacacbbbbcba 1.59 ccaaacabcccacac 18.02 abaabcccbcabbacaccccbabba 19.69 cbcacaacbacbcacac 1.65 acccbacbbcbbbcbacc 10.88 abccccbccacababbabbcc 16.70 abcbcaaabaaaaabc 12.48 aaabcacbccbcbccbababaa 2.37 cbbcbbcbccabcccbaccbc 14.85 cbbbbbbccabcbbcac 17.65 bcbcaabbabaccbbaccacccbcb 3.68 bcbcbcbbaaabacabcbbaccc 14.03 abcaabababcabcbacabbcbbb 10.23 ccaababcabbccbcaaaacabac 0.59 abacbcbccccaabbca 6.11 bcbbcaacabbccbabccc 7.32 cabbbacabbaacbacb 4.51 acabcbacababbacabac 9.29 aacabaacaccccacbbcabcaacb 8.83 acaaccbaccabacacbc 13.63 cbbaacabccabbac 9.65 bcbababaaccbcbccccaa 6.02 cbacbbaccbacaaa 10.32 bababbcbbcaaaccccbbaaa 7.15 cbabacbcabcabaccaabcbcbaa 16.95 abacbbacaccaaacbaccab 3.63 acbaaccaaacaacaccbc 9.61 cbcacaaaacbcccaca 4.20 abbcccccbcccacbbbcbbbcb 2.14 cbbabccaabccbaccbccbac 18.16 bbcbbbacabccbca 2.76 aabaccbcacabccacb 11.26 cababccbcbbccbbaccacaccbc 1.20 abcabbcbcccaaab 6.94 acbbcacaacbccaacccabb 17.85 cbbbabcacbccaccaabc 1.06 bccabccacabbbabacabb 14.83 cbccacaccbcbbcbbcbb 4.15 acccaccabaabbbbc 12.80 bbabaababcbccccaacac 12.97 acaaccbcbcbbccccab 17.55 acabacbaacabbcc 3.28 bbabcaaababacbbcbac 9.10 caccccabbacabcccccbbbbacc 0.63 aabacacaabacabbbbba 7.90 cbcbabaaabcaaccacaab 8.40 acaabbbbaacacbbaaaaacabac 7.48 bbbbcbccabbcaaaabacb 9.48 baabbaabccaaaacbccacbbca 10.36 abcababcbbbaacacaacccbca 13.00 accacabcbaaababcabacbbabb 18.61 cbcbacabbcabaacaabbac 3.48 cbababcbcbbacbcb 7.33 ccacaccbbcbcabbbbcc 19.13 bcbabaabbbbaababab 11.86 baabbbbacbacaccb 14.28 ccbabaacccacbcba 18.22 bcbccabbbabcbacc 0.13 abcacbbbbacccbc 17.33 bbbaaaacbcbaaacccca 10.24 cbacabaaccabbcac 11.96 caababaaccbbcbcaabbaaca 6.65 bbbaabccbbccbacbaabbccca 6.89 baabacaaabbccacbbabccac 10.71 bbcabaabaabcaabacccbcacac 3.46 cabbccbbabbccbccbaaac 10.20 bbbabacbbabbbacccbbaaacb 13.42 bcbcabbbbcbccaa 19.82 bccaabbacccbbccbaca 7.07 aaaaccaabbabccbbcabbabc 0.91 aacaaaaacacaccacbb 19.43 cbccbabccccaabc 17.29 ababbbbababbbbccaabbb 17.61 acbcaaaabbbababbbbcc 9.54 acacacbbbbcccbcaa 17.91 aabcabbcaacbaacbb 13.49 caccacabacccbacbbacbabac 0.62 bbccaabbccbaabccbb 17.12 baaabbabbacbcacccccbcbc 17.17 caaaccccbaacacbbccaabb 9.32 ccaabcbcacaababbab 5.59 cabccaaabcccbabcaabcaaaac 17.73 ccccabbabcbbccac 7.63 abcbabcbcbbbcaa 8.62 bbcaccbbbbcbccbccbaccabc 1.64 bacbacccaaaabcabcaacccb 17.38 bacacbbbbcbabbaacccabcbc 17.78 cbbccbcbbabcabbccbccbb 2.20 babcbcacaabccabc 8.71 cbabaaababacaabaabba 13.80 caabaccaacbbbbbbcbcaaca 18.28 bcababccccabccbbacccb 10.52 ccbbaabbabaabcaacaabc 10.33 abcccacaaccbaabb 13.92 abcccbcbcaacacaacc 3.58 ccccabcbbbaccaabcba 14.26 bcacabacaabacacb 4.63 cbbacabcaaccababbbc 11.75 aabbcababaccbacabbbaccbbb 6.76 bccbcbcbcacbaccaba 10.64 ababcbaaaacccaccacacabcac 13.66 cbabaaccaaaacccb 5.07 bccbcbaccabbbaacb 6.94 bbabbccaccabacbacaccbb 3.29 acacaabacbacbcbaabbacbbc 15.51 cbcababcbaacbccbcbbbcbacb 6.85 baccbcbbbbaabcabbc 18.18 cccccbabbaccabbccb 14.08 abacaacaacbaaaa 13.05 bacabbacbccbabacbccc 3.07 bacbcabbccccabcb 2.72 bcbbacbbacaabbbbcbbacbac 17.39 baccbccabaccabbbbbccbbb 17.93 bbcbacbbacabaabacbabcaaaa 1.37 ccabbbaabbcbcba 2.74 babaccaccacbbbcbabcaaa 7.99 caacabbbacacaabbabaacbc 8.26 acabcbababbccbbcbbbcccaa 11.83 cbbabbacccbacbacacbc 3.37 cccbabcbbbbcbbcbcbcc 9.09 acacaabcaacbbaacbacb 10.87 bcaaaababacabbaa 17.85 bccabaabbbbcbcaaaaacc 4.03 aabbaaabcabcaabbbbba 1.74 bbbbacaabbcaabbacabcac 17.80 bbbccbcbacbaaaacabbb 14.35 abbccbacacccaaaacacbcbcc 5.82 bbacbcbcbabaacccccc 0.03 bacabbccccccacbaacbcca 14.28 cbacbcaacccbaab 7.95 bbbcabcbabcbabacbbbaaac 4.90 abbbaccaaabcbcbbcc 9.71 ababccabbcbbbabcbabaacbb 11.66 cabcaabcabacacbcacbcca 2.26 ccbcbccbcbccbac 14.37 ccaabcbcaaaaaaaabbbacaa 5.96 caccaccccccccacacabcbbb 16.64 cabbacbbacaaaaa 9.33 cbcbcacaabbaacccbbcb 8.84 bcaaaacabbbbbaca 16.03 acacbbcacaccccbb 1.16 abcacabaccabaabbcaabbabac 17.40 cbbcabbababaabcabacaaab 6.55 ccbcacababcbbaaabacbbaab 16.32 acaaaaacaacbbacabbb 6.05 caaaaaabaababcbaacabba 16.02 abbacccbbaababbcbbaabcab 10.30 cbababcbccccbaaacacaccaa 0.94 acccabcbaacbbbabc 2.40 bbcabaccabbbcbbbababbacc 2.87 cbcbbbcbcbcccbca 3.45 accbaccbbcbacccaab 10.12 caaccbaabaabbccacaacb 13.25 ccbaababcacacbaccabba 4.07 bbbaccbcabcbbcb 13.86 cbcccaccbbacccbbbccbcabba 8.75 cababcccbabaababaabab 10.88 cabbcbaccbcbababababccbba 8.22 cccaaacbabbaaaa 7.34 accbacbbbabcaaabbbbaabacc 2.11 cabcbbaabbbcaaaaaacaccbba 14.91 cacbbcbbccbacab 7.14 acaabbccbcbcbbabc 15.73 bcccaaacbbaaabb 12.89 ccabbcbcbcabcaabcccacaaca 16.50 bbabbabbabacaba 11.07 bbaabbbabcbcbbbcbbbbcaabc 9.23 bccbccbbbbccccc 14.16 cacbcbbabccacbab 13.52 cbbaabaaaabaccabcbbccb 5.17 bbaaabbcaaabaabbbbaa 9.52 bbbaaabaccabbbab 13.91 cbcbacababaababcaabcaabc 18.24 aabbaccbaacbccbcaabbcac 9.08 bccbababbcaacbaaa 5.58 bcbabaccabaaaabcbcbbcbaab 12.22 acbbbbbacccbbccbcababcbc 5.93 acabbcbbccbccbcacb 14.85 cbccbcabccaccbbbaabc 17.98 bbaccacbabaabbbccababcaa 12.53 aaacabccabcabaa 12.48 bacccbbabbbaabcabccc 6.87 ccacaaaacaaabccbbabacbab 18.19 aacacabaaaaccbabacbabaa 14.02 aacbbccbcaacabb 16.29 baaabbcababaabbcabcaaabbb 11.83 aabcbaaaccbcbcbaa 6.87 bcbbccacbbcbccbccccccbbca 9.97 baabaacbacabacccccbbb 1.40 cbaacbcbccaccbbaacb 7.24 baabbccabbaabbcbccaacc 6.92 bccbcacbcbbbcaaccbabbabba 3.65 cccbcbabcbbcbacacacbba 3.51 babaabccaacbaccb 3.77 bcacaabcbbbbacbcab 2.04 aabacaccbcabcaac 14.36 bbbaabccaaabcbbab 9.86 ccbbbccaaaaabbbcbababba 2.86 caaaaaaabbcaabbaccaacabbc 17.63 cccacaabcccaaabbcbcaaccba 17.81 aabbcccbcaaacbbaba 12.06 ccccbaccaaccacabbcccabcbb 9.67 cccaaabcbabaacbccccabccc 10.43 bbacacccbccaacaa 5.49 cacbbbbbbbbabbabcbcbacb 17.44 bcaacbbcabbaabcacbb 7.74 ccaabacacccbccacacaac 15.93 bcaaacabbcabbcbc 0.80 acacbcccbbabbaacb 6.93 ccaabcccbcacabaccba 7.80 aaaaccbabcbacbbbb 17.94 cbababacbabbabcb 0.83 bccbbaaaaaaabbbabbbb 7.08 cbbbacaabbccbaabcbcbab 11.51 bbbaaccacbbabacaab 16.02 baaccabacbcacbbbccbca 5.75 cacbaaaaaaacbaccaaaaa 4.57 bbcabcbcbbcbaccabbabbabbb 14.39 acaccbcbbbbcaaacccbc 14.24 acbaaabcacbaaaaa 17.34 aaacabbaccbcaacaac 6.68 ccbcaacaacbcacbccccaabbc 15.74 bacabcbabbbccccbcacabcbcb 9.02 abaacaabacbabccaacac 6.89 ccbbbabcacacccc 8.23 cccaaabbabbabccb 14.71 abacaaccbacaacccacbbbbb 18.10 aabcaccacaaccbbcbcabbcb 10.05 cbcbbcabaccabcbcbbbcaac 9.26 baabaacacbbacbbbcaccbaa 11.34 cbccbcbcbcaaacb 6.64
Output
abcaca

Large validator Validator
Input
300 10 ccbcbaaaccacaaaa 14.74 ccbababcbaaca 7.75 abcbbcaabaacaaa 9.63 cbbababccba 11.22 caabcacbca 3.07 cbaabccaccc 10.40 babababbcbccabba 2.75 bcbbbcaccacbca 21.78 abcbbabcbbbabcba 4.23 cbaccbabaabbbbb 16.05 abaccccccbc 7.44 acaababaacacc 13.26 ccabacbbaa 19.42 cabaacabaccbc 24.07 aaacbcababacb 6.66 bacaabaabcc 2.92 cbbcbbaaacacabbc 17.45 bbaccccacbbbaa 6.69 abaaacbcbbbc 2.66 aaccacabbca 5.94 cbbbcbacacaaa 15.55 aacbbcccbcb 16.42 abcaccbccbcb 19.00 cbcaaccbbaab 7.10 aaabbbccbab 21.66 acbbcbccabbbabbcc 11.29 caccabbaacaacac 6.86 bacbbabccbbabac 1.89 ccacaaabcbbcab 15.44 caccbccabcac 23.49 cccabcabacabcaab 17.26 abacbabcaa 14.30 bcabbccbccbabcaba 15.68 bbbbaaaabbbcbcc 15.32 ccccbcbacbcbcb 1.13 aaccabbcbcc 24.45 cbcbbbcbac 24.98 cabbaacabccccaaa 23.41 bababcbabaaaac 20.45 cccabccbbccacaccc 22.89 bbabbcbbbaabaca 16.63 abaacbbbbbbac 0.40 bbabbbccaa 1.09 acaacacbabaabbbba 16.24 aabacaccac 14.23 abaaacccbcaacba 10.82 bccacacaaaa 13.77 abcbbbacaabcacb 4.29 bbaaacbbccaa 9.49 acaacacacbaaccca 18.50 ccbcaabacaabbbab 9.49 abcabbccccaa 15.90 babaaccacbcccca 13.38 bccbabbbcbbbbaaa 15.60 acbccbcaab 15.21 bbaababccacbcacbb 22.61 cbbbaabbcbbbacbc 13.66 accaabcaabaaccb 22.75 aabbbbaaaaa 19.16 cacccbccacaa 6.46 cbabcabbccbbbca 18.64 aaacbbbccacbabbcc 9.56 bcacbaaccbaa 15.22 ccabccbbbb 3.22 bcbabcbccbbcacc 23.72 aabcbaabbbcbca 2.39 abcababbac 7.17 caabbcccccbaabca 13.07 cbcbcccaccb 11.41 cbabbbcbabbbbb 12.34 cbabbbcbbabacb 11.58 bcbacbcaccccbacb 18.10 baabccacabaa 7.14 bcbaabbbbbbbccbcb 20.26 bcbacbbabaaccc 15.48 aacbbcbbcbcbbbcc 20.52 cccbabbacb 15.46 acaacaaaaaccbcc 16.99 cacbaacbcacccbccc 15.10 bcbbcbcbbabcac 0.71 cccbbbccbcabbb 6.14 abccbcbacbacabbb 14.78 acbcacbbcbbbcca 19.55 babacbbcccbcbbcbb 23.54 acbabcbccaaab 2.69 bbbccbabbcaab 23.97 acbbbbcaaccccb 1.34 bcaacacbcbaabbcbc 1.33 babbcabcbaaaa 4.31 bccccaabccabcaa 9.56 ccbacbcbbccabbc 12.51 aacaabbabccca 14.74 aacaacbbbcbaabb 6.07 bcbbcaccabaab 4.59 acaccbcaabcbc 14.64 bccacbaabcbabba 18.07 cbbbaabacab 15.75 aaccbbbbbab 23.00 acbababacbb 24.43 bcbcbcabcabccb 3.60 ccccbcbcaccb 3.80 caababcabacbbb 17.87 bcbbbbabcbc 0.20 bacaaaabbbbbbba 0.18 bbccbacbcabba 22.04 acacbcbbabbba 23.14 ccacaccbba 15.75 ccbcaaabcbbaa 23.82 aabcbccbbcacbb 19.82 accbaaababcbbbb 0.61 cbbbaacaab 0.03 ccbccaccbcccb 18.30 abcbcccbaaabc 16.40 acacacbcbcabc 0.84 ccabaaaccccab 1.25 bccbcbccacbaabc 1.93 abcaaacbbcacbc 0.76 aabcbacbba 7.46 aabacaacbbc 5.15 babababacaaaaac 10.45 babbaabbacac 1.43 cbbbbbcbcbbbaac 6.65 aacabbaacbba 12.23 bcaccbababaacbabc 13.33 accaacbbbbbcaba 0.05 acbbabcccbb 8.84 bcbabcbcacbbbc 21.15 ccaabaaccab 23.72 aabcabcacabaabb 14.61 bbcbcccbaccbacc 8.64 cacacbbabaa 10.30 cbcbbcccaa 3.57 bacbcbbbbacccaaaa 5.90 acaaaacacaba 21.84 ccbaabcacccccbaa 6.05 cbccaabbcaacab 22.62 bbbabbbbbcb 19.93 bababaaccaabab 17.87 acabbbccbbac 10.52 cbbcbbccbaa 14.83 ccabbaabaacbccbc 7.99 aacabaabbccbabcc 4.26 ccccccaccbbab 8.99 aaabaabcccbabba 16.31 ccbbacbbacac 23.64 baccbacacacbbbb 10.73 acaabacbbabbbb 6.36 bbcabababbaacaaab 4.44 bbbbcaabbb 23.83 ccbcccacabbaa 23.75 ccbcbbbcab 19.86 bababbcbcbaa 10.11 bbacbbabbacc 11.28 abbbacbbcbbacbcb 1.13 abcbcbabaabca 24.50 cbcaaccabb 24.34 babcbabbccabb 9.44 aaaabbcbccccc 18.53 cbaccbaaca 20.23 bbbaccacbcba 6.58 cbabbacacaaaaa 5.47 acbaacbababcb 4.68 ababccabcccbaacab 11.44 bbcbabcbcbcacabcb 22.79 bbbcaaccbbababa 24.56 aabbbccaccaba 15.98 cbcbcabbaabbca 11.44 cbcacbaabbcc 2.06 accababcaab 16.25 bcabacaaccccca 23.13 babbcbbcbabc 21.38 ccbcaabccaa 15.07 aaaccccaaaaaabba 13.15 ccabbcbbacbba 0.36 aacabbaccbaacabbb 20.97 bbabaaccccccbcabc 0.99 aaacaaccbaa 1.50 abaaaaabcaa 14.86 abbbaabcbac 21.86 bacbabcaab 6.26 abbaccaabcab 1.90 ccabcabbccccbca 7.78 cbbcbaaaaababcab 2.60 bccbcacacbababb 23.00 cbbabbcabcc 11.73 abbacacacbbcbb 7.86 cabaacabcb 7.63 baabbbbcaaaaac 14.77 acaacaccbcabcb 5.86 abbccbcbcbabca 13.16 aacbaaacbbcaaaaba 13.73 acccbaccaaccba 10.41 bacccabbbbac 7.68 abccbccaaabbcc 19.60 cabcaccbba 9.64 bcbbbbacbcccb 7.32 bbabbcbcacbacbbb 22.64 aababcacbca 12.72 cbbcbacaababaaacb 8.26 aacababcabccc 22.60 bcababcabbcbba 15.93 cccabcacbcbababc 17.66 ccacacbbcaaabcca 21.47 bacacaababcacbbc 10.71 acabccbaba 24.31 babbacaaaabbbbcca 20.49 aabcccbaaabacabb 5.06 aabacabacbccaa 2.75 ccbbccabcabcccaac 16.28 aabcabbbbbacbca 15.62 cabcbaaacbbabcabb 24.88 bcacaaacaaa 15.59 abbcbcbbccbbcbac 14.64 accaccacbbc 21.83 bbaabacbcccacaba 18.03 cccaaacaaac 3.39 bccaabcabacabcabb 8.99 bcbaaccabbabcacc 18.93 abcbaccacc 3.67 ccccabccccacaba 7.49 cabcbcabcbac 16.00 cccabcbbcacca 21.73 bbcbacbbbcbcbbc 16.75 aaaabccbcbabbca 20.33 cacaacabbcaaa 0.83 cbaabcaaacaa 12.80 bbcbbcbacabca 24.91 aabcccaaab 2.97 ccabccbbbcca 2.89 baabbcabbbc 11.69 abbbcbbabbbcabbab 1.12 babbabbcaaabb 23.43 aacaaaacabbcaa 14.43 cccbaabaabbccbaa 9.78 ccbcabaabbab 1.10 cabbcbbcabbacaa 19.75 ccaabccbbaacc 22.73 bbaccaaabc 5.19 bacacaacabbc 20.95 caaaaccababaa 21.33 abbabacaaaacc 24.24 babcabbabcbabbcba 7.65 baabbaccbaccbca 24.48 accabbccaaaba 15.07 cabcccaabccbcb 18.50 bbccacabaabbcccc 10.56 cacacaaaaaa 23.03 cabaaaacbbacbaa 18.05 bbbcbcaaab 20.21 abbcabbbcaaacb 10.47 bccaaccabbccccca 2.08 ccacbbbbaaacbaac 3.20 bcbcabcacabbcca 24.52 acbaababbcccaccbb 4.46 baabacbcbbcccab 23.51 cbbbbcbbcccca 15.13 aacbbabccab 18.11 abbabcacaaabb 15.36 aabbbccbccbbbac 21.95 cbcbcbcabaacbab 13.62 acacabcbabc 24.28 bccaacccabcccc 23.08 abbcccbacbabcaaba 3.69 bccbbbbbcbccbb 12.15 bacababcababb 11.95 bbcaccccccabc 21.32 cbbaabcacbc 4.38 aabbccabaccac 1.49 cccaacccbc 15.95 aacaacbaabb 3.31 cccaaaabbaccc 12.52 cabacabbbcbbcccac 15.67 bbbbcbcbbabbca 11.80 cababbabcabaa 22.13 aababaacaccbbbbc 8.89 abbbaabcbcbbabacc 3.75 cbbcbbbcbabaaaaa 6.18 ccbcccbcbbbb 24.00 bbbbccbcbb 19.98 aaaacbbcccbcbbcc 16.47 bcbbbbbbbacabbabb 3.81 bbbbcbbacbcacba 15.60 bbccaccacaaa 8.22 cbacabcbba 20.78 bcbaabacabc 15.14 cacbcabcbbccacbbb 16.00 abbcabcbbb 19.64 cbbccbbacac 19.20 bcccbcaccccbba 7.35 cbcbbaaaabaaaacb 21.20 abbbabbbca 10.95 bccaccaccc 12.25 bccccbccaaab 15.63 cbaccbacac 0.98 cbacaabaaccaaacc 3.40 accaaabbccbaaccba 16.80 acccbaccbbaba 15.87 acabaacacb 7.70 babbabcbacbabccca 5.60 ccaabbbabbcb 3.70
Output
bbbca

Another large test Test
Input
350 12 fadaeeaf -8.26 ebbcabad 5.56 cabbaa -5.61 acededabac 5.57 debffc -9.73 effbcdafbf 4.77 abaaffbace -3.29 cfabae -4.27 dddacab 4.88 bacadfaa 7.36 ebdceaef -8.30 efdedcefa -3.83 dfacbfbabe -0.71 dcebbcb -3.15 fdbfade -0.06 cbdbceef -3.89 ebdbfbfd 5.12 eabdad -8.97 bfcffefacb -4.06 ddcbcaaced -4.58 bfaecdef 7.57 ffbfcfebde -8.42 aaeeafedd 1.66 eabdbdeed -5.84 ffaadb -5.33 ddacbddcc -4.76 bbfacecfe 1.74 bbcfdeaa -4.18 fcabfbbd -0.25 ecfabffc -1.53 beceffecd 6.54 ecbcba 4.67 abcaadac 2.97 bbfedb -1.57 cddcbea -2.80 deddecf -3.82 dfbbabdf -7.33 cadcde -0.59 bbedfbc 4.42 adfefcddf -5.47 edecdb -9.73 cafbbde -8.26 fdbeafca 3.75 fcdbbbb -0.03 bafbeefc -8.40 effcede -8.06 adddeeefae 6.93 fdefdfadc -9.32 ddcabba 8.92 ceecfbda 8.60 adaedfdbc 5.67 bfffda 3.72 fbbccae -1.24 dedeefaa 5.01 dccbefcdaf 9.22 dacdccfca -0.57 bcaccac 9.93 cceeceba 4.46 abdfbdda 5.16 bcbfbfb 4.68 feeafdfbe 1.89 bdbefaffe 1.43 ccdfebbbf 8.96 bfdcfcbf -9.00 cafeffdab 9.05 babcefcc -7.20 facedcbced 9.45 bfebfbde -5.40 bccccfbaf -0.66 ecbaccfe 2.70 adaeeeaa 8.03 ccacacaae 7.08 efefcc -6.86 fdfaabde -9.17 fafebfa -2.78 ebefcafbd -3.49 fefacc 7.53 dadcbaec -1.57 dabceb -7.08 eaddeeced 5.09 fbddfc -5.96 ecccbebad -0.28 bdbcfba -9.39 acacabb -2.56 aafffcfdcc -8.29 fbdcfaf -9.50 bbebfaa 9.02 bccafff 1.85 fcfdafdce -8.13 cbcfffaef -9.82 ffcede -0.31 ddaabefeb 1.91 cbdcfafafc 0.29 aadffccaaf -0.64 bfefdfce -1.48 baacbeda -3.56 bfdcbd 8.55 ddcacb -5.71 ccdaeedb -3.67 dbadba -6.48 dacbaaaaad 2.84 edbfabaefc -8.16 dcacabdd 1.34 cbdaaa 5.36 fbcffacbba -2.31 aafeadf -9.10 dfffbacbb -4.28 ffefdccad 7.58 bdfbcbddc -8.92 bcdcddbcd -6.61 cfcaacfe -4.19 dafaeb -4.55 fccbbcf 0.33 afebcbedfd -8.26 abfcaca 1.91 abedda 9.51 faeeebddb -9.83 caaffedcb 0.00 eeaebfe -8.40 ddfcfcfa 7.97 accacca 1.29 abbcffbbae -7.74 feffcdee -8.52 abbfcb 5.30 abfeccae -5.76 adcdaec -7.59 fabfaadc 6.19 dffcaacf 9.51 baeabce 6.11 bedebcfcec -4.14 bdcccecdeb -7.61 bccdaa -8.17 bfcbdebcd -2.09 ffeaed -3.35 ecabacbfc 8.62 dcefeab -9.08 dbacdddc -2.58 dcfafbece 3.60 deccadddff 5.24 aceebfba -2.26 dbbbddaa -7.25 bacceffffe -2.82 dabdffd 7.84 efcaca 0.99 decfffe 8.52 eadfcdafb -5.94 bacbaabad -3.77 bdebddc -3.27 ebbefcdafb 7.34 cafacbdee 2.33 aaceabfdfe -8.26 acbeade -0.98 bdbdfebad -0.56 aecaddfdf -8.08 bfbcccffab 2.50 eeadfbaaaf 9.31 decefccaac -7.72 dcfadcf -5.01 fefeebcbe -7.91 eeffcbda -3.01 acfbdccbad -5.05 daaefb -7.40 aadedbda -6.11 bdbbbacacd -1.52 fcffcfdac -3.02 fbaddec 1.30 eeadeaad -4.24 effeda 3.99 badffb 4.20 cabebcba 1.47 dbffabaaa 0.05 ceebdfccba -5.37 fcfabef 4.42 afbceedd 3.14 dcfacadc -8.89 affedbdda -2.98 acaddbedac 3.45 ceecfccfff 9.88 fdfeddc 9.31 fdcbaaae 8.62 cfcfec -5.42 afcdca 6.49 fcbaafdace 2.16 dbffabebe -5.52 afadaceb 0.17 aaecdbb 9.24 acaaecefdc -9.66 fdcfdefbcd -2.93 ceddacdf 8.23 dbcbdcf -8.25 edcddbd 1.19 dfddfaad 2.76 ecfdfcada -6.96 fbbceed 2.03 afacbaaa 2.28 cfcfbaaeed -7.78 cefddcdbe 8.45 ccebee 0.67 efaefc -4.58 fadbaadfe 8.10 dfcbeefcfb 3.75 bffbbefd -1.82 cbfecddac 5.30 feabbb -8.95 bedaacc -4.25 cccddbac 7.94 ebfebb 9.19 dbeeafdab 9.35 eaadefcb -3.28 aebdbadeca -1.32 faeebbb -5.24 faedef 3.73 bfedcbce 3.62 fefaae -8.18 eadabfabea 3.16 cbfdec -5.84 eecffaf 5.86 dddcfee 6.98 eccfacfed 2.48 cccfebba 2.23 accdbfad 5.51 bbaecd 0.03 feeaddafd -5.74 bbdaddcee 3.28 ccedddaaba 7.92 fbdcdbcba 6.71 eaffdea 1.76 bcccfbe 3.16 cebabfa 6.76 efedaddca -6.78 efcbfd -1.36 ceeefa 7.11 faecbfc 2.94 eadfdecefe -4.91 eeaaeacc -4.97 bffffcedc 8.29 dcbbaf -8.20 bedfaddbcc 5.90 eedbaaff -0.57 fecffa 5.10 cafcbe 2.30 dcbadaddf 9.43 fbdaefc -1.94 cebaeb -9.44 ebaceba -0.49 eccfebb -4.02 eefbbbed -7.58 cccebefc 6.08 aefdfdbad -6.89 edfcbad 9.84 accafdcccb 4.42 ddaaefbf -7.32 bbceebddfb 1.11 afafaef 9.44 fafdddedba -6.24 eebafb -9.20 ddcbea -6.54 fecece 1.82 ffcfdccdff 4.39 badebcbf 8.50 fcbbbd -6.25 abecbdbe 3.96 fdbfaddae 5.15 efeceef -6.57 aaaccbbc -5.91 aedecadcdf 5.73 fcfabedecb -6.40 babbffaf -3.02 afcbbfcdbd 6.67 bbaadcdeed -3.77 deedfbc 7.22 ceccbc 4.43 fddafeffed 7.42 febcfeecca -9.35 eddffdefea 1.46 efddbdcea -5.84 daefea -9.79 bfdeeccdbf 0.66 dbdeddfed 0.15 dacedaaf -0.80 cdefdcceed -4.93 aaeeaedc -4.88 bafefbccbb -0.01 bcafec 7.55 aeeafbcf 8.66 acabcae -3.26 bdcdadf 4.32 bfaadc -5.30 fdefaafcdd 7.64 bcdeffab -7.49 fdccbd -6.85 ebcafabbcd -6.19 feddceb 2.58 aaeadeb -7.57 badfacc 1.24 ccadcacda -2.67 aecfdef -8.41 edefbafc -2.13 aaaffeeafe -3.42 eacedbcfc -8.29 faaceef -6.85 dbeffacb -2.94 cdbefc -9.51 afbdffac -5.56 aeefdeb -3.55 dbcbcbbdf -9.16 cbaddefd 7.07 fdfbcea 5.22 efdccfbb 7.48 dbdebabcb 0.34 ffabec -1.74 fbaecefb 8.74 abebecdac 0.16 ddbeaaaec -3.37 bbaebcaa 8.41 bbbeddded -3.14 cfbacc 0.90 ececab 1.66 afccadf 8.04 adafadffec 8.52 dbabab -7.67 fcbaacddc 4.37 abccaeab -7.06 faaabfe -7.42 aefcaab -7.31 ceebeec -9.44 edfddfce -0.65 efeecdaf -6.58 eedceba 4.37 dcaabac -3.17 fabfeebbef 7.52 aafeccb -8.55 aebdcc -7.11 ecbdba 5.50 dabcdf -4.92 abdeedf 2.02 eebcaafde 8.02 afdfcdfa -4.03 fcdaafcec 7.36 bcfaaabffd -6.32 efeacb -9.70 febaeddec -5.65 befcffacd 4.09 dfabecdf 0.52 facadbceeb 2.48 ccbfcead 3.99 dcdbcfbdac 3.14 dbfbcdbec -0.63 ffdcdcdccd 6.72 fcadbcc 1.18
Output
ccb

Another large validator Validator
Input
403 1.41 baaabaaaab 0.91 babbbabbbbab 0.74 babbababbaa 0.78 bababaabbbbbbb 0.18 baabbbabbbbbab 0.50 bbababbaabbbaaa 0.53 abbbbabbaaa 0.57 bbbabbabaabbbbaa 0.95 bbabbaaaaaaaa 0.24 abbbbaaaaaabbb 0.66 baababaaababb 0.12 bbbbabababababab 0.36 ababbabbabaabbaa 0.48 aababaaabbabbba 0.14 abaabaabbaababaa 0.23 bbabbaabbbaa 0.30 abbabbbbabbbbab 0.96 aaaababbba 0.23 bbaabaabbbba 0.85 bbaaabbbbba 0.64 bbbbabaaba 0.30 aaaaabababbbb 0.53 bbbbaaaaaa 0.88 babaaaabbaa 0.63 bababaababbaaba 0.41 baabbbabbbbbb 0.33 abaaaaaaab 0.30 bbababbbbbbababb 0.23 bbabbbbbabbaaba 0.86 babbbabaaaba 0.11 bbabaabaabbabbbb 0.10 bbbaaababbbbabb 0.88 aaaabaabbb 0.14 abbabbabbbbb 0.97 baaaabbbaabbaaa 0.73 aabbabbbabbbaa 0.34 bbbbbbaaab 0.51 bbbbbabaaabba 0.17 aaaabbbaba 0.40 bbabbabbbbaabaa 0.55 babbbbaaaaaaaab 0.07 bbaabbaabbaa 0.15 bbaaabaabbb 0.35 babbbabbbbb 0.93 abbbbaabaabaa 0.66 bbbbabaaabaaaa 0.41 bbababbbbaababa 0.61 abababaaabbaab 0.86 aaabaabbbaa 0.82 bbbbaaabaa 0.17 baabababaabbba 0.03 bababbaaabbab 0.02 aaaaaaabab 0.13 abaaaaaaaaa 0.98 babaabbababaabaa 0.01 baabbaaabbaabab 0.45 bbbbaababbb 0.60 abaababaaa 0.27 aabbbaabbaa 0.83 abbbbabbabb 0.93 abaababaaa 0.14 abaaaabbababaaa 0.39 abaabbaaba 0.86 aaaaababaabaab 0.31 abbababababaaabb 0.50 baabaaaabaaaabba 0.13 abbbaaabbaa 0.69 aaaaababbababba 0.52 aaabbabaaabba 0.96 babaaaabaaaabab 0.54 aababaaaaba 0.99 aababbababbabaab 0.58 baaaaaabaaba 0.58 baaabbbaabbbab 0.12 bbaaabbbaababbbb 0.01 abbbbaaaabaa 0.22 bbaabaabaabbaa 0.12 abbbabaaababaaaa 0.56 abababbbbbabba 0.61 bbbbaababbaaaa 0.10 ababaababaaaaab 0.22 bbaaaaaabbbbaaa 0.64 bbbaabbaaabaa 0.17 bbbaabbaabbbba 0.71 abaaabbaabbab 0.38 abbaaabbbbaabaa 1.00 babbabbbaaabbbb 0.60 aabbaababbaaba 0.99 abaababbbbabaa 0.07 abbbaabaabbb 0.97 aabaababbaabbba 0.75 aabbbbbbaababa 0.98 aaabbbaabbbaabaa 0.56 bbbbbabbabbabbb 0.32 baaabaaabab 0.65 baaaaabbaba 0.52 bbaaabbbbaaaaaba 0.28 babbbabbbaababba 0.01 ababbababababa 0.99 aaaaabaaababa 0.78 bbbaaaabababbbb 0.84 aaaabaaaaab 0.91 abaabbbbbbbbbbab 0.10 baababbbbaaab 0.66 aabbabaabbababaa 0.95 abbaabbbbbab 0.52 baaaaaabbb 0.44 aabbaaaaaaaa 0.49 aaabbaaabaaabbaa 0.84 ababaaabababb 0.85 ababbabbaaa 0.00 bbbabbbabbaab 0.60 bbaabbbbabbbbb 0.13 baaabbbbbbbaabaa 0.68 abbabbbbbbb 0.01 babaababaabaaa 0.55 bbbaaaabbbabba 0.87 baaaababaaabbaa 0.65 babbababaabab 0.21 aaabababbabbba 0.09 baaabbababbaabb 0.56 aaabbbaaabb 0.74 babaaaaabbbbabb 0.30 abbabaabaabaaba 0.81 aaaabbabbbb 0.29 bbabababaaaba 0.20 baabbbababbaab 0.03 aabbbabbaaab 0.83 bbabaabaababba 0.42 baaabbabbaab 0.82 abbabaabbbbbaaab 0.54 aaababbabbb 0.59 bbabababaababb 0.10 babaaaaaaabb 0.84 bbababbbabbba 0.19 babbaabbbbabbbaa 0.60 aabaaabbabaabaaa 0.62 bbbabbaaabbbaaaa 0.61 bbbbbbabaaa 0.57 aaaaaabbaabb 0.30 aaaabbbbababbbab 0.37 aabbabaabbabaa 0.18 bbaabbaaabababa 0.91 aaabaabaabbbbb 0.14 ababababbbbaa 0.47 bbaabbababaaa 0.95 abbbbaabbbbb 0.49 abababbbbbb 0.02 bbabbbabbbabaab 0.28 ababbabaaba 0.25 bbbbbabaabbaa 0.96 aaaaaabbbbbbbb 0.86 babaaabbbaab 0.71 babbababbbbbba 0.33 baaabbabbaba 0.06 bbabbbbbaaab 0.89 bbabaabbaabbba 0.88 bbbbbabaaba 0.15 abbbabbabbabbba 0.74 abbbaabbaabb 0.31 aaabbbbabbabaa 0.39 bbabbababbbb 0.68 abbaabbabaabb 0.62 baababbbbbb 0.29 aabbbbabbbbabb 0.46 bbabbbababa 0.02 baaabaaabbbbb 0.56 abbaaabababaabaa 0.13 aaabbbabbbaaabab 0.76 bbaabbaaaa 0.77 abbababbaaa 0.81 babbbabbabbbaaba 0.43 ababaaaaaabb 0.48 bbbbbbbaaba 0.88 bbbbbabbababa 0.01 ababbaabbbb 0.11 baabbaaaaabbb 0.77 bbbbbaabbabbbbaa 0.32 baaabaabababaaba 0.49 bbaabaababbababa 0.95 abbababaabbbbb 0.25 babbaaabbabbaa 0.12 bbbbbbbbbabbbaaa 0.16 abaabbbbba 0.45 bbbabaaaaabaaa 0.06 bbbbabbbabaaa 0.96 aabbaaabbba 0.22 bbbaaaaaaaa 0.58 aaaaabaaabb 0.29 bbaaaaabbbaaabaa 0.66 aaabaababbbaaa 0.44 bbabbbaaaabaaa 0.99 bbbaaaabaaab 0.53 bbabaaaabaabbb 0.32 bbbbabbbbbb 0.61 aabbbbbababbab 0.50 babbbabaaaaba 0.11 abbbbabbbb 0.56 bbbbbaabbaaaabba 0.59 aaaabbbabbbababb 0.96 baaaabaabbbb 0.10 bbabbabbaaabaab 0.09 bababbabaa 0.78 bbbbbbbbbb 0.82 aaaaaaabbbaaaba 0.90 babbabbbaabbabb 0.08 bababbbbabbbaa 0.73 aaababaabb 0.28 baabababaaa 0.82 bbbabaabbaaab 0.88 bababaaaaba 0.87 aababbaabbbb 0.94 aababababa 0.10 bbbbababbabab 0.09 baaaaabbaabbab 0.59 aababbbababbaaa 0.78 bbbaaabaabababab 0.91 aabaaabbbaaa 0.67 baaaaaaaaabbab 0.98 abbababbabbb 0.43 baabaabbbbab 0.52 aabbbbbabb 0.44 abababbbabbb 0.68 baaaabaaaaabb 0.89 baababbaba 0.36 aaaababbaaabbb 0.70 aaaabbbaabab 0.42 babaaaabbbbbaa 0.49 bbabaaabbbb 0.17 abaaabaaababbab 0.97 bbbaaaabbaaba 0.76 babbaabbbbba 0.26 babaabababbaabb 0.17 abbabbabaaaa 0.32 baabbbbabaaaaaba 0.79 bbabbaabbbb 0.12 baaaabbbbaa 0.70 bbabbaaabb 0.14 aabbabbaabbababa 0.30 aabbbbababaabaa 0.28 aabbbbbaab 0.87 babababaaabb 0.96 babbabaabba 0.16 aabaabbabbaaaaa 0.47 baaabbaaba 0.55 aaabababbabbaaba 0.51 bbbbbbbbbaaa 0.68 baabbaabaaabbbaa 0.53 baabaabbaabbaabb 0.95 aaababbbbbababb 0.34 abaaaaababb 0.36 aaaabbababbb 0.28 ababbbbaaaabab 0.48 aabaabaaaa 0.55 aabbbaaababbbabb 0.68 bbaaaaaaabbbba 0.99 abbbabbbaabaa 0.42 aaabbbababbaa 0.68 baaaaaaaabbb 0.74 bbaababaab 0.37 baabbbbabbbabaab 0.89 ababbbaaababba 0.35 aaabaabaaa 0.91 ababbbabab 0.30 bbbaaabbbbbaaaaa 0.41 ababaabbbaaaaab 0.01 abbababbbabb 0.78 ababbaabaaaaab 0.04 baabaaabbbaa 0.20 bbaabbaaabbabb 0.66 bbabaaaaaaab 0.68 babaababbaaab 0.19 aababaaaaabbbbbb 0.79 aaabbbbbbaa 0.41 ababaababbabaab 0.85 babaabbabbbbaa 0.62 aaabaaabbb 0.60 babbaaaaaab 0.27 aabaaaabababaa 0.87 bbbabababbbb 0.32 aabbababbb 0.97 babaaabbbba 0.09 bbabbaababa 0.59 ababaabaabbbbaaa 0.94 bababbbbba 0.51 bbabaaaabb 0.71 bbbaabaabbabb 0.15 babababaab 0.81 abaaabbbaa 0.84 abbaaabbaab 0.78 bbaabbbabaab 0.08 bbaabbabbbbabaab 0.21 bbbaaabaaaab 0.59 aabbbaaaababa 0.41 babbbbabbbaaabaa 0.72 abbbaaaabba 0.69 babaabbbbabaabaa 0.34 aabbbbaabbaab 0.19 abbabaabbaaabbba 0.54 baabaabaaabbabaa 0.54 bbabaabababbb 0.31 bbbbbaaabaabbaba 0.77 abbbaabaaabaa 0.15 aabaaabbabbbbba 0.32 abbbbaaababb 0.92 bbbabbbaab 0.15 aaabbbaabaabb 0.85 abaaaabababbaa 0.37 bbbabaabaabb 0.16 ababbbbaaaaabaa 0.19 aaabaaababbbbaba 0.43 bbbbabbbaaba 0.94 bbbbaaaaabbbaba 0.01 abbabbabba 0.83 bababbbaabaaa 0.73 aaaaaaaabbaa 0.79 bbabaaabab 0.09 aaabababbbabbbb 0.36 aababbbbaaababa 0.88 bbbbaabaaaba 0.12 baabaabbababab 0.17 aaaabbaabb 0.90 aaabbbbaaaa 0.28 baaaabaaaba 0.82 bbaabbbbbaaaab 0.93 aabaaaaaabbabbba 0.75 bababbbabbaaa 0.98 bababaaababbbba 0.84 bbbaaabaaababaab 0.60 abaabbbbaa 0.52 babbbbabbbbb 0.88 abbaaababaaaba 0.02 babbabaaabaaaba 0.29 aaaaaabababb 0.22 aababaabab 0.29 abbaaabbbaaaab 0.03 aabababaabbbab 0.15 aaaaaaabbabbaa 0.05 abababbabbbb 0.39 bbabaabbbabbaaab 0.02 baabaaaabbabbab 0.51 aabaaaaabbba 0.68 aabbababaaa 0.69 aaabaabaaa 0.91 abbabbbbabaaabab 0.73 bababbbaaabbbba 0.32 aaabaababa 0.66 aababbaaabbaaa 0.47 bbabbabbbbb 0.45 bbaaabbabababab 0.73 babaabbbaab 0.11 baabbaabab 0.74 baabaabaabaa 0.08 abbbbbaabaaaaaba 0.28 bbaaaabbabaaa 0.89 aabbaaabab 0.22 aaaaaaabaa 0.16 babaabaabbbaabbb 0.59 babbabaaaaa 0.14 abaabaaabba 0.06 bbbbaabaabaa 0.95 abababaababa 0.80 abbaaaababbbbb 0.57 abbbbbabbb 0.25 abbaabaaaa 0.47 aaabbabbaabab 0.52 baababbaba 0.23 abbbaabbbba 0.07 aababbabbaba 0.11 abbbabaabb 0.30 bbbbbaabab 0.33 bbaabbaabbb 0.88 baabaababaab 0.17 bbbbbbababbaab 0.16 bbbbbaaabaaaa 0.26 baaabbaaaaaaa 0.21 babaabbabba 0.83 aaabaabaabbba 0.24 abaaaababb 0.83 bababbbabbba 0.90 ababaabbbbabaaba 0.60 aababbababa 0.87 bbbabaabbb 0.42 aabaabaabbabb 0.23 aaabbbbbabb 0.34 babbaaaaabbaa 0.97 baaaabaababb 0.95 baaaaabaaaaab 0.67 aabbaaabbaa 0.29 bbabbbabbbb 0.52 babbbbbbba 0.95 baaabbbbabaaba 0.38 bbaabaaabbbaabbb 0.28 abababaabbb 0.10 baabbabaaaabbaaa 0.13 abaaaabbaa 0.86 abbaaaabaa 0.49 abbbaabbbbbbaa 0.03 aaabaabbaaa 0.98 aababbbaabbabbb 0.23 baaaaabbbab 0.99 bbbbabaabbbbb 0.70 abaaaaabaaa 0.47
Output
aabbbaaa

Solution language

Solution

Stub generator input