Question

DE Shaw - OA - Intern - 2022 | Set-24 | 2022

Answer 1

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;

 

}

Answer 2

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()

Answer 3

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?