[Community Puzzle] The Optimal Urinal Problem

Puzzles
#1

Hi,

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?

Thanks

#2

dynamic programming

#3

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…

2 Likes
#4

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

Edit: got the 100% at last

#5

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.

#6

I wrote you a private message.

#7

Thanks got it!

#8

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: