# Bricks Game

# Bricks Game

+ 4 comments im still a noob.

i shall come back to this one day.

+ 3 comments Hi all, I would like to give you my feedback about the exercice and the difficulties I have experimented for those who are really stuck. Unfortunatelly I didn't success to implement a solution so I checked on the Editorial.

First of all it was not obvious that having two players is "fake". In fact only the first player have the "power" to optimize the maximum solution (because he plays first) and the second one shall deal with the remaining problem (it is because the first player takes X bricks than the second player will take the Y next bricks). The biggest difficulty is to see the second player as a subplayer of yourself which wants to do the same as you (as a "clone") ie get the maximum score. A proof? Finaly you can play alone this game. Easier no?

Then how to build the right algorithm? I will not give you the solution but some tips to keep in mind. I am a beginner with DP and the main issue I meet is to formalize the problem a mathematically way. You have to find the "magic" formula which is computed for i_th -1 and keep true at i_th (cf https://en.wikipedia.org/wiki/Recurrence_relation). More specifically when the first player wants to pick the i_th brick what does it mean for the previous solution? What should keep true at i_th? Remember: previous solutions are optimal and you have to indistinguishably consider the two players.

I hope this is helpful. Good luck!

+ 3 comments O(N) Solution: Reverse the original array Make an array sum which stores sum until ith element Make a 1D dp array. For each game the maximum sum a player can get is Sum[i] - (the sum other player can get in the remaining bricks) i.e. maximum of (sum[i] - dp[i-1] (selecting only one brick), sum[i]- dp[i-2] (2 bricks), sum[i] - dp[i-3] (3 bricks)) Take care of base cases

+ 0 comments For java people : if your solution doesn't work for test cases 10-12, use long instead of int.

+ 2 comments This might help anyone stuck!

If we're at state i, aka the ith brick is at the top, we can write this as a function

**DP(i)**, that will return the max value that we can obtain for i, assuming it's our go.At brick i, you have 3 different choices, you can either: Take one brick, take two bricks, or take three bricks. Each of these leads us to a new state (sub problem):

DP(i) -> DP(i-1) //if we take one DP(i) -> DP(i-2) //if we take two DP(i) -> DP(i-3) //if we take three

So ideally we want to simply take the MAX of these possible moves. We want to make optimal decisions, so we'll just simply take the MAX of the three choices because the one that returns the highest value is going to be the choice we want!

DP(i) = MAX{ DP(i-1), DP(i-2), DP(i-3)}

A problem with this is that these next states, aren't out turns! After we've made our move it's the oppositions turn! We're trying to maximise our score, and in effect we're also trying to minimize their score!

So we're trying to maximize our score, while simultanously minimizing their score.

Let say we removed the first block: aka the next state was DP(i-1), we want to minimize this state and this would look like this:

DP(i-1) = MIN{ DP(i-2), DP(i-3), DP(i-4)}

Here we're evaluation every single move the opponent can make, and we're saying, take the minimum, we want the opponents score to be minimized!

We can then simply combine these to form this large recurrence relation:

DP(i) = MAX{ //we take 1 brick - next state for the oppo is DP(i-1) MIN{ DP(i-2), //they take 1 DP(i-3), //they take 2 blocks DP(i-4) //they take 3 blocks } , //we take 2 bricks - next state for the oppo is DP(i-2) MIN{ DP(i-3), //they take 1 DP(i-4), //they take 2 blocks DP(i-5) //they take 3 blocks } , //we take 3 bricks - next state for the oppo is DP(i-3) MIN{ DP(i-3), //they take 1 DP(i-4), //they take 2 blocks DP(i-5) //they take 3 blocks } }

Sort 97 Discussions, By:

Please Login in order to post a comment