no problem I can help u anything thanks !
On Tue, Apr 14, 2015 at 10:41 PM, Nate Bauernfeind < [email protected]> wrote: > Yes I'm quite sure that binary search works; I got large and small > correct. I just read the analysis and I'm surprised to see this is not the > intended solution. =) My code is scala and, though terse, should be pretty > clear. I've made minor improvements over my submitted solution (user > NefariousZhen). > > To do the binary search you only need to ask the question: Can all > pancakes be eaten in 'm' minutes? > > case class Plate(pancakes: Int, eaters: Int) extends Ordered[Plate] { > def minutes = (pancakes + eaters - 1) / eaters > override def compare(that: Plate): Int = minutes.compareTo(that.minutes) > } > > Note that Plate.minutes is basically rounded up integer division. If the > pancakes don't equally divide then we need an additional minute to finish > the plate. > > Now to actually answer the proposed question: > @tailrec > def eatable(ps: PriorityQueue[Plate], min: Int): Boolean = { > if (ps.head.minutes <= min) { > true > } else if (min > 0) { > val p = ps.dequeue() > ps += p.copy(eaters = p.eaters + 1) > eatable(ps, min - 1) > } else { > false > } > } > > At each step: > 1) If the worst plate will be finished in the time remaining then we're > done! > 2) We're not done, do we have time to add a diner to this plate? If so > replace the plate with a new plate that has one more diner. (Note: After > reading the analysis, I now realize I could be more clever here, but for > the sake of simplicity I'm going to just add one diner at a time.) > 3) If we're out of time, we can't eat that fast, back out. > > One thing to note, using this approach if we can eat all pancakes in 't' > minutes, it will also be true for 't + 1'. This allows us to binary search > to find the best 't'. > > The analysis teases at the end that the best solution (they provide) is > O(D*sqrt(M) + M). But this is way better. > > The outer binary search is lg(M) * ( > D lg (D) + // Create Priority Queue > M * ( // eatable may recurse no more than M times > lg(D) + // remove a plate > lg(D) // add back that plate > ) > ) > > Yielding: O(lg(M) *(D lg(D) + M * (lg(D) + lg(D)))) a.k.a. O(D lg(D) lg(M) > + M lg(D) lg(M)) > > For completeness sake (if you want to do this in Scala yourself) here's a > main: > def main(args: Array[String]): Unit = { > val in = io.Source.stdin.getLines() > val T = in.next().toInt > for (cs <- 1 to T) { > val d = in.next().toInt > val ds = in.next().split(" ").map(p => Plate(p.toInt, 1)) > var min = 0 > var max = ds.map(_.pancakes).max > while (max - min > 0) { > val mid = (min + max) / 2 > if (eatable(PriorityQueue(ds: _*), mid)) { > max = mid > } else { > min = mid + 1 > } > } > println(s"Case #$cs: $min") > } > } > > Not too bad, eh? > > Nate > > On Monday, April 13, 2015 at 10:30:44 AM UTC-4, Xiongqi ZHANG wrote: > > Are you sure binary search will work? > > > > I am very interested in the way you use it. Please give details/code. > > > > > > Parker > > > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/2718ceb0-62aa-435b-adff-702a44104826%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CABTXE5FKrJb%3DeF_8ShB8iF%2BR-nRHDt-isMkbohq0szFX7E02Mg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
