WA in PARNTHSS

i don’t know why my solution is getting wrong… its a simple catalan problem …dont know where i screwed…plz help

def solve(n, k):  
    if (k > n - k): 
        k = n - k 
    res = 1
    for i in range(k): 
        res = res * (n - i) 
        res = res // (i + 1) 
    return res

def catalan(n): 
    c = solve(2*n, n) 
    return c//(n + 1)
    
for _ in range(int(input())):
	s=input()
	l=len(s)
	n=l-1
	print(catalan(n)%1000000007)

Your Code is correct. Actually the problem setter has added some extra-space after the sequence of characters in a line which is causing the error.
I tried your code with minor change and it’s working
Submission : https://www.codechef.com/viewsolution/33271965

P.S - It wasn’t your mistake.

1 Like

yeah, i used strip() then it’s working fine for test cases

How do we know that the answer is the (n-1)th catalan number?

The nth catalan number gives us the total number of valid sequences of n left and n right parentheses.

But if we look at the sample test case given in the problem( i,e abcd),there are 5 ways.
But those 5 ways given in the problem seem different to me than what the definition of the 3rd catalan number(i.e c3) suggests.

Sorry if i missed something trivial (i m still a newbie :slight_smile: ).

Number of ways to insert n pairs of parentheses in a word of n+1 letters, e.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)). For n=3 there are 5 ways, ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd)))…
in the problem you need to insert n-1 pair of parenthesis in the string such that none of the parenthesis include a single char except the one covering the whole string