3 days ago

admin 1.6k

Hyderabad

Q3. Charged Particles Solution

Initial Distance Calculation

To calculate the initial distance between the particles:

1. Start with a base distance of N-1 (since there are N-1 gaps between N particles).
2. For each pair of adjacent particles:
   • If they have the same charge, the separation is 2 units.
   • If they have opposite charges, the separation is 1 unit.

For example, for the string 0110, the separations are 1, 2, 1, giving a total distance of 4.

Adjusting the Distance After Flipping

When we flip a charge, only the distances between the flipped charge and its adjacent charges can change. The rest of the string remains unaffected.

To efficiently adjust the distance:

1. Check the charge before the one we're flipping (if it exists).

   • If they were different before the flip, the separation increases by 1.
   • If they were the same, the separation decreases by 1.

2. Check the charge after the one we're flipping (if it exists) and adjust the distance in the same manner.

3. Flip the charge.

4. Print the new distance.

Time Complexity

The time complexity of this approach is O(N+K). We calculate the initial distance in O(N) time. For each of the K operations (flips), we adjust the distance in O(1) time.

C++ Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int calculate_initial_distance(const string& S) {
    int distance = 0;
    for (int i = 0; i < S.size() - 1; i++) {
        if (S[i] == S[i+1]) {
            distance += 2;
        } else {
            distance += 1;
        }
    }
    return distance;
}


int main() {
    int N, K;
    cin >> N >> K;

    string S;
    cin >> S;

    vector<int> Q(K);
    for (int i = 0; i < K; i++) {
        cin >> Q[i];
    }

    int distance = calculate_initial_distance(S);
    //cout << distance << " ";

    for (int qi : Q) {
        int index = qi - 1;

        // Check the previous charge if it exists
        if (index > 0) {
            if (S[index] != S[index - 1]) distance++;
            else distance--;
        }

        // Check the next charge if it exists
        if (index < N - 1) {
            if (S[index] != S[index + 1]) distance++;
            else distance--;
        }

        // Flip the charge
        S[index] = (S[index] == '0') ? '1' : '0';

        cout << distance << " ";
    }

    return 0;
}

3 days ago

admin 1.6k

Hyderabad

Q3. Collecting Coins

Two approaches to solve the problem, both areO(N log N) because we need to sort the arrays. First one is straightforward binary search. Second is slightly more elegant and optimal solution for this problem using prefix sum, notice and learn how nicely array of heroes has been sorted while keeping track of original order of heroes in order to correctly output answer in second approach.

Approach 1: Binary Search

Algorithm

1. Sort the monsters based on their power and calculate the prefix sum of their coins.
2. For each hero, find the position of the first monster whose power is greater than the hero's power using binary search.
3. The total coins collected by the hero will be the prefix sum at the position found in step 2.
4. Print the total coins collected by each hero.

C++ Code

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

using namespace std;

int find_position(const vector<pair<int, int>>& monsters, int x) {
    int l = 0, r = monsters.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (monsters[mid].first <= x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<pair<int, int>> monsters(M);
    for (int i = 0; i < M; i++) {
        cin >> monsters[i].first;
    }
    for (int i = 0; i < M; i++) {
        cin >> monsters[i].second;
    }

    sort(monsters.begin(), monsters.end());

    vector<long long> prefix_sum(M);
    prefix_sum[0] = monsters[0].second;
    for (int i = 1; i < M; i++) {
        prefix_sum[i] = prefix_sum[i-1] + monsters[i].second;
    }

    for (int i = 0; i < N; i++) {
        int pos = find_position(monsters, A[i]);
        if (pos == 0) {
            cout << 0 << " ";
        } else {
            cout << prefix_sum[pos-1] << " ";
        }
    }

    return 0;
}

Approach 2: Sorting and Single Pass

Algorithm

1. Sort the monsters based on their power and calculate the prefix sum of their coins.
2. Sort the heroes based on their power but remember their original positions.
3. Iterate through the sorted heroes. For each hero, find the position of the first monster whose power is greater than the hero's power by iterating from the last found position.
4. Store the total coins collected by the hero in the result array at the hero's original position.
5. Print the result array.

C++ Code

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

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<pair<int, int>> heroes(N);
    for (int i = 0; i < N; i++) {
        cin >> heroes[i].first;
        heroes[i].second = i;  // Store the original position
    }

    vector<pair<int, int>> monsters(M);
    for (int i = 0; i < M; i++) {
        cin >> monsters[i].first;
    }
    for (int i = 0; i < M; i++) {
        cin >> monsters[i].second;
    }

    sort(monsters.begin(), monsters.end());

    vector<long long> prefix_sum(M);
    prefix_sum[0] = monsters[0].second;
    for (int i = 1; i < M; i++) {
        prefix_sum[i] = prefix_sum[i-1] + monsters[i].second;
    }

    sort(heroes.begin(), heroes.end());

    vector<long long> result(N);
    int last_pos = 0;
    for (int i = 0; i < N; i++) {
        while (last_pos < M && monsters[last_pos].first <= heroes[i].first) {
            last_pos++;
        }
        if (last_pos == 0) {
            result[heroes[i].second] = 0;
        } else {
            result[heroes[i].second] = prefix_sum[last_pos-1];
        }
    }

    for (int i = 0; i < N; i++) {
        cout << result[i] << " ";
    }

    return 0;
}

13 months ago

Amit • 50

Mumbai

Question 2: Collecting Coins

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

using namespace std;

void collectCoins(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& coins_collected) {
    for (int i = 0; i < A.size(); ++i) {
        for (int j = 0; j < B.size(); ++j) {
            if (A[i] >= B[j]) {
                coins_collected[i] += C[j];
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> A(n), B(m), C(m);

    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    for (int i = 0; i < m; ++i) {
        cin >> B[i];
    }

    for (int i = 0; i < m; ++i) {
        cin >> C[i];
    }

    vector<int> coins_collected(n, 0);
    collectCoins(A, B, C, coins_collected);

    for (int i = 0; i < n; ++i) {
        cout << coins_collected[i] << " ";
    }

    return 0;

}

13 months ago

Amit • 50

Mumbai

Question 1: Candle Stack

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

using namespace std;

int minimumCandlesToBuy(vector<int>& candle, int K) {
    sort(candle.begin(), candle.end());
    int count = 0;
    int current_candle = 1;

    for (int i = 0; i < candle.size(); ++i) {
        if (candle[i] == current_candle) {
            ++current_candle;
            ++count;
            if (current_candle > K) {
                break;
            }
        }
    }
    return count;
}

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> candle(N);

    for (int i = 0; i < N; ++i) {
        cin >> candle[i];
    }
    int result = minimumCandlesToBuy(candle, K);
    cout << result << endl;
    return 0;
}