In this HackerEarth Challenging Track problem solution, Alice and Bob saw a challenging track that consists of N hurdles of variable heights Hi. Now, Bob challenges Alice to complete this track with a given amount of jump power P.

The rules for completing the challenge are as follows:

Each time Alice jumps a hurdle, the jump power P of Alice reduces by the height of the hurdle.

Every even minute all the remaining hurdles having even heights will decay and their heights reduce by 1 and every odd minute all the remaining hurdles having odd heights will decay and their heights reduce by 1.

Initially, time T = 0 minute. It takes 1 minute for Alice to reach to the next hurdle and the time taken to jump a hurdle can be considered to be negligible. Alice has to complete the challenge starting from the first hurdle to the last hurdle, left to right, sequentially.

If P < 0 at any moment, Alice cannot move further. Find out if Alice can complete the challenge?


HackerEarth Challenging Track problem solution


HackerEarth Challenging Track problem solution.

#include <bits/stdc++.h>

using namespace std;

const int N = 1E5 + 5;
long long a[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t --) {
        int n;
        long long p;
        cin >> n >> p;
        for(int i = 0; i < n; i ++) {
            cin >> a[i];
            if(i != 0 && !(a[i] & 1))
                a[i] --;
        }
        int cnt = 0;
        long long cost = a[0];
        for(int i = 1; i < n; i ++) {
            cost += max(0LL, a[i] - cnt);
            cnt ++;
        }
        if(p >= cost)
            cout << "Yes " << p - cost << '\n';
        else
            cout << "No\n";
    }
    return 0;
}


Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
LL h[100001];
int main()
    {
        ios_base::sync_with_stdio(0);
        int t;
        cin >> t;
        while(t--){
            LL n , p;
            cin >> n >> p;
            for(int i = 1; i <= n; i++){
                cin >> h[i];
                if(i < 2){
                    continue;
                }
                int total = 0;
                if(h[i] % 2 == 0){
                    total = total + i - 1;
                }
                else{
                    total = total + i - 2;
                }
                h[i] -= total;
                h[i] = max(0LL , h[i]);
            }
            bool flag = 1;
            for(int i = 1; i <= n; i++){
                p = p - h[i];
                if(p < 0){
                    flag = 0;
                    break;
                }
            }
            if(flag == 1){
                cout << "Yes " << p << endl;
            }
            else{
                cout << "No" << endl;
            }
        }
    }