So there's this question 1995C - Квадратирование
It basically asks to count how many times we need to square elements at different indexes .. such that the whole array becomes non decreasing..
I've reduced it down to a math formula that goes like this
k[i] = k[i-1] + (ceil(log2(log2(a[i-1])) - log2(log2(a[i])))
here k[i] is the number of times i need to square at index i..
i reached here by writing an inequality in terms of a[i] powered (2^k[i]).. and same for a[i-1] and then took log2 of both sides. below is my code that implements this solution..
heres the main block of code from my solution:
int cnt = 0;
int prev = 0;
for(int i=2;i<=n;i++) {
if(arr[i]==1 && arr[i-1]>1) {
cout<<-1<<"\n";
return;
}
if(arr[i-1]==1) continue;
long double a = log2(arr[i-1]);
long double b = log2(arr[i]);
int ax2 = prev + ((int)ceil(log2(a) - log2(b)));
ax2 = max(0ll, ax2);
cnt += ax2;
prev = ax2;
}
cout<<cnt<<"\n";
I however am getting a WA on some test case when i submit this solution... Is there some flaw in my logic? I'm pretty sure I understood the question correctly.. Perhaps there's some cases I am not considering? I know that the computer is not accurate when it comes to floating point precisions.. Is that the problem? I'd appreciate any help.. Thank you in advance.
check for 1 2 1 3, correct answer is -1 and your code outputs 0. Create a check that if there is a 1 after a number>1 then return -1.
I do have such a check.. the first if block inside the loop checks exactly that.. I dont think that's the problem.
Yes, it was a precision issue I had used the same logic my code. I changed long double to double and int to long long in your code and it worked. edited code.
long double is not accurate in arithmetic calculations u can test it by calculating powers of 2 in long double.
oh hey you're right.. double IS more accurate than long double.. that's a nice little nuance i didn't kmow before.. thanks a lot man.