HackerEarth Minimum cost problem solution YASH PAL, 31 July 2024 In this HackerEarth Minimum cost problem solution, You are standing at position 1. From position i, you can walk to i+1 or i-1 with cost 1. From position i, you can travel to without any cost to pi (p is a permutation of numbers 1…n). You have to reach position n. Determine the minimum possible cost. HackerEarth Minimum cost problem solution. #include <bits/stdc++.h>using namespace std;const int maxn = 1e5 + 17;int n, d[maxn], p[maxn];bool mark[maxn];int main(){ ios::sync_with_stdio(0), cin.tie(0); int t; cin >> t; while(t--){ cin >> n; for(int i = 0; i < n; i++) cin >> p[i], p[i]--; fill(d + 1, d + n, n); memset(mark, 0, sizeof mark); queue<int> q({0}); while(q.size()){ int i = q.front(); q.pop(); if(mark[i]) continue; mark[i] = 1; vector<int> self({i}); while(p[self.back()] != i){ self.push_back(p[self.back()]); d[self.back()] = d[i]; mark[self.back()] = 1; } auto add = [&](int j){ if(d[j] <= d[i] + 1) return ; d[j] = d[i] + 1; q.push(j); }; for(auto i : self){ if(i) add(i - 1); if(i < n - 1) add(i + 1); } } cout << d[n - 1] << 'n'; }} Second solution #include <bits/stdc++.h>using namespace std;const int maxn = 1e5 + 17;int n, d[maxn], p[maxn];bool mark[maxn];int main(){ ios::sync_with_stdio(0), cin.tie(0); int t; cin >> t; while(t--){ cin >> n; for(int i = 0; i < n; i++) cin >> p[i], p[i]--; fill(d + 1, d + n, n); memset(mark, 0, sizeof mark); queue<int> q({0}); while(q.size()){ int i = q.front(); q.pop(); if(mark[i]) continue; mark[i] = 1; vector<int> self({i}); while(p[self.back()] != i){ self.push_back(p[self.back()]); d[self.back()] = d[i]; mark[self.back()] = 1; } auto add = [&](int j){ if(d[j] <= d[i] + 1) return ; d[j] = d[i] + 1; q.push(j); }; for(auto i : self){ if(i) add(i - 1); if(i < n - 1) add(i + 1); } } cout << d[n - 1] << 'n'; }} coding problems