Join Us
Loading Similar Posts
Entering edit mode
Question 1: Magical Pathway Puzzle
Problem Statement:
Ella is exploring a magical forest filled with glowing stones arranged in a line. These stones are numbered from 1 to N, with the first stone at position 1 and the last at position N. Ella starts outside the forest, just before the first stone. She can step forward to either the next stone or skip a stone to land two stones ahead. However, some stones are cursed and cannot be stepped on. If Ella steps on a cursed stone, she will be teleported back to the start.
Your task is to help Ella find and return an integer value representing the number of ways she can safely reach the Nth stone without stepping on any cursed stones. If there is no possible way to reach the last stone, return 0.
Note:
The answer may be large, so return the answer modulo 10^9 + 7.
The array follows 1-based indexing.
Input Specification:
input1: An integer value N, representing the total number of stones.(Additional inputs for cursed stones would follow).
Question 2: Maximum Fruits to Collect
Problem Statement:
Evan is planning to collect some fruits from a garden. The garden is described in a M \times N matrix, where every element of the matrix represents the number of fruits in that cell.
Evan is initially in the X^{th} row and Y^{th} column and can only take K steps to collect the fruits. In every step, he can move to any one of the four adjacent cells and can collect the fruit present in that cell.
Your task is to find and return an integer value representing the maximum number of fruits that Evan can collect in K steps.
Note:
- Each cell can be visited only once.
- The starting position of Evan will always have 0 fruits.
- The matrix has 1-based indexing.
Input Specification:
- input1: An integer value M representing the number of rows in the matrix.
- input2: An integer value N representing the number of columns in the matrix.
(Inputs for X, Y, K, and the matrix grid would follow).
Question 3: Project Launch
Problem Statement:
As a project manager, Emily is overseeing the launch of several marketing campaigns. She has X different campaign ideas and can combine these ideas to create a powerful new marketing strategy. She can use at most Y ideas in any combination to craft a new marketing approach.
Your task is to help Emily determine how many different marketing combinations she can craft from the existing campaign ideas and return an integer representing the total number of possible strategies, including the original ideas.
Note:
- Return answer modulo 10000.
Input Specification:
- input1: An integer value X, representing the number of different campaign ideas.
- input2: An integer value Y, representing the maximum number of ideas that can be used to create a new marketing strategy.
Entering edit mode
Problem 1 Solution:
Magical Pathway Puzzle
Topics Involved / Prerequisites
- Dynamic Programming (1D)
- Modular Arithmetic
Overview This is a variation of the classic "Climbing Stairs" problem. Ella can reach stone i either from stone i-1 (a 1-step jump) or from stone i-2 (a 2-step jump). The total number of ways to reach stone i is the sum of the ways to reach those two preceding stones, provided they are not cursed.
Approach
- State Definition: Let dp[i] be the number of ways to reach stone i.
- Initialization: Ella starts at position 0 (outside the forest). So, dp[0] = 1.
- Transitions: Iterate from stone 1 to N:
- If stone i is cursed, dp[i] = 0 (she can't step here).
- Otherwise, dp[i] = dp[i-1] + dp[i-2]. (Check bounds to ensure i-2 >= 0).
- Modulo: Apply modulo 1,000,000,007 at each addition to prevent integer overflow.
Code Implementation ( c++)
#include <iostream>
#include <vector>
using namespace std;
int magicalPathway(int N, const vector<int>& cursed) {
int MOD = 1000000007;
// dp[i] represents ways to reach stone i
vector<int> dp(N + 1, 0);
// Base case: 1 way to be at the starting position (0)
dp[0] = 1;
for (int i = 1; i <= N; ++i) {
if (cursed[i]) {
dp[i] = 0;
} else {
// Step from 1 stone behind
dp[i] = dp[i - 1];
// Step from 2 stones behind
if (i >= 2) {
dp[i] = (dp[i] + dp[i - 2]) % MOD;
}
}
}
return dp[N];
}Time and Space Complexity
- Time: O(N) — We iterate through the N stones exactly once.
- Space: O(N) — To store the DP array. (This can be optimized to O(1) by only keeping track of the last two valid positions, but an array is safer if cursed stones are passed as an array).
Entering edit mode
Problem 2 Solution:
Maximum Fruits to Collect
Topics Involved / Prerequisites
Backtracking / Depth First Search (DFS)
Matrix Traversal
Overview Because Evan can move in 4 directions and cannot revisit cells, this problem requires exploring all possible paths of length K. Since K is a hard limit, we can use Backtracking to explore every valid path up to K steps, keeping track of the maximum fruits collected across all paths.
Approach
DFS Setup: Start a recursive DFS from
(X-1, Y-1)(converting 1-based input to 0-based indexing).Tracking Variables: Pass the current step count and the current sum of fruits down the recursive calls.
Base Case: If the current step count reaches K, evaluate if the current sum is greater than the global maximum. Do not go further.
Recursive Step: Check all 4 adjacent cells (Up, Down, Left, Right). If a cell is within bounds and not visited, mark it as visited, add its fruits to the current sum, recursively call DFS for the next step, and then backtrack (unmark it as visited) to allow other paths to use it.
Code Implementation (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxFruits = 0;
// Direction arrays for Up, Down, Left, Right
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
void dfs(int x, int y, int steps, int currentFruits, int K, int M, int N, const vector<vector<int>>& grid, vector<vector<bool>>& visited) {
maxFruits = max(maxFruits, currentFruits);
if (steps == K) return;
// Explore all 4 adjacent cells
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < M && ny >= 0 && ny < N && !visited[nx][ny]) {
visited[nx][ny] = true;
dfs(nx, ny, steps + 1, currentFruits + grid[nx][ny], K, M, N, grid, visited);
visited[nx][ny] = false; // Backtrack
}
}
}
int getMaximumFruits(int M, int N, int X, int Y, int K, const vector<vector<int>>& grid) {
vector<vector<bool>> visited(M, vector<bool>(N, false));
maxFruits = 0;
// Convert 1-based inputs to 0-based indices
int startX = X - 1;
int startY = Y - 1;
visited[startX][startY] = true;
dfs(startX, startY, 0, 0, K, M, N, grid, visited);
return maxFruits;
}Time and Space Complexity
Time: O(4^K) — In the worst case, from every cell, we branch out in 3 to 4 directions up to K depth.
Space: O(M * N) — To store the visited matrix, plus O(K) for the recursive call stack depth.
Entering edit mode
Problem 3 Solution
Project Launch
Topics Involved / Prerequisites
Combinatorics
Pascal's Triangle (Dynamic Programming)
Overview Emily needs to find the sum of all combinations of choosing i ideas from X total ideas, where i ranges from 1 to Y. Mathematically, this is evaluating the formula:
Because the modulo is 10000 (which is not a prime number), using standard modular inverse formulas for combinations is risky. Generating Pascal's Triangle using DP is the safest way to compute combinations while applying the modulo at every addition.
Approach
- Edge Case: If Y > X, we cap Y at X because she cannot choose more ideas than exist.
- Pascal's Triangle: Create a 2D array C where C[n][k] stores nck .use the identi
- Build DP: Use the identity
- ( n)c( k ) = ( n − 1 )c(k − 1 ) + ( n − 1 )c(k )
- Apply modulo 10000 at each addition.
- Sum: Loop from i = 1 to Y and add C[X][i] to a running total, applying modulo 10000 to the total.
Time and Space Complexity
- Time: O(X * Y) — To build up the combinations table up to X and Y.
- Space: O(X * Y) — To store the 2D DP matrix.
Code Implementation (C++)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int projectLaunch(int X, int Y) {
int MOD = 10000;
if (Y > X) Y = X;
vector<vector<int>> C(X + 1, vector<int>(Y + 1, 0));
// Build Pascal's triangle
for (int i = 0; i <= X; i++) {
for (int j = 0; j <= min(i, Y); j++) {
if (j == 0 || j == i) {
C[i][j] = 1;
} else {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
}
int totalStrategies = 0;
for (int i = 1; i <= Y; i++) {
totalStrategies = (totalStrategies + C[X][i]) % MOD;
}
return totalStrategies;
}
