Hi Stefan, Thanks for the detailed comments. The analysis in our site is doing a worst-case type analysis, and it's usually better to just round up to simplify the reasoning than to keep every bound tight. You are right to point out that the part with x+1 was misleading as it didn't seem like an upper bound, so I've edited that. Notice that in the analysis it does say "at most two" or some variation of that when bounding the number of values in a stage. I rather keep the analysis simple than tight, as it's probably the best advice for the contest as well to not overdo it with tightness when you don't have to. Given that even the less accurate estimate gives a complexity that will make the implementation run instantly, there would be no reason to try to refine that further.
That being said, I think it's totally legit for you to post this thoughts here or in any other place that you like, as more insight into the problem is almost always a good way to train our brains. The above applies only to our policy regarding what to put and what to leave out from our official analysis. Best, Pablo On Sun, Apr 9, 2017 at 12:35 AM, Stefan Pochmann <[email protected]> wrote: > I think there are a few mistakes in the "Bathroom Stalls" analysis: > > "since stage i processes two consecutive values, they are either 2x and > 2x+1 or 2x and 2x-1, for some x (that is, one even and one odd number)." > > Not necessarily two consecutive values, they can also be *the same* value. > > "Thus, the spawned values for stage i+1 are either x and x+1 or x and x-1, > respectively." > > How could they spawn x+1? I think it's like this: > > - 2x-1 spawns only x-1. > - 2x spawns x-1 and x. > - 2x+1 spawns only x. > > So in either of the mentioned two cases (2x and 2x+1 or 2x and 2x-1) only > x-1 and x can be spawned. And if a stage only contains one value, then also > at most two consecutive values are spawned. > > If x+1 *could* be spawned as well, that might even be a problem. Then a > stage of two values could spawn a stage of *three* values (x-1, x and x+1), > violating the analysis's own assertion that each stage only has at most two > consecutive values. And maybe the three could spawn four or more, which > could spawn even more, etc? I didn't look into it because as shown above, > it's really at most two. > > "the population of S is at most 4 at any given time" > > While that's correct, I don't think it's tight. I think S has at most *3* > values at any given time. Because the solution removes X before it inserts > X0 and X1. > > Cheers! > Stefan > > On Sunday, April 9, 2017 at 6:34:40 AM UTC+2, Bartholomew Furrow wrote: > > I don't think they've announced it, but the Code Jam team has uploaded > analyses for the Qualification Round problems. > > > > > > I strongly recommend reading the analyses for this round, especially if > you had trouble with any of the problems. They're written in extremely > clear language (thanks to Pablo, Ian, Joseph and Steve), give great > intuition for the solutions and how to come up with them, and have > occasional tidbits of general advice for contestants. > > > > > > Bartholomew > > -- > 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/e16c4a4d-12f1-46eb-91ab-967bef0f0203%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/CANa5jcArsDb9qRePoAGNxCDBK852e5ZheC6kJMx8ykt3ACDvFg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
