I'm really sad I didn't have time to play. I am curious if someone who did could shatter my naivety -- this seems more like a statistics problem than a programming problem, isn't it about identifying a markov model for each scenario?
What about this (aside from verification) couldn't be worked out with pencil/paper/excel?
To put another way, isn't this effectively an online (as in, must commit to choice made and don't know what next piece will be, not as in on the internet) 1D bin packing variant?
Nice to see another participant's thinking process for the puzzles! I ended up getting 5th place using dynamic programming for all of the scenarios, but I'm under the impression that almost everybody in the top 20 had almost equally good strategies and most of the variance in scores was due to luck with the sequence of people they got.
A quick sanity check is in Scenario 2, you needed 300 creative people each with a ~6.2% chance of showing up. The odds of getting a sequence of people where that's even possible for the first place score (2906 rejections + 1000 accepts = 3906 total people) is on the order of 1 in 10000, and that's without even factoring in the other constraints.
I peaked at around 21st but stopped playing because it seemed to be a lottery.
I ran simulations with perfect information and found the lower bound for scores. Scenario 2 was mean 3743 rejections with 265 std deviation. This is the curve formed from simulated data and a strategy that had with perfect information, i.e. you could build the best possible strategy after knowing the random assignments.
So winners had scores that I could not even theoretically achieve unless I could see 1000s of scenarios.
So I ran my code locally and was happy that my code was always just a few rejections off of optimal and called that a private success.
That's what I thought when I saw the challenge originally... maybe a better way of running it would have been to have each run be with a deterministic seed, and apply to all candidates.
That way people can test offline with random sequences, but the leaderboard runs have the same seed for everyone. Maybe I'm missing something obvious, but I think this would have lessened the impact of luck.
The tricky thing is the code for making decisions runs locally on the contestants machine, so the first time they submit they can record the sequence locally and compute the best set of actions for the next time they submit. Even if the sequence is somehow tied to a user's account so they can't resubmit against the same sequence, they could do the same thing with an alt account and feed the sequence to a main account.
Sites like Kaggle usually get around this problem by running contestant code in a containerized environment server side, but even then you can get clever with tricks to leak info.
The trick for Scenarios 2 and 3 is that most of the constraints don't end up being bottlenecks. For example in Scenario 2, well-connected pretty much always gets satisfied while doing the other constraints, so the DP table only needs 4 dimensions (space, Berlin local, techno lover, creative).
My other trick was to only build the full DP table for the latter half of the game (i.e. when all the constraints are at least 50% satisfied) which across 4 dimensions reduces the size by a factor of 16. For the beginning half of the game I combined Berlin and techno into a single parameter, which technically isn't perfect but doesn’t matter too much in the early game. I wrote up my approach here if you want more details: https://chriskw.xyz/2025/09/16/Berghain/
Re: optimizing for best case vs expected case, I thought about that but in simulations my strategy mostly performed the same as a "perfect knowledge" strategy where you could see all of the people in line ahead of time and retroactively accept people. When it under performed it was usually because some miraculous string of people showed up near the end, but betting on that happening seemed like it would do more harm than good, i.e. it would throw away more best case scenarios than it would salvage.
Great write-up. Love how everyone is sharing their solutions. Fun fact, this is an actual business problem we have to solve at our company (Listen Labs).
We have an AI customer interviewing platform our customers ask us things like:
“I want to talk to 200 people, at least 100 who are ChatGPT Pro users, 75 who use Gemini weekly, and 50 from each region of the US.”
We don’t know those attributes upfront, so we have to ask participants screening questions and decide in real time whether to move forward.
Of course, it's a bit different as we optimize for the average case, not the best case, and we don't know the distributions (but can estimate with LLMs!).
> For Scenario 1 (just two traits), he solved it exactly using dynamic programming.
I wonder if this exact solve tried setting "more rejections than X" as failure, so that you can get better best case for the cost of dropped worst cases
Wait until they find out that guest list on Berghain does not guarantee entry !
What is the probability of a person with both the attributes "looks like they belong to berghain" and "can solve an obscure live optimisation challenge" ?
> What is the probability of a person with both the attributes "looks like they belong to berghain" and "can solve an obscure live optimisation challenge" ?
As someone who goes there often, I can say it's surprisingly high
>What is the probability of a person with both the attributes "looks like they belong to berghain" and "can solve an obscure live optimisation challenge" ?
As a person who has been there, you'd be surprised. Strict door policy is sort of a soft intelligence test, and the music there is so insanely good that it attracts highly creative, highly open folks.
I'm really sad I didn't have time to play. I am curious if someone who did could shatter my naivety -- this seems more like a statistics problem than a programming problem, isn't it about identifying a markov model for each scenario?
What about this (aside from verification) couldn't be worked out with pencil/paper/excel?
To put another way, isn't this effectively an online (as in, must commit to choice made and don't know what next piece will be, not as in on the internet) 1D bin packing variant?
Nice to see another participant's thinking process for the puzzles! I ended up getting 5th place using dynamic programming for all of the scenarios, but I'm under the impression that almost everybody in the top 20 had almost equally good strategies and most of the variance in scores was due to luck with the sequence of people they got.
A quick sanity check is in Scenario 2, you needed 300 creative people each with a ~6.2% chance of showing up. The odds of getting a sequence of people where that's even possible for the first place score (2906 rejections + 1000 accepts = 3906 total people) is on the order of 1 in 10000, and that's without even factoring in the other constraints.
I peaked at around 21st but stopped playing because it seemed to be a lottery.
I ran simulations with perfect information and found the lower bound for scores. Scenario 2 was mean 3743 rejections with 265 std deviation. This is the curve formed from simulated data and a strategy that had with perfect information, i.e. you could build the best possible strategy after knowing the random assignments.
So winners had scores that I could not even theoretically achieve unless I could see 1000s of scenarios.
So I ran my code locally and was happy that my code was always just a few rejections off of optimal and called that a private success.
That's what I thought when I saw the challenge originally... maybe a better way of running it would have been to have each run be with a deterministic seed, and apply to all candidates.
That way people can test offline with random sequences, but the leaderboard runs have the same seed for everyone. Maybe I'm missing something obvious, but I think this would have lessened the impact of luck.
The tricky thing is the code for making decisions runs locally on the contestants machine, so the first time they submit they can record the sequence locally and compute the best set of actions for the next time they submit. Even if the sequence is somehow tied to a user's account so they can't resubmit against the same sequence, they could do the same thing with an alt account and feed the sequence to a main account.
Sites like Kaggle usually get around this problem by running contestant code in a containerized environment server side, but even then you can get clever with tricks to leak info.
How did you use DP for scenario 2 and 3? The table seems to be way to big unless you do some optimizations.
Also did you optimize for the best case in any way vs expected cases?
The trick for Scenarios 2 and 3 is that most of the constraints don't end up being bottlenecks. For example in Scenario 2, well-connected pretty much always gets satisfied while doing the other constraints, so the DP table only needs 4 dimensions (space, Berlin local, techno lover, creative).
My other trick was to only build the full DP table for the latter half of the game (i.e. when all the constraints are at least 50% satisfied) which across 4 dimensions reduces the size by a factor of 16. For the beginning half of the game I combined Berlin and techno into a single parameter, which technically isn't perfect but doesn’t matter too much in the early game. I wrote up my approach here if you want more details: https://chriskw.xyz/2025/09/16/Berghain/
Re: optimizing for best case vs expected case, I thought about that but in simulations my strategy mostly performed the same as a "perfect knowledge" strategy where you could see all of the people in line ahead of time and retroactively accept people. When it under performed it was usually because some miraculous string of people showed up near the end, but betting on that happening seemed like it would do more harm than good, i.e. it would throw away more best case scenarios than it would salvage.
Great write-up. Love how everyone is sharing their solutions. Fun fact, this is an actual business problem we have to solve at our company (Listen Labs).
We have an AI customer interviewing platform our customers ask us things like: “I want to talk to 200 people, at least 100 who are ChatGPT Pro users, 75 who use Gemini weekly, and 50 from each region of the US.”
We don’t know those attributes upfront, so we have to ask participants screening questions and decide in real time whether to move forward.
Of course, it's a bit different as we optimize for the average case, not the best case, and we don't know the distributions (but can estimate with LLMs!).
> For Scenario 1 (just two traits), he solved it exactly using dynamic programming.
I wonder if this exact solve tried setting "more rejections than X" as failure, so that you can get better best case for the cost of dropped worst cases
Wait until they find out that guest list on Berghain does not guarantee entry !
What is the probability of a person with both the attributes "looks like they belong to berghain" and "can solve an obscure live optimisation challenge" ?
> What is the probability of a person with both the attributes "looks like they belong to berghain" and "can solve an obscure live optimisation challenge" ?
As someone who goes there often, I can say it's surprisingly high
Surprisingly high is not high, or we're meeting different kinds of people in there ;)
How do you know someone goes to Berghain? Don’t worry, they’ll tell you
>What is the probability of a person with both the attributes "looks like they belong to berghain" and "can solve an obscure live optimisation challenge" ?
As a person who has been there, you'd be surprised. Strict door policy is sort of a soft intelligence test, and the music there is so insanely good that it attracts highly creative, highly open folks.
What are you implying about people that go to Berghain?
They don't look like they can solve some obscure optimisation challenge.