0
$\begingroup$

I came about this problem looking for interesting DP problems. I tried with no luck to find which could be the overlapping sub-problems to explore and solve and tabulate. But it is my belief there are none and this problem can't be solved using DP.

Explanation of the problem rules can be seen here:

A turskish Roulette is a type of roulette which consists of:

  • S amount of slots, each one with a number between -64 and 64.
  • B amount of balls, each one with a number between -64 and 64 too.
  • 3 <= S <= 250 & 1 <= B <= 1/S
  • Each ball takes 2 slots of the roulette when they settle.
  • For each ball, let L be the sum of the 2 slots value numbers times it's number.
  • If the number L is negative the player loses that amount, else he wins that amount.
  • The balls will always settle in the order they were introduced into the roulette, ej. If I throw the balls 1, 2 & 3 then the ball 2 will always be between 1 and 3.
  • The objective is to find the max profit the owner of the roulette can have(max amount a player can lose in 1 turn) given a specific roulette with S number of slots and B number of balls each of them with their respective values.

I tried implementing a solution but the apparent lack of overlapping sub-problems made it impossible.

Things I already tried is the tabulation of the max_profit for a ball given a certain amount of slots. But I'm still short of the answer.

So, are there overlapping problems that can be helpful with memoization or tabulation?

$\endgroup$
  • $\begingroup$ Hint: You can "cut" the circle at some arbitrary position between two slots, and use a "normal" DP (try to figure this out yourself) to calculate the maximum for all solutions in which no ball touches both of these slots. Then you can "cut" the circle at a different position, and calculate the corresponding maximum. How can these solutions be combined? $\endgroup$ – j_random_hacker Nov 19 '17 at 12:12
  • $\begingroup$ @j_random_hacker Can you clarify a bit? or provide a short example of the tip? For example I hace the slots 0 1 2 3 4. In theory the 4 is connected to 0 next. So what do you mean by some arbitrary position between two slots, I mean, ANY slots? $\endgroup$ – RmaxTwice Nov 19 '17 at 12:55
  • $\begingroup$ Yes, I mean you can freely choose any such "cut point", and then the problem (when restricted to cases where a ball does not cross the cut point) becomes "linear", and behaves much like many other DPs (like the DP for Knapsack, etc.). $\endgroup$ – j_random_hacker Nov 19 '17 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.