Submission #768389

#	Time	Username	Problem	Language	Result	Execution time	Memory
768389		himanshu3889	Kangaroo (CEOI16_kangaroo)	Pypy 3	100 / 100	123 ms	52204 KiB

kangaroo

import sys,math
from bisect import bisect_left , bisect_right 


def rd(): return sys.stdin.readline().strip()
def rdl(typ,sep=" "): return list(map(typ, rd().split(sep)))
def wt(x,sep="\n") : sys.stdout.write(str(x) + sep)    # string / num
def wtBoolUp(x): wt("YES" if x==True else "NO")  # True = YES/ False =NO
def wtBoolLow(x): wt("Yes" if x==True else "No")  # True = Yes/ False =No
def wtlArr(arr,sep=" "): sys.stdout.write(sep.join(map(str,arr)) + "\n") if arr else None  # Print arr in single line
def wtlsArr(arr): sys.stdout.write("\n".join(map(str,arr)) + "\n") if arr else None  # Print arr in mult lines
def wtlsArrArr(arr):    # print Arrays in multiple lines
    for a in arr: wtlArr(a)

# for dfs use this and use 'yield' during dfs and at last
from types import GeneratorType
def bootstrap(f, stack=[]):              
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

INF = float("inf") 
mod = 10**9 + 7    

def binPow(a,b,mod) :
    res = 1
    while b :
        if b % 2: 
            res = res * a % mod
        a = a * a % mod
        b //= 2
    return res

def invMod(x,mod): return pow(x,mod-2,mod)      

def getFacts(n,mod):   # O(n)
    fact = [1]*(n+1)
    for i in range(2,n+1): fact[i] = (i*fact[i-1])%mod
    return fact

def nCr(n, r, fact, mod) :  # O(logMOD)
    num = fact[n]       # numerator
    den = (fact[r] * fact[n - r]) % mod   # denominator
    return (num * invMod(den, mod)) % mod

def lcm(num1,num2):
    hcf = math.gcd(num1,num2)
    lcm_ = (num1*num2)//hcf
    return lcm_

def sqrtFloat(num):  # req : https://codeforces.com/contest/1809/problem/B
    l, r = 0 , num
    res = 0
    while l <= r :
        mid = (l+r)//2
        if mid*mid <= num :
            res = mid
            l = mid + 1
        else : #number will be on l side
            r = mid-1
    
    return res + 0.1*(res*res != num)

def prefixSum(arr):   # 0 at last of prefix sum
    pref = [0]*(len(arr)+1)
    for i in range(len(arr)): pref[i] = arr[i] + pref[i-1]
    return pref

def prefixXor(arr):   # 0 at last of prefix Xor
    pref = [0]*(len(arr)+1)
    for i in range(len(arr)): pref[i] = arr[i] ^ pref[i-1]
    return pref

def apSum(n):  return n*(n+1)//2   # [1,n]
def apSumRange(l,r) : return apSum(r)-apSum(l-1)  # [l,r]

def hypot(p1,p2):
    return ((p2[0]-p1[0])**2 + (p2[1]-p1[1])**2)**0.5
def manhat(p1,p2):
    return abs(p2[0]-p1[0]) + abs(p2[1]-p1[1])

def comb(n,r):   # for small x otherwise TC higher
    res = 1
    for i in range(r) : res = res*(n-i)//(i+1)   # res*(n-i) % (i+1) == 0  always
    return res

def powerArr(base,n,mod):
    pwr = [1]*n
    for i in range(1,n):
        pwr[i] = (base*pwr[i-1]) % mod
    return pwr

def getClosest(num,sortArr,notTake=-INF,notTakeCnt=1):
    idx = bisect_left(sortArr,num)  # find closest to x , not take notTake
    closeArr = []
    for i in range(max(0,idx-2),min(len(sortArr),idx+3)) : # [idx-2,idx-1,idx,idx+1,idx+2]
        if notTakeCnt>0 and sortArr[i] == notTake:
            notTakeCnt -= 1
            continue
        closeArr.append(sortArr[i])
    return min(closeArr, key=lambda x:abs(x-num),default=-INF)

def group(arr, notTake=INF):  # grouping of similar elements
    n = len(arr)
    res = []
    i = 0
    while i < n:
        st = i
        while i+1 <n and arr[i] == arr[i+1] :
            i += 1
        if arr[st] != notTake:
            res.append([arr[st],st,i,i-st+1])
        i += 1
    return res

def dirnsRD() : return [(0,1),(1,0)]
def dirnsLU() : return [(0,-1),(-1,0)]
def dirns(): return dirnsRD() + dirnsLU()
def dirnsDiag(): return dirns() + [(1,1),(1,-1),(-1,1),(-1,-1)]
def chessDirns(): return [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

def cntBits(n): return bin(n).count("1")
def isRepSumP2(num, x): return cntBits(num) <= x <= num  # num in sum two's power in x moves ?
def binry(decimal): return bin(decimal).replace('0b', '')
def deciml(binary): return int(str(binary),2)
def printAllBin(arr):
    maxLen = len(binry(max(arr)))
    for x in arr:
        curr = binry(x)
        res = " ".join(list("0"*(maxLen-len(curr))+curr))
        wt( res + f"   <- {x}")

def c2i(ch,up=0): return ord(ch) - ord('A' if up else 'a')  # ch to integer
def i2c(n,up=0): return chr(ord('A' if up else 'a') + n)    # integer to ch

def setPrec(num, cnt): return round(num, cnt)
def flush(): sys.stdout.flush()
def clearCache(func): func.cache_clear()   # used to clear the lru cache for every new test case



# >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
''' ॐॐ _/\_ हर हर महादेव _/\_ ॐॐ '''

# sys.setrecursionlimit(300_005)
mod = 10**9 + 7



# Additionally, we want to impose the additional restriction that in a component, 
# the first number must be less than than the second number, 
# and the last number must be less than the second-to-last number. 
# (This means that (132) is allowed as a component, but (12)
#  would not be even though it follows the alternating pattern).
def solve():
    n,s,e = rdl(int)
    ##  -----------------------------------------  
    
    dp = [[0]*(n+2) for _ in range(n+2)]
    dp[1][1] = 1

    for i in range(1, n):
        for comp in range(1, i+1):
            if i+1 == s or i+1 == e:    # adding endpoints
                dp[i+1][comp+1] += dp[i][comp] *1    # create new component at leftmost / rightmost
                dp[i+1][comp+1] %= mod
                # merge with components : s join leftmost start, e join rightmost end
                dp[i+1][comp] += dp[i][comp] *1     
                dp[i+1][comp] %= mod
                ### merge two components not allowed since want first or at last ###
            else:
                # create new component
                ways = comp+1 - (i+1>s) - (i+1>e)  # s / e placed down
                dp[i+1][comp+1] += dp[i][comp] * ways
                dp[i+1][comp+1] %= mod
                ## merge with components is not allowed since 132 allow but 12 not allow###
                # merge two components
                dp[i+1][comp-1] += dp[i][comp] * (comp-1) 
                dp[i+1][comp-1] %= mod
        
    return dp[n][1]
    
    


# Don't forget the mod and recursion limit

wt(solve())

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49