You are viewing a single comment's thread. Return to all comments →
#!/bin/python3 import os import sys from collections import Counter def mapString(s): counter = 0 map_val = {} s_ = '' for el in s: if el not in map_val: map_val[el] = counter counter += 1 s_ += str(map_val[el]) return s_ def isValid(s): if s == s[::-1]: return False char_counts = Counter(s) no_odds = 0 for (el, c)in char_counts.items(): if c % 2: no_odds += 1 if len(s) % 2: return not bool(no_odds - 1) return not bool(no_odds) def generateAllPossible(s, allStates): s = mapString(s) if s in allStates: return allStates.append(s) if len(s) < 8: generateAllPossible(s + '0', allStates) generateAllPossible(s + '1', allStates) generateAllPossible(s + '2', allStates) generateAllPossible(s + '3', allStates) def generateTransitionMatrix(tr_matrix, states, state_to_index): for s in states: x_val = state_to_index[s] no_of_swap = len(s) * (len(s) - 1) / 2 for i in range(len(s)): for j in range(i + 1, len(s)): s_ = mapString(s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:len(s)]) if isValid(s_): y_val = state_to_index[s_] tr_matrix[x_val][y_val] -= 1/no_of_swap def swap_row(m, i, j): temp_row = m[i] m[i] = m[j] m[j] = temp_row def forwardElim(m): for k in range(len(m)): i_max = k v_max = m[i_max][k] for i in range(k+1, len(m)): if (abs(m[i][k]) > v_max): v_max = m[i][k], i_max = i if (i_max != k): swap_row(m, k, i_max); for i in range(k+1, len(m)): f = m[i][k] / m[k][k]; for j in range(k+1,len(m) + 1): m[i][j] -= m[k][j] * f m[i][k] = 0 def backSub(m): x = [0 for _ in range(len(m))] N = len(m) for i in reversed(range(N)): x[i] = m[i][N] for j in range(i+1, N): x[i] -= m[i][j] * x[j] x[i] = x[i] / m[i][i] return x def findSolutions(tr_matrix): forwardElim(tr_matrix); return backSub(tr_matrix) def preprocess(): states = [] generateAllPossible('', states) states = list(filter(isValid, states)) tr_matrix = [[float(i == j) for i in range(len(states))] for j in range(len(states))] states_to_index = {} for (ind, s) in enumerate(states): states_to_index[s] = ind generateTransitionMatrix(tr_matrix,states, states_to_index) for i in tr_matrix: i += [1] ans = findSolutions(tr_matrix) return (ans, states_to_index) if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') (ans, states_to_index) = preprocess() t = int(input()) for t_itr in range(t): s = input() if(len(s) != 1 and s != s[::-1]): index = states_to_index[mapString(s)] result = round(ans[index],4) else: result = 0 fptr.write('%.4f\n'%result) fptr.close()
getting a timeout, how do i speed it up
Seems like cookies are disabled on this browser, please enable them to open this website
Palindromes
You are viewing a single comment's thread. Return to all comments →
getting a timeout, how do i speed it up