1 day ago

Suryansh Rishit • 0

Mysuru

Problem Editorial: Minimum Cost to Reach the Destination
Logic and Approach:

We treat the problem as a Dynamic Programming problem with:

• States defined by the current city (index).

• Transitions defined by allowed jumps: i → i+1 and i → i+3.

• The cost is the sum of differences in ticket costs at each step.

💡 Recursive DP with Memoization:

1. Base Case:
   If we're at the last city (i == n-1), the cost to reach the destination is 0.

2. Memoization:
   If the answer from city i is already computed (dp[i] != -1), return that to avoid recomputation.

3. Recursive Transitions:

   • Try jumping to i+1 and add the transition cost.

   • Try jumping to i+3 if within bounds.

   • Take the minimum of both paths.

Code:

#include<bits/stdc++.h>

using  namespace std;



int solve(int i,vector<int> &arr,vector<int> &dp){

    if (i == arr.size()-1 ){
        return 0;
    }
    if(dp[i] != -1) return dp[i];
    int ans = INT_MAX;

    if (i+1 < arr.size()){
        ans = min(ans,abs(arr[i+1]-arr[i]) + solve(i+1,arr,dp));
    }
    if (i+3 < arr.size()){
        ans = min(ans,abs(arr[i+3]-arr[i]) + solve(i+3,arr,dp));
    }
    return dp[i]=ans;
}

int main(){


    int n;
    cin >> n;

    vector<int> arr(n);
    for(int i = 0 ; i < n;i++){
        cin >> arr[i] ;
    }
    vector<int> dp(n+1,-1);
    cout << solve(0,arr,dp) << endl;

}

Time and Space Complexity:

• Time Complexity:
  O(N), because each state (city index) is computed only once.

• Space Complexity:
  O(N), for the dp array and recursion stack.

1 day ago

Suryansh Rishit • 0

Mysuru

Problem Editorial: Mean, Median and Mode

Approach:

1. Mean: Just accumulate the sum and divide by n.

2. Median: Sort the array.

   • If odd, take middle element.

   • If even, average of two center elements.

3. Mode: Use a map<int, int> to count frequencies. Track:

   • Max frequency.

   • Smallest number with max frequency.

Code:

#include <bits/stdc++.h>
using namespace std;

vector<double> findMeanMedianMode(int n, vector<int> &arr) {
    double sum = 0.0;
    map<int, int> freq;

    for (int i = 0; i < n; i++) {
        sum += arr[i];
        freq[arr[i]]++;
    }

    double mean = sum / n;

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

    double median;
    if (n % 2 == 1) {
        median = arr[n / 2];
    } else {
        median = (arr[n / 2] + arr[n / 2 - 1]) / 2.0;
    }

    int mode = arr[0];
    int maxFreq = 0;

    for (auto &p : freq) {
        if (p.second > maxFreq || (p.second == maxFreq && p.first < mode)) {
            maxFreq = p.second;
            mode = p.first;
        }
    }

    return {mean, median, static_cast<double>(mode)};
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    vector<double> res = findMeanMedianMode(n, arr);

    cout << fixed << setprecision(6);
    cout << res[0] << ", " << res[1] << ", " << (int)res[2] << endl;

    return 0;
}

Time Complexity:

• The sorting step takes O(n log n) time.

• Calculating the sum and building the frequency map takes O(n) time.

• Scanning the map to find the mode also takes O(n) time.

Since O(n log n) dominates, the overall time complexity is:

O(n log n)

Space Complexity:

• You use extra space for:

  • The input array → O(n)

  • The frequency map → O(n) (in the worst case, when all elements are unique)

So, the total space complexity is:

O(n)