It_Wasnt_Me's blog

ABC 204 E — Rush Hour 2 why ternary wont work
By It_Wasnt_Me, history, 4 years ago, In English

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

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

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

It is because the function is not strictly decreasing.

→ Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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]

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply