Блог пользователя It_Wasnt_Me

Автор It_Wasnt_Me, история, 3 года назад, По-английски

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 ?

my submission

  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

It is because the function is not strictly decreasing.

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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".

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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]

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.