koustav_7890's blog

CF DIV 3 Help
By koustav_7890, history, 4 years ago, In English

Can someone explain why the condition in Question C the condition is Root(n) in the tutorials? link to problem: https://mirror.codeforces.com/contest/1426/problem/C

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After x operations of type-1 and y operations of type-2, the sum of resulting array will be (x + 1)*(y + 1).
We have to minimise (x + y), such that (x + 1)*(y + 1) >= n. Note that for any number N, two numbers A, B such that A*B = N, you will get minimum (A + B) for such A which is closest to square root of N. If you try to plot a graph, it will be a parabola with minima at square root of n, hence you can either use ternary search or check few values near sqrt(n).

→ Reply