0 like 0 dislike
1,033 views
| 1,033 views

0 like 0 dislike

Can be solved using dp.
dp[x][y[z][w][k=0/1/2/3] being our current state
k represents current animal breed
Transitions are simple
for simplicity, let k=0
dp[x][y][z][w][0] = dp[x-1][y][z][w][1]+dp[x-1][y][z][w][2]+dp[x-1][y][z][w][3]
bases case is
dp[0][0][0][0][0/1/2/3] = 1;

Maybe this works fine:

// initialize with -1;
int dp[lions+1][tigers+1][leopards+1][panthers+1][4];
int helper(int lions,int tigers,int leopards,int panthers,int last){

``````if(lions ==0 and tigers==0 and leopards==0 and panthers==0){
return 1;
}

if(dp[lions][tigers][leopards][panthers][last] != -1){
return dp[lions][tigers][leopards][panthers][last];
}

int ways = 0;
if(last == 0){
if(tigers > 0){
ways += helper(lions,tigers-1,leopards,panthers,1);
}
if(leopards > 0){
ways += helper(lions,tigers,leopards-1,panthers,2);
}
if(panthers > 0){
ways += helper(lions,tigers,leopards,panthers-1,3);
}
}
if(last == 1){
if(lions > 0){
ways += helper(lions-1,tigers,leopards,panthers,0);
}
if(leopards > 0){
ways += helper(lions,tigers,leopards-1,panthers,2);
}
if(panthers > 0){
ways += helper(lions,tigers,leopards,panthers-1,3);
}
}
if(last == 2){
if(lions > 0){
ways += helper(lions-1,tigers,leopards,panthers,0);
}
if(tigers > 0){
ways += helper(lions,tigers-1,leopards,panthers,1);
}
if(panthers > 0){
ways += helper(lions,tigers,leopards,panthers-1,3);
}
}
if(last == 3){
if(lions > 0){
ways += helper(lions-1,tigers,leopards,panthers,0);
}
if(tigers > 0){
ways += helper(lions,tigers-1,leopards,panthers,1);
}
if(leopards > 0){
ways += helper(lions,tigers,leopards-1,panthers,2);
}
}

return dp[lions][tigers][leopards][panthers][last] = ways;
``````

}

by Expert (111,350 points)
0 like 0 dislike
it can be solved using backtracking. Here's a memozized version:

def count_perm(x, y, z, w):

# last: (0, 1, 2, 3) == (x, y, z, w)
@lru_cache(None)
def solve(x=x, y=y, z=z, w=w, last=0):
if x < 0 or y < 0 or z < 0 or w < 0: return 0
if x == 0 and y == 0 and z == 0 and w == 0: return 1
ans = 0
if last == 0:
# last is x -> can use y/z/w
ans += solve(x, y - 1, z, w, 1) + solve(x, y, z - 1, w, 2) + solve(x, y, z, w - 1, 3)
elif last == 1:
# last is y -> can use x/z/w
ans += solve(x - 1, y, z, w, 0) + solve(x, y, z - 1, w, 2) + solve(x, y, z, w - 1, 3)
elif last == 2:
# last is z -> can use x/y/w
ans += solve(x - 1, y, z, w, 0) + solve(x, y - 1, w, 1, 1) + solve(x, y, z, w - 1, 3)
elif last == 3:
# last is w -> can use x/y/z
ans += solve(x - 1, y, z, w, 0) + solve(x, y - 1, z, w, 1) + solve(x, y, z - 1, w, 2)
return ans % 1000000007

return solve()
by Expert (111,350 points)
0 like 0 dislike
There are x lions, y tigers, z leopards, and w panthers. Find the number of ways to place them on a line such that no two same animals are adjacent to each other. (0<=x,y,z,w<=51)

I didn't get this during the test, but can this be solved using backtracking?
by Expert (111,350 points)