I tried to solve this problem in the contest but unfortunately I was getting WA on 6 tests
I thought that I had implementation bugs, after I read the tutorial I found that "Note that you cannot directly apply ternary search when searching for the optimal solution. Can you figure out why?"
Anyone know why ternary wont work here ? I guess that the function will always be something decreasing then increasing or always increasing, Am I right ?
It is because the function is not strictly decreasing.
Because unlike binary search, ternary search doesn't work when its function has equal values(aka it should always be strictly increasing or strictly decreasing). You can read this blog and its comments. It is explaining a bit more "why".
I found the intended math solution but one of my friends has done ternary, I haven't understand it yet, but you can look at it: [https://atcoder.jp/contests/ABC204/submissions/23251808]
I think so ternary works till l = sqrt(n)-1, r = sqrt(n)+1 and then he checked which is smallest, sorry for my bad English.