1 day ago

Sarthak • 10

Hyderabad

Question 1: Hazardous Chamber (Ion Particles)

Problem Statement:

You are exploring a hazardous chamber filled with ion particles arranged in a line. Each particle i has an intensity I[i].

Whenever you decide to activate particle i, it releases an ion trail of magnitude:

trail_i = I[i] % (i + 3)

This trail interferes with future particles. After choosing particle i, any later particle j > i becomes unstable (and therefore cannot be selected) if:

((I[j] xor I[i]) % 6) == trail_i

Your goal is to select as many stable particles as possible, in strictly increasing index order. You may choose or skip any particle, but once a particle becomes unstable, it cannot be chosen later.

Find the maximum number of particles you can select while respecting instability rules.

Input Format:

• The first line contains an integer, N, denoting the number of particles.
• Each line i of the N subsequent lines (where 0 \le i < N) contains an integer describing the intensity I[i].

Question 2: Medium : Spectral Lockstep

Problem Statement:

You are an explorer of the Aurora Vaults, facing a line of spectral nodes numbered from 1 to N. Each node i glows with a spectral value S[i].

Every time you include a node in your expedition log, it prints a single-colour key into the vault's ledger:

Key(i) = (S[i] + i) % 5

But the ledger is tricky: as soon as you record node i, all later nodes j (j > i) whose(S[j] % 5)equalsKey(i)become locked — you cannot record them later in your sequence. Nodes already recorded remain safe.

You may decide, at each position scanning left to right, whether to record that node or skip it. Your aim is to record a sequence of nodes (strictly increasing indices) of maximum possible length under the locking rule.

Find the maximum possible length under the locking rule.

Input Format:

• The first line contains an integer, N, denoting the number of spectral nodes.
• (The subsequent lines will contain the spectral values S[i] for each node).

13 hours ago

admin 1.9k

Hyderabad

Problem1 Solution

Hazardous Chamber (Ion Particles) Solution

Topics Involved / Prerequisites

• Dynamic Programming
• Graph Theory (Longest Path in a Directed Acyclic Graph)
• Bitwise Operations and Modular Arithmetic

Overview

The goal is to find the longest sequence of particles where each particle is stable relative to the one chosen before it. We can model this as finding the longest path in a directed acyclic graph, where a directed edge exists from an earlier particle to a later particle only if the earlier particle's trail does not destabilize the later one.

Approach

1. State Definition

We use Dynamic Programming. We maintain an array dp where dp[i] stores the maximum sequence length that strictly ends at the particle index i. Every particle can, at a minimum, form a sequence of length 1 (just itself).

2. Transition and Checking Stability

We iterate through each particle i from left to right. For each particle, we look back at all previously evaluated particles j (where j < i). We calculate the trail emitted by j, and check the instability formula. If the current particle i is stable against j, it means we can safely extend the sequence that ended at j. We update dp[i] to be the maximum of its current value or dp[j] + 1. The overall answer is the maximum value found anywhere in the dp array.

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int findMaxStableParticles(int n, const vector<int>& intensities) {
        if (n == 0) return 0;

        vector<int> dp(n, 1);
        int max_particles = 1;

        // Step 1 & 2: Build the DP array
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
               
                int trail_j = intensities[j] % (j + 3);
                
            
                if (((intensities[i] ^ intensities[j]) % 6) != trail_j) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        
            max_particles = max(max_particles, dp[i]);
        }

        return max_particles;
}

Time Complexity

• Time: O(N^2) - We use a nested loop structure. For each of the N particles, we look back at all previous particles, resulting in quadratic time.
• Space: O(N) - We require an auxiliary array of size N to store the dynamic programming states.

13 hours ago

admin 1.9k

Hyderabad

Problem 2 Solution

Spectral Lockstep Solution

Topics Involved / Prerequisites

• Dynamic Programming
• State Compression (Bitmasking)

Overview

• Selecting a node permanently locks out future nodes that share a specific property, functioning as a bounded state constraint.
• Because there are only five possible keys that can be locked, we can perfectly represent the locked state using a bitmask.
• Evaluating transitions backward ensures we optimally decide whether to pick or skip each node based on future consequences.

Approach

1. The Bitmask State

We use state compression to represent our dynamic programming matrix. Our state represents the maximum number of nodes we can pick from a specific suffix of the array, given the currently locked keys represented by an integer mask. A bit set to 1 in the mask means that specific modulo 5 value is currently banned.

2. Bottom-Up Transitions

We iterate backward from the last node to the first. At each node, we evaluate two choices for every possible mask configuration. If we skip the node, our score remains the same as the next node with the exact same mask. If we pick the node, we verify its modulo 5 value is not currently banned by the mask. If it is safe, we calculate the new key it locks, turn on that corresponding bit in our mask, and add 1 to our score. We store the maximum of these two choices.

C++ -:

    #include <bits/stdc++.h>
    using namespace std;
    int findMaxSpectralNodes(int n, const vector<int>& S) {
        if (n == 0) return 0;
        vector<vector<int>> dp(n + 1, vector<int>(32, 0));

        for (int i = n - 1; i >= 0; i--) {
            int node_num = i + 1;

            for (int mask = 0; mask < 32; mask++) {
                // Option 1: Skip the current node
                int ans = dp[i + 1][mask];

                // Option 2: Pick the current node (if it's not locked)
                int mod_val = S[i] % 5;
                
                if ((mask & (1 << mod_val)) == 0) {

                    // Calculate the new key this node will lock
                    int key = (S[i] + node_num) % 5;
                 
                    int new_mask = mask | (1 << key);
                    
                    ans = max(ans, 1 + dp[i + 1][new_mask]);
                }

                dp[i][mask] = ans;
            }
        }

        return dp[0][0];
    }

Time Complexity

• Time: O(N *2^5) = O(32N) - We evaluate 32 possible masks for each of the N nodes. Because 32 is a small constant, this simplifies to linear O(N) time.
• Space: O(N * 2^5) = O(32N) - We need a 2D matrix to store the states, which simplifies to O(N) auxiliary space.

Code Implementation (C++)