MasterMind's blog

Help with atcoder problem D (Cake 123)
By MasterMind, history, 5 years ago, In English

Hi there,

I need help in understanding the editorial of this Problem

The Editorial written in Japanese mentioned 4 methods to solve the problem which I translated using google translator and I managed to understand the first two methods. The last method mention Binary search, I am interested in a the binary search solution.

Anyone can shed some light on this would be really helpful.

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MasterMind (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let $$$x$$$ be the deliciousness of the $$$k^{th}$$$ way. We want to binary search for $$$x$$$.

Validation takes $$$O(XYlog(Z))$$$ time. Maybe it could be done better, but I haven't thought too much about it. Once you have $$$x$$$, then finding the answer is straightforward. Is this what you were looking for?

→ Reply