My attempt of the following problem -> http://www.spoj.pl/problems/PERMUT3/ is getting TLE.
My approach is straight forward. Logic is to recurse over substrings by adding a new number (larger one) to the existing permutation.
For a given encoded string 's' of 0, 1's formed from input permutation, do the following:
1. If s starts with 0, i.e. s = 0x, then we include permutations formed, with encoded string x. In this case, we add n to beginning of all permutations formed, with encoded string x.
2. If s ends with 1, i.e. s = x1, then we include permutations formed, with encoded string x. In this case, we add n to end of all permutations formed, with encoded string x.
3. Is s contains 10, i.e. s = x10y, then we include permutations formed, with encoded strings x and y. Here we add n where '10' encoding occurs.
This is the beautified code, since src limit is 512, the original looks pretty shabby.
[bbone=python,361]
import sys, string, array
def nCk(i,j):
n = m = 1
for k in range(j):
n = n * (i-k);
m = m * (k + 1)
return n / m
def permute3(a):
if dp.has_key(a):
return dp.get(a)
n = len(a)
ans = 0
if n < 2:
return 1
if a[0] == '0':
ans += permute3(a[1:n])
if a[n-1] == '1':
ans += permute3(a[0:n-1])
for i in range(n-1):
if a[i] == '1'and a[i + 1] == '0':
ans += permute3(a[0:i]) * permute3(a[i+2:n]) * nCk(n, i+1)
dp[a] = ans;
return ans
def read():
return sys.stdin.readline()
dp={}
n = int(read())
while(n > 0):
words = string.split(read());
a=""
for i in range(n-1):
a += ("1" if int(words[i]) < int(words[i + 1]) else "0")
print permute3(a);
n = int(read())
[/bbone]
