[Community Puzzle] The Optimal Urinal Problem


#1

Hi,

I'm looking at this community puzzle 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...


#4

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

Edit: got the 100% at last