I am trying to solve this problem. PROBLEM LINK
But I can't figure out why I am getting WA in test 2. I cannot exactly find out the exact test case on which my code fails because its the 485th TC and CF isn't showing it.
My logic is this:
My logic:
We want to make the current element to be greater than or equal to prev element To do this, let's say we raise the curr element to some power. Mathematically,
=> curr * 2^pow >= prev = 2^pow >= prev/curr
Take log base 2 on both sides.
pow >= log2(prev) — log2(curr);
this means, pow = ceil(log2(prev) — log2(curr))
My code:
void solve(){
int n;cin>>n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin>>a[i];
int ans = 0;
int prevpow = 0;
for(int i = 1; i < n; i++){
int curr = a[i];
int prev = pow(2, prevpow) * a[i-1];
if(curr >= prev){
prevpow = 0;
continue;
}
// y < x
prevpow = ceil(log2(prev) - log2(curr));
ans += prevpow;
}
cout<<ans<<endl;
}
[submission:272673906]