Comments
On vaaven → Codeforces Round 1031 (Div. 2), 16 months ago
+9

shouldn't have participated

On cry → Codeforces Round 965 (Div. 2), 2 years ago
+3

Majority of submissions have this code, most likely copied off youtube or telegram. 275628589
+2

274425542

Say that again :clown:
0

just submitted your code and got a TLE

274432933

this is not a contest but rather a clown fest

+4

Let's assume there were no time constraints. The simplest approach would be to traverse the entire array a such that for every a[i] < a[i-1], we keep squaring a[i] until a[i] >= a[i-1].

However, given the constraints, this would result in a TLE error. Instead, we keep a reference with respect to the previous element. I think it would be easier to explain with an example.

Let's consider a = [128, 4, 2].

Since 4 < 128, we initiate our count at 0 and keep squaring 4 until it becomes greater than or equal to 128:

  1. ( 4 * 4 = 16 )
  2. ( 16 * 16 = 256 )

Since 256 > 128, we update our count to 2, as it took us 2 steps.

If we continue with our naive approach, the array would be a = [128, 256, 2]. Next, we need to keep squaring 2 until it becomes greater than or equal to 256:

  1. ( 2 * 2 = 4 )
  2. ( 4 * 4 = 16 )
  3. ( 16 * 16 = 256 )

So it took us (2 + 3 = 5) steps in total.

Now, if we use a different approach, we don't update 4 to 256 in our main array and just keep track of the count. Hence, after the first operation, a = [128, 4, 2].

We know it took us 2 steps to make 4 greater than or equal to 128, so we compare 2 with its previous element (4). It takes just 1 step to make 2 greater than or equal to 4, as ( 2 * 2 = 4 ). Finally, with reference to the previous element, we can say it takes us (2) (steps to convert 4 to 256) + (1) (step to convert 2 to 4) + (2) (steps to convert 4 to 256) = 5 steps.

Similarly, if the array a was [128, 4, 16], we compare 4 with 16 and realize it takes 1 step (4 * 4 = 16) for 4 to become greater than or equal to 16. Therefore, to convert 16 to the previous element of 4, it would take us (2) (steps to convert 4 to 256) + (2 — 1) (steps to convert 16 to the previous element of 4, as 4 requires at least 1 step to be greater than or equal to 16).

My submission for reference
-17

https://codeforces.me/contest/1883/problem/E

Problem C is on codeforces too lol