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;
}
}
}