1 day ago

Suryansh Rishit • 0

Mysuru

Problem-1

The logic :

1. Input the total number of items n and then read n strings.

2. Since only the last appearance of any item matters (because re-opening pushes it to the top), iterate the input array in reverse.

3. Use a set<string> to keep track of already-included items.

4. If an item hasn't been inserted yet, add it to the result vector and mark it in the set.

5. Finally, print the ans vector which stores the final order of items, from top to bottom.

#include<bits/stdc++.h>

using namespace std;



int main(){

    int n;
    cin >> n;
    vector<string> arr(n);
    cin.ignore();
    for(int i = 0;i<n;i++){
        getline(cin, arr[i],'\n');
    }
    vector<string> ans;
    set<string> s;

    for(int i = n-1;i>=0;i--){
        if (!s.count(arr[i])){
            ans.push_back(arr[i]);
            s.insert(arr[i]);
        }
    }

    for(int i = 0 ; i < ans.size();i++){
        cout << ans[i] << endl;
    }
    return 0;


}

Time & Space Complexity

• Time Complexity:

  • O(n) — iterating through the list once in reverse.

  • O(log k) per set operation, where k is number of unique strings, but effectively O(1) average due to small input limits.

• Space Complexity:

  • O(k) — for storing unique items in a set and final output in ans.

1 day ago

Suryansh Rishit • 0

Mysuru

Problem - 2

Approach

The key insight is to efficiently count elements smaller than each array element in two ranges:

1. Left range: For each index i, count elements in [0, i-1] that are smaller than arr[i]
2. Right range: For each index i, count elements in [i+1, n-1] that are smaller than arr[i]

Algorithm Steps:

1. Process left to right: Use a multiset to maintain elements seen so far. For each position i:
   • Count elements in multiset that are smaller than arr[i] using lower_bound()
   • Store this count in left[i]
   • Insert arr[i] into multiset
2. Process right to left: Clear multiset and repeat the process in reverse:
   • For each position i from n-1 to 0, count smaller elements in multiset
   • Store this count in right[i]
   • Insert arr[i] into multiset
3. Count k-Spikes: For each index i, check if both left[i] ≥ k and right[i] ≥ k

#include<bits/stdc++.h>

using namespace std;


int main(){

    int n;
    cin >> n;
    vector<int> arr(n);

    for(int i = 0 ; i < n;i++){
        cin >> arr[i];
    }
    multiset<int> s;
    int k;
    cin >> k;
    vector<int> left(n,0),right(n,0);
 
    for (int i = 0; i < n; ++i) {
        left[i] = distance(s.begin(), s.lower_bound(arr[i]));
        s.insert(arr[i]);
    }

    s.clear();  
 
    for (int i = n - 1; i >= 0; --i) {
        right[i] = distance(s.begin(), s.lower_bound(arr[i]));
        s.insert(arr[i]);
    }
 
    int cnt = 0;
    for (int i = k; i < n-k; ++i) {
        cout << arr[i] << endl;
        cout << left[i] << "  " << right[i] << endl;
        if (left[i] >= k && right[i] >= k)
            cnt++;
    }
    cout << cnt << endl;

}
 

Time Complexity (TC):

O(n log n) - Two passes through array with multiset insert and lower_bound operations

Space Complexity (SC):

O(n) - For multiset, left array, right array, and input storage