You are given an array of positive numbers. You can can convert any element (i) to any value in range [i/2, i-1] or [i+1, 2*i] in one step. Mind minimum steps needed to make the all elements equal.

1 <= n <= 1e5

Each element in range [1,1e5]

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 173 |

2 | awoo | 168 |

3 | nor | 164 |

4 | SecondThread | 163 |

5 | BledDest | 162 |

5 | Um_nik | 162 |

7 | maroonrk | 161 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

You are given an array of positive numbers. You can can convert any element (i) to any value in range [i/2, i-1] or [i+1, 2*i] in one step. Mind minimum steps needed to make the all elements equal.

1 <= n <= 1e5

Each element in range [1,1e5]

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2023 01:50:28 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I think I found a solution.

First off, let's try to fix the element we will convert all elements into and minimize the step count across all elements. Can we calculate the minimum steps in $$$O(\log n)$$$? Turns out we can.

Let $$$x$$$ be the final element. First, we need a frequency array. Now we will use this to find all elements in a certain interval. It is clear we can find the number of elements in the interval $$$[x,2x]$$$ in $$$O(1)$$$ by turning the frequency array into a prefix sum array. We can do the same for $$$[x,\frac {x}{2}]$$$. For both of these we add $$$1$$$ to the total step count. For the interval $$$[2x,4x]$$$ though the step count will be 2, same goes for $$$[\frac {x}{2},\frac {x}{4}]$$$. The amount of such segments will clearly be $$$O(\log n)$$$.

Since there's only $$$10^5$$$ possible final elements, the total time complexity will be $$$O(n \log n)$$$

I'm sorry if I got this wrong

Let target element be 10

so according to you any element in range

[10,20] will take 1 move(s) [20,40] will take 2 move(s) [40,80] will take 3 move(s)

So let's take the element 50 which is to be converted to 10 : Then 50 -> 25 -> 12 -> 10 (3 moves)

Yeah, this approach seems right. You can also think about it as having only log(n) checkpoints that matter. So instead of 50->25->12-10, you can do 50->40->20->10 since the checkpoints are powers of 2 times your target (10), and there are log(n) ranges that matter.

Thank you!