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 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/e16c4a4d-12f1-46eb-91ab-967bef0f0203%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
