[Community Puzzle] The Optimal Urinal Problem


I’m looking at this community puzzle (https://www.codingame.com/training/medium/the-optimal-urinal-problem) and I’m sure it cannot be done with brute force, so I’m trying to find out what pseudo-algorithm I should use and I’m failing to see how will I find out whats the initial position. Any hint?


dynamic programming

As mentioned, Dynamic programming (or more specifically - memoization) is the way here. Brute force will likely solve the first test cases, but will fall short when n goes above 1000. It’s a good start to get the basic understanding of the problem and have a working solution.

I have found this puzzle very very interesting, as the dynamic programming can also be considered an interim solution, with complexity is o(n). It will solve all test cases, BUT …

After some further analysis, I believe there is an O(1) solution here. Have a look at the pattern that is created when computing the max number of people in a given "Section"of urinals, assuming you have people standing in both ends of the segment. (in other words, after implementing the memoization, have a look at the pattern of the numbers that are stored).

A most interesting pattern…


So do you suggest a top-down or a bottom-up approach ?

Edit: got the 100% at last

Could someone help me?

I dont get my “Bug”:

My solution works for all testcases in the IDE, but when I put in my solution I get 87% because Toilet World (Not Universe!) fails. And well the code is as far as I can see correct and the bigger of the two actually succeeds and also since there is no info about timeout/plain wrong result I cannot debug this.

I wrote you a private message.

Thanks got it!

Hi there ! I am proud to say that there is a direct solution. I broke down the pattern of the numbers, and can calculate directly any solution (position / number of guys) with any number of urinals.
Took a bit of time, but it’s possible. :smiley: