Join Us
Loading Similar Posts
Entering edit mode
Q1 Help Your Master
Problem Description
GOAT-master got arrested in a police chase. He is trying to escape the high-tech prison he is held captive in. He needs a pass-code P for disabling all the cameras in order to escape. Passcode is the solution of matrix problem given below. Help him finding the pass-code.
You are given a matrix of order N×N. Each cell in a matrix has a value A : (o<=i,<N), which is either positive or equal to -1 (representing blocked cell)
Cells which are not blocked have distinct values. You can traverse from a cell in any direction (up, down, left or right), if there is no blockage.
For any cell Aj,j, sed-value S;,; is defined as sum of values of cells Ax, y which are multiple of Aj,j, but not reachable from A;,. For blocked cells, sed-value is -1.
Pass-code P is sum of sed-values of all the cells, modulo 1000000007.
Problem Constraints
1<=N<=1e3
1<=A[il [il<=1e6
A[il [j]=-1 for blocked cells only
Input Format
First argument is a 2-D array of integers denoting the above matrix.
Output Format
Return the sum of sed-values of all the cells, modulo 1000000007.
Example Input
Input 1:
[1, 3 ,-1, 5],
[-1,-1, -1 ,-1],
[2, 6 ,-1, 10],
[8, 7 ,- 1 ,11]]
Output 1:
68
Q2 XOR subsequences
Problem Description
You are given an array A, you have to create an array B which is a subsequence of A.
An array B is called valid if it satisfies both the conditions
- B[i] < B[i+1] where 1 <= i<|B|.
- bit_count( B[1] ^. ^ B[i-1] ^ B[i]) <= bit_count(B[i+1]) where 1 <= i < |B|.
.........
Let X be the Bitwise XOR of all the elements in valid array B.
You need to find the number of different values of X that can be formed.
Note: bit_count(t) is the number of set bits present in the binary representation of t
Problem Constraints
1 <= IAl <= 10^5
1 <= A[i] <= 100
Input Format
The first argument is an integer array A
Output Format
Return an integer denoting the number of different values of X that can be formed
Q3 .Space Race 2025
Problem Description
The year is 2025. The space race is in full motion. Elon Musk and Jeff Bezos have already launched their rockets into space. Bill Gates on the other hand, is struggling to even get started However, his good friend Elon, offers him his secret rocket fuel formula if Gates is able to solve a particular problem.
There are A planets Jeff's space company is not very good so he can only jump from the ith planet to the (i+1)th planet and (i+2)th planet. Let XJ be the array of integers representing the number of ways to get to the ith planet if Jeff starts from the 1st planet. XJ[0] would be 1. Since the values can be very large, consider them all modulo 1e9+7
Elon's space company is quite advanced compared to Jeff's. So from the ith planet, Elon's rocket can jump to all planets such that:
- For every set bit in XJ[i]'s binary representation, Elon's rocket when at the ith planet can jump ahead by values in the range [2^b, 2^bit+2]. •
- Let XII be 5. It's binary representation would be 101. Thus, from the ith planet, Elon's rocket will be able to jump ahead by [2^0, 2^1] u [2^2 2^3] where U is union.
- If i was, let's say, equal to 23 and XJ[i] was equal to 5 then from there, the rocket can jump to all values in these ranges [24, 25) U (27, 31).
Let XEbe the array of integers that denote the number of ways to get to the ith planet using Elon's rocket, starting from the 1st planet. Elon asks you the calculate this array. Since the values can be very large, consider them all modulo 1e9+7. XE[0] = 1
Problem Constraints
1 <= A <= 1e5
Input Format
The first and only argument is the integer A, denoting the number of planets.
Output Format
Return an array of integers as per the given problem.
Entering edit mode
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define pii pair<int,int>
#define ll long long
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool isValid(int x, int y, int n, vector<vector<int>>& A, vector<vector<bool>>& visited) {
return x >= 0 && y >= 0 && x < n && y < n && A[x][y] != -1 && !visited[x][y];
}
int solve(vector<vector<int>> &A) {
int n = A.size();
vector<vector<bool>> visited(n, vector<bool>(n, false));
ll result = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(A[i][j] == -1 || visited[i][j]) continue;
// Step 1: BFS to get all cells in this connected component
vector<pii> cells;
queue<pii> q;
q.push({i, j});
visited[i][j] = true;
while(!q.empty()) {
auto [x, y] = q.front(); q.pop();
cells.push_back({x, y});
for(int d = 0; d < 4; ++d) {
int nx = x + dx[d];
int ny = y + dy[d];
if(isValid(nx, ny, n, A, visited)) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
// Step 2: Build frequency map and value list
unordered_map<int, int> freq;
vector<int> vals;
for (auto [x, y] : cells) {
int val = A[x][y];
freq[val]++;
vals.push_back(val);
}
// Step 3: For each unique v in component, compute sed-value contribution
for (auto [v, f] : freq) {
ll sumDivisible = 0;
for (int x : vals) {
if (x % v == 0)
sumDivisible += x;
}
result = (result + f * sumDivisible) % MOD;
}
}
}
return (int)result;
}
int main() {
vector<vector<int>> A = {
{1, 3, -1, 5},
{-1, -1, -1, -1},
{2, 6, -1, 10},
{8, 7, -1, 11}
};
int result = solve(A);
cout << "Pass-code P = " << result << endl;
return 0;
}
Entering edit mode
Question 2 : XOR subsequences
Solution:
Approach:
We use a recursive backtracking strategy to explore all possible strictly increasing subsequences that meet the given conditions.
Starting from each index, we try to build a valid subsequence by recursively adding elements that:
Are greater than the last added element (to ensure the subsequence is strictly increasing).
Satisfy the bit_count constraint, i.e., the number of set bits in the XOR of the current path should be less than or equal to the bit count of the next element.
If an element meets both conditions, we add it to the current path and continue exploring further elements from the next index.
Whenever we reach a valid state (i.e., the current path is non-empty), we compute the XOR of the entire path and store it in a set to track distinct results.
If an element doesn’t satisfy the conditions, we simply skip it and try the next one.
This approach ensures that we explore all valid subsequences and collect all unique XOR values formed by them.
Code:
#include <bits/stdc++.h>
using namespace std;
int bit_count(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if ((1 << i) & n) count++;
}
return count;
}
void rec(int index, int n, vector<int>& arr, vector<int>& path, int pre_XOR, unordered_set<int>& result) {
if (!path.empty()) {
result.insert(pre_XOR);
}
for (int i = index; i < n; i++) {
if (path.empty() || (path.back() < arr[i] && bit_count(pre_XOR) <= bit_count(arr[i]))) {
path.push_back(arr[i]);
rec(i + 1, n, arr, path, pre_XOR ^ arr[i], result);
path.pop_back();
}
}
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
unordered_set<int> result;
vector<int> path;
rec(0, n, arr, path, 0, result); // pass pre_XOR = 0 at start
cout << result.size() << endl;
return 0;
}
Time Complexity: O(2^n), as we explore all increasing subsequences and insert their XORs into an unordered_set in constant time per insertion.
Space Complexity: O(n+2^n), where O(n) is for the recursion stack and O(2^n) for storing all possible unique XOR values in the set.
