5 hours ago

ANIRUDH • 0

Kota

Problem: Rat and Cheese

Solution: Breadth-First Search (BFS)

This problem is a classic single-source shortest path problem on a grid. The solution hinges on correctly interpreting the problem statement: "the rat has a special ability that he can clone himself 4 times and go upward, right, down, left... in 1 second". This "cloning" describes a simultaneous, wave-like expansion from the rat's position, which is the core mechanic of a Breadth-First Search (BFS). The goal is to find the time it takes for this expansion to reach the  

furthest piece of cheese.

The logic is as follows:

1. Model the "Cloning" Ability: The problem states the rat "can clone himself 4 times and go upward, right, down, left... in 1 second". This is the key insight. It describes a simultaneous, wave-like expansion from the rat's current position. This process is perfectly modeled by a  

   Breadth-First Search (BFS), where each "level" of the search corresponds to one second of time passing.

2. Initialization: Before starting the search, the algorithm must scan the grid to find the rat's initial position (the single source for the BFS) and count the total_cheese. This count is needed to verify if all cheese blocks are eaten at the end. If there's no cheese, the time is 0.

3. BFS Setup: A queue is used to manage the traversal. The rat's starting position and an initial time of 0 are enqueued. A visited grid is also created to ensure the "clones" don't enter the same cell twice, preventing infinite loops.

4. Level-by-Level Traversal: The BFS proceeds in a loop. In each iteration, a position is dequeued, and its four neighbors are explored. This simulates the "clones" moving out one step. The time variable associated with each state in the queue tracks how many seconds have passed.

5. Eating Cheese and Tracking Time: When a "clone" moves to a new cell containing cheese, a cheese_eaten counter is incremented. The time taken to reach this cheese is time + 1. The algorithm must keep track of the max_time taken to reach any cheese block, as the final answer is the time required to eat the last, most distant one.

6. Final Check: After the BFS completes, the algorithm compares the cheese_eaten count with the total_cheese count. If they match, all cheese was reachable, and max_time is the answer. If not, some cheese was inaccessible, and -1 is returned.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

int solveRatAndCheese(int N, std::vector<std::vector<int>>& grid) {
    if (N == 0) return 0;

    std::queue<std::tuple<int, int, int>> q;
    std::vector<std::vector<bool>> visited(N, std::vector<bool>(N, false));

    int start_row = -1, start_col = -1;
    int total_cheese = 0;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (grid[i][j] == 2) {
                start_row = i;
                start_col = j;
            } else if (grid[i][j] == 1) {
                total_cheese++;
            }
        }
    }

    if (total_cheese == 0) return 0;

    q.push({start_row, start_col, 0});
    visited[start_row][start_col] = true;

    int cheese_eaten = 0;
    int max_time = 0;
    
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [r, c, time] = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < N && nc >= 0 && nc < N && !visited[nr][nc] && grid[nr][nc] != 0) {
                visited[nr][nc] = true;
                int new_time = time + 1;

                if (grid[nr][nc] == 1) {
                    cheese_eaten++;
                    max_time = std::max(max_time, new_time);
                }
                
                q.push({nr, nc, new_time});
            }
        }
    }

    return (cheese_eaten == total_cheese) ? max_time : -1;
}

Complexity Analysis:

• Time Complexity: O(N*N). In the worst-case scenario, the BFS algorithm will visit every cell in the N x N grid exactly once. For each cell, it performs a constant number of operations (checking four neighbors). Therefore, the time complexity is proportional to the number of cells in the grid.

• Space Complexity: O(N*N). The space complexity is determined by the storage required for the queue and the visited grid. In the worst case, the queue could hold a large fraction of the grid's cells, and the visited array stores a boolean for each cell. Both scale with the size of the grid.

5 hours ago

ANIRUDH • 0

Kota

Problem 1: Alpha Bitwise Operation

Solution: Iteration by Bit Position

This is the most efficient and standard solution for this problem. The core idea is to iterate through each bit position (from 0 to 30) and, for each position, count how many numbers in the array have that bit set. If this count is strictly greater than half the array's size, the corresponding bit is set in the final result. This approach is optimal because the number of bits is a small constant, while the array size can be large.

The logic is as follows:

1. Iterate by Bit Position: The algorithm loops through each bit position k, from 0 up to 30. This range is sufficient because the maximum value for an array element is 109, which is less than 230.

2. Count Set Bits: For each bit position k, a counter is initialized to zero. The algorithm then iterates through every number in the input array A.

3. Check k-th Bit: Inside the inner loop, it checks if the k-th bit of the current number is set. This is done efficiently using the bitwise expression (number >> k) & 1. If the bit is set, the counter is incremented.

4. Apply Threshold Rule: After scanning the entire array for bit k, the algorithm checks if the total count of set bits is greater than N/2. To avoid floating-point issues, this is implemented as count * 2 > N.

5. Construct Result: If the condition is met, the k-th bit is set in the final result variable. This is done using a bitwise OR operation with a mask: result |= (1LL << k). After checking all bit positions, the result variable holds the final answer.

#include <iostream>
#include <vector>
#include <numeric>

long long calculateAlphaBitwise(int N, const std::vector<int>& A) {
    long long final_result = 0;
    for (int k = 0; k < 31; ++k) {
        int count_set_bits = 0;
        for (int num : A) {
            if ((num >> k) & 1) {
                count_set_bits++;
            }
        }
        if (count_set_bits * 2 > N) {
            final_result |= (1LL << k);
        }
    }
    return final_result;
}

Complexity Analysis:

• Time Complexity: O(N * K). The algorithm has a nested loop structure. The outer loop runs a constant number of times K (approx. 31, for the number of bits), and the inner loop runs N times (the size of the array). Since K is a small constant, the overall time complexity is effectively linear, or O(N).

• Space Complexity: O(1). The algorithm uses only a few variables to store the result, counters, and loop indices. The amount of memory used does not scale with the size of the input array N.