Challenge: Palindromes
Subdomeniu: Probability (probability)
Scor cont: 40.0 / 40
Submission status: Accepted
Submission score: 1.0
Submission ID: 464751765
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/palindromes/problem
Cerinta
Given a string, you keep swapping any two characters in the string randomly till the string becomes a palindrome. What is the [expected number](http://en.wikipedia.org/wiki/Expected_value) of swaps you will make? There will always be at least one palindrome which can be formed with the letters of the given string.
**Input:**
The first line contains the number of test cases T. Each of the next T lines contains a string each.
**Output:**
Output T lines containing the answer for the corresponding test case. Print the answer correct to 4 decimal places.
**Constraints:**
T <= 10000
The length of the string will be at most 8 characters.
The string will consist of only lower-case letters 'a'-'z'.
**Sample Input:**
4
b
bb
abb
cbaabbb
**Sample Output:**
0.0000
0.0000
3.0000
59.3380
**Explanation:**
For the first two cases, the string is already a palindrome so no swaps are needed.
For the third case, there are 3 possible swaps. The string will become "bab","bba" or remain "abb" with 1/3rd probability each. It's easy to see that the expected number of swaps needed is 3.0000
For the last case, the answer is 59.337962..., which should be printed as 59.3380Cod sursa
#!/bin/python3
import os
import sys
from collections import Counter, defaultdict
def canonicalize(s: str) -> str:
mp = {}
nxt = 0
out = []
for ch in s:
if ch not in mp:
mp[ch] = chr(ord('0') + nxt)
nxt += 1
out.append(mp[ch])
return ''.join(out)
def is_palindrome(s: str) -> bool:
return s == s[::-1]
def is_non_absorbing_valid_state(s: str) -> bool:
# Non-absorbing: not already palindrome.
if is_palindrome(s):
return False
# Reachable palindrome condition for this multiset.
cnt = Counter(s)
odd = sum(v & 1 for v in cnt.values())
return odd == (len(s) & 1)
def generate_all_canonical_states(max_len: int = 8):
seen = set()
all_states = []
def dfs(cur: str):
c = canonicalize(cur)
if c in seen:
return
seen.add(c)
all_states.append(c)
if len(c) < max_len:
for ch in '0123':
dfs(c + ch)
dfs('')
return all_states
def solve_group(states):
m = len(states)
idx = {s: i for i, s in enumerate(states)}
n = len(states[0])
pairs = n * (n - 1) // 2
p = 1.0 / pairs
# Augmented matrix [A | b], where A * E = b.
mat = [[0.0] * (m + 1) for _ in range(m)]
for s, i in idx.items():
mat[i][i] = 1.0
mat[i][m] = 1.0
arr = list(s)
for a in range(n):
for b in range(a + 1, n):
arr[a], arr[b] = arr[b], arr[a]
t = ''.join(arr)
arr[a], arr[b] = arr[b], arr[a]
if is_palindrome(t):
continue
tc = canonicalize(t)
j = idx[tc]
mat[i][j] -= p
# Gaussian elimination with partial pivoting.
for col in range(m):
piv = col
for r in range(col + 1, m):
if abs(mat[r][col]) > abs(mat[piv][col]):
piv = r
mat[col], mat[piv] = mat[piv], mat[col]
pv = mat[col][col]
# Normalize pivot row.
for j in range(col, m + 1):
mat[col][j] /= pv
# Eliminate in all other rows.
for r in range(m):
if r == col:
continue
fac = mat[r][col]
if abs(fac) < 1e-15:
continue
for j in range(col, m + 1):
mat[r][j] -= fac * mat[col][j]
res = {}
for s, i in idx.items():
res[s] = mat[i][m]
return res
def precompute_expectations():
all_states = generate_all_canonical_states(8)
valid_states = [s for s in all_states if is_non_absorbing_valid_state(s)]
groups = defaultdict(list)
for s in valid_states:
sig = (len(s), tuple(sorted(Counter(s).values(), reverse=True)))
groups[sig].append(s)
ans = {}
for states in groups.values():
ans.update(solve_group(states))
return ans
def main():
expect = precompute_expectations()
data = sys.stdin.read().strip().split()
if not data:
return
t = int(data[0])
out = []
ptr = 1
for _ in range(t):
s = data[ptr]
ptr += 1
if len(s) <= 1 or is_palindrome(s):
out.append('0.0000')
else:
c = canonicalize(s)
out.append(f"{expect[c]:.4f}")
sys.stdout.write('\n'.join(out))
if __name__ == '__main__':
main()
HackerRank Probability – Palindromes