Re: [gcj] Please help me with the Small B. Getting wrong.
no problem I can help u anything
thanks !
On Tue, Apr 14, 2015 at 10:41 PM, Nate Bauernfeind
nate.bauernfe...@gmail.com 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(sCase #$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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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.
Re: [gcj] Please help me with the Small B. Getting wrong.
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(sCase #$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 google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
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.
Re: [gcj] Please help me with the Small B. Getting wrong.
My approach doesn't put the pancakes on a new plate, but rather increased the number of people eating off that plate. Then you never need to calculate how many pancakes to put where. Division and modulo was all I then needed to figure out how many minutes were needed to eat the pancakes originating from that plate. I implemented a binary search, answering, can we eat all pancakes in n minutes? Whenever a plate was too large, I'd add an eater and use a minute. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/e9c8e14a-732f-4b90-8005-95fbbfa50c16%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Please help me with the Small B. Getting wrong.
Are you sure binary search will work? I am very interested in the way you use it. Please give details/code. Parker On Mon, Apr 13, 2015 at 7:37 PM Nate Bauernfeind nate.bauernfe...@gmail.com wrote: My approach doesn't put the pancakes on a new plate, but rather increased the number of people eating off that plate. Then you never need to calculate how many pancakes to put where. Division and modulo was all I then needed to figure out how many minutes were needed to eat the pancakes originating from that plate. I implemented a binary search, answering, can we eat all pancakes in n minutes? Whenever a plate was too large, I'd add an eater and use a minute. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/e9c8e14a-732f-4b90-8005-95fbbfa50c16%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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAGDEU-KMmFivebe9oMPy7nTTH91tM-d%3DP6YEk4NYW2%3DDUQkBVg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Please help me with the Small B. Getting wrong.
1) If you have 9, 3, 3, 3, 3, (many 3s) Then you need two special minutes to divide 9 into three 3s, and 3 minutes to eat them all 2) If you have 9, 5, 5, 5, 5, (many 5s) Then you need one special minutes to divide 9 into 4 and 5, and 5 minutes to eat them all So the way you divide numbers depends on all numbers, not just the maximum number. On Sun, Apr 12, 2015 at 6:00 PM Luke Pebody l...@pebody.org wrote: 1) If you have 6 stacks of size 4, then you are best off just letting everyone eat 2) If you have a stack of size 9, the best thing to do is to have one special minute where you give 3 to some other hungry customer, and then another special minute where you do the same. On Sun, Apr 12, 2015 at 9:10 AM, utkarsh gupta guptautkarsh2...@gmail.com wrote: For small B, what I did was to first divide all the maximum sized pancakes to half giving the extra half to empty plates.Now it will be take special minutes equal to the frequency of maximum sized sized pancake.Check if the new maximum sized pancake + the special minutes added is less than your initial ans, update answer if it less. Now again divide the maximum into two add the special minutes required and check if the new maximum + special minutes is less the your previous ans . Keep doing it until you have divided each pancake such that every pancake is either = 3 ,because for pancake = 1,2,3 answer will be same. Any help is appreciated. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/327a0d00-dc6c-4062-900c-d84da294ee6b%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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-ObXjSZBj021L5LkFo3PMBOFso8zLSy7y57VNxLb_%3DWtw%40mail.gmail.com https://groups.google.com/d/msgid/google-code/CAECKw-ObXjSZBj021L5LkFo3PMBOFso8zLSy7y57VNxLb_%3DWtw%40mail.gmail.com?utm_medium=emailutm_source=footer . 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAGDEU-Kxiguv2YurTaZ%2Bpb8VPC_FOZxhAxjsfO7vtVROpRbucw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Please help me with the Small B. Getting wrong.
when you have dividing the max value for the second time, you also need to keep track of the first special minutes to add to the next big value.. On Sun, Apr 12, 2015 at 3:45 PM, Xiongqi ZHANG zhangxion...@gmail.com wrote: 1) If you have 9, 3, 3, 3, 3, (many 3s) Then you need two special minutes to divide 9 into three 3s, and 3 minutes to eat them all 2) If you have 9, 5, 5, 5, 5, (many 5s) Then you need one special minutes to divide 9 into 4 and 5, and 5 minutes to eat them all So the way you divide numbers depends on all numbers, not just the maximum number. On Sun, Apr 12, 2015 at 6:00 PM Luke Pebody l...@pebody.org wrote: 1) If you have 6 stacks of size 4, then you are best off just letting everyone eat 2) If you have a stack of size 9, the best thing to do is to have one special minute where you give 3 to some other hungry customer, and then another special minute where you do the same. On Sun, Apr 12, 2015 at 9:10 AM, utkarsh gupta guptautkarsh2...@gmail.com wrote: For small B, what I did was to first divide all the maximum sized pancakes to half giving the extra half to empty plates.Now it will be take special minutes equal to the frequency of maximum sized sized pancake.Check if the new maximum sized pancake + the special minutes added is less than your initial ans, update answer if it less. Now again divide the maximum into two add the special minutes required and check if the new maximum + special minutes is less the your previous ans . Keep doing it until you have divided each pancake such that every pancake is either = 3 ,because for pancake = 1,2,3 answer will be same. Any help is appreciated. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/327a0d00-dc6c-4062-900c-d84da294ee6b%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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-ObXjSZBj021L5LkFo3PMBOFso8zLSy7y57VNxLb_%3DWtw%40mail.gmail.com https://groups.google.com/d/msgid/google-code/CAECKw-ObXjSZBj021L5LkFo3PMBOFso8zLSy7y57VNxLb_%3DWtw%40mail.gmail.com?utm_medium=emailutm_source=footer . 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAGDEU-Kxiguv2YurTaZ%2Bpb8VPC_FOZxhAxjsfO7vtVROpRbucw%40mail.gmail.com https://groups.google.com/d/msgid/google-code/CAGDEU-Kxiguv2YurTaZ%2Bpb8VPC_FOZxhAxjsfO7vtVROpRbucw%40mail.gmail.com?utm_medium=emailutm_source=footer . 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CA%2Bho9JzEasNh0%3Dad7S-uu_CjMuV0gY5GfgBc8ydVAELvot%2BVyA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Please help me with the Small B. Getting wrong.
Try a single stack of 9 pancakes. Edward On 12 Apr 2015, at 09:10, utkarsh gupta guptautkarsh2...@gmail.com wrote: For small B, what I did was to first divide all the maximum sized pancakes to half giving the extra half to empty plates.Now it will be take special minutes equal to the frequency of maximum sized sized pancake.Check if the new maximum sized pancake + the special minutes added is less than your initial ans, update answer if it less. Now again divide the maximum into two add the special minutes required and check if the new maximum + special minutes is less the your previous ans . Keep doing it until you have divided each pancake such that every pancake is either = 3 ,because for pancake = 1,2,3 answer will be same. Any help is appreciated. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/327a0d00-dc6c-4062-900c-d84da294ee6b%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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/837E4793-FD3E-4ED3-BDC8-00A2AACBAA6D%40gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Please help me with the Small B. Getting wrong.
1) If you have 6 stacks of size 4, then you are best off just letting everyone eat 2) If you have a stack of size 9, the best thing to do is to have one special minute where you give 3 to some other hungry customer, and then another special minute where you do the same. On Sun, Apr 12, 2015 at 9:10 AM, utkarsh gupta guptautkarsh2...@gmail.com wrote: For small B, what I did was to first divide all the maximum sized pancakes to half giving the extra half to empty plates.Now it will be take special minutes equal to the frequency of maximum sized sized pancake.Check if the new maximum sized pancake + the special minutes added is less than your initial ans, update answer if it less. Now again divide the maximum into two add the special minutes required and check if the new maximum + special minutes is less the your previous ans . Keep doing it until you have divided each pancake such that every pancake is either = 3 ,because for pancake = 1,2,3 answer will be same. Any help is appreciated. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/327a0d00-dc6c-4062-900c-d84da294ee6b%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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-ObXjSZBj021L5LkFo3PMBOFso8zLSy7y57VNxLb_%3DWtw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Please help me with the Small B. Getting wrong.
For small B, what I did was to first divide all the maximum sized pancakes to half giving the extra half to empty plates.Now it will be take special minutes equal to the frequency of maximum sized sized pancake.Check if the new maximum sized pancake + the special minutes added is less than your initial ans, update answer if it less. Now again divide the maximum into two add the special minutes required and check if the new maximum + special minutes is less the your previous ans . Keep doing it until you have divided each pancake such that every pancake is either = 3 ,because for pancake = 1,2,3 answer will be same. Any help is appreciated. -- 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 google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/327a0d00-dc6c-4062-900c-d84da294ee6b%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
