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.
