<reponame>Oxyhydride/Intro-To-Competitive-Programming<filename>Course Files/02 - Problem Solving Paradigms/Solutions/02B/BricksGame.py<gh_stars>0
# FUNCTIONS
def solution(n, arr):
    """
    Let's start simple: considering the base cases.
    - When there is one brick left, we should obviously take the only brick left.
    - When there are two bricks left, we should take both bricks.
    - When there are three bricks left, we should take all three bricks.

    The intresting part starts when there are 4 bricks left.

    Suppose we are left with the bricks
        [1, 2, 3, 4]
    and it is our turn to make a move. What is our optimal play? Well, we can either take one brick, two bricks, or
    three bricks.
        - If we take 1 brick, opponent is left with [2, 3, 4] which he will obviously take all of them. We score 1.
        - If we take 2 bricks, opponent is left with [3, 4] which he will obviously take all of them. We score 
          1 + 2 = 3.
        - If we take 3 bricks, opponent is left with [4] which he will obviously take. We score 1 + 2 + 3 = 6.

    Let's analyse our thought process. What are we considering when we are making this argument?

    For starters, we are assuming that the opponent is making optimal play. But optimal play is also what WE are
    aiming for. Thus we can conclude that the opponent is using the SAME STRATEGY as we are.

    Now let's finally introduce some DP terminology. Define the DP array as follows:
        dp[-i] = (optimal score, number of bricks taken in this move)
    where `dp[-i]` represents that tuple in the case where there are `i` bricks left (hence the minus sign).

    Back to our problem. Suppose we start with $k$ bricks remaining and we take one brick. What will our opponent's
    move be? Or rather, what is the *state* that our opponent will be in? Well, if we take one brick, our opponent will
    be left with $k - 1$ bricks, so the state is `dp[-(k-1)] = dp[-k + 1]`. Now our opponent's move will be
    `dp[-k + 1][1]` (since the second value of the DP state is the number of bricks that we should take) and we'll be
    left with `(k-1) - dp[-k + 1][1]` bricks. The state that WE need to play is now `dp[-((k-1) - dp[-k + 1][1])]`
    which simplifies to `dp[-k + dp[-k + 1][1] + 1]`. The score we would attain in this case would thus be
        `dp[-k + dp[-k + 1][1] + 1][0] + arr[-k]`
    where `arr` contains the bricks' scores.

    Repeating the above argument for the other two types of moves (i.e. taking 2 bricks or taking 3 bricks) yields
    the score in all three cases:
        Taking 1 brick score:       dp[-k + dp[-k + 1][1] + 1][0] + arr[-k]
        Taking 2 bricks' score:     dp[-k + dp[-k + 2][1] + 2][0] + arr[-k] + arr[-k + 1]
        Taking 3 bricks' score:     dp[-k + dp[-k + 3][1] + 3][0] + arr[-k] + arr[-k + 1] + arr[-k + 2]
    The optimal score for the state when we have `k` bricks left is thus the MAXIMUM of these three scores. The number
    of bricks taken naturally follows.
    """

    # Create the table
    dp = [(0, 0) for _ in range(n + 1)]  # First element is the max score, second element is number of bricks to take
    
    # Set base cases
    dp[-1] = (arr[-1], 1)                      # When there is 1 brick left, it is optimal to just take that brick
    dp[-2] = (arr[-1] + arr[-2], 2)            # When there are 2 bricks left, it is optimal to just take both bricks
    dp[-3] = (arr[-1] + arr[-2] + arr[-3], 3)  # When there are 3 bricks left, it is optimal to just take the three bricks
    
    # Process the rest of the cases
    for bricks_left in range(4, n + 1):
        # Consider all possible moves that we can take and the maximum score in each case
        take1brick  = dp[-bricks_left + dp[-bricks_left + 1][1] + 1][0] + arr[-bricks_left]
        take2bricks = dp[-bricks_left + dp[-bricks_left + 2][1] + 2][0] + arr[-bricks_left] + arr[-(bricks_left - 1)]
        take3bricks = dp[-bricks_left + dp[-bricks_left + 3][1] + 3][0] + arr[-bricks_left] + arr[-(bricks_left - 1)] + \
                      arr[-(bricks_left - 2)]
        
        # Determine the best option
        options = [take1brick, take2bricks, take3bricks]
        best_option = max(options)
        
        # Update the DP table
        dp[-bricks_left] = (best_option, options.index(best_option) + 1)  # 2nd element is the number of bricks taken
    
    # Return the score for the initial case of having all the bricks
    return dp[-n][0]

# INPUT
t = int(input())

for _ in range(t):
    n = int(input())
    A = [int(x) for x in input().split()]

    # PROCESSES
    # Solve the problem using the function
    answer = solution(n, A)

    # OUTPUT
    print(answer)

Files/02 - Problem Solving Paradigms/Solutions/02B/BricksGame.py<gh_stars>0
# FUNCTIONS
def solution(n, arr):
    """
    Let's start simple: considering the base cases.
    - When there is one brick left, we should obviously take the only brick left.
    - When there are two bricks left, we should take both bricks.
    - When there are three bricks left, we should take all three bricks.

    The intresting part starts when there are 4 bricks left.

    Suppose we are left with the bricks
        [1, 2, 3, 4]
    and it is our turn to make a move. What is our optimal play? Well, we can either take one brick, two bricks, or
    three bricks.
        - If we take 1 brick, opponent is left with [2, 3, 4] which he will obviously take all of them. We score 1.
        - If we take 2 bricks, opponent is left with [3, 4] which he will obviously take all of them. We score 
          1 + 2 = 3.
        - If we take 3 bricks, opponent is left with [4] which he will obviously take. We score 1 + 2 + 3 = 6.

    Let's analyse our thought process. What are we considering when we are making this argument?

    For starters, we are assuming that the opponent is making optimal play. But optimal play is also what WE are
    aiming for. Thus we can conclude that the opponent is using the SAME STRATEGY as we are.

    Now let's finally introduce some DP terminology. Define the DP array as follows:
        dp[-i] = (optimal score, number of bricks taken in this move)
    where `dp[-i]` represents that tuple in the case where there are `i` bricks left (hence the minus sign).

    Back to our problem. Suppose we start with $k$ bricks remaining and we take one brick. What will our opponent's
    move be? Or rather, what is the *state* that our opponent will be in? Well, if we take one brick, our opponent will
    be left with $k - 1$ bricks, so the state is `dp[-(k-1)] = dp[-k + 1]`. Now our opponent's move will be
    `dp[-k + 1][1]` (since the second value of the DP state is the number of bricks that we should take) and we'll be
    left with `(k-1) - dp[-k + 1][1]` bricks. The state that WE need to play is now `dp[-((k-1) - dp[-k + 1][1])]`
    which simplifies to `dp[-k + dp[-k + 1][1] + 1]`. The score we would attain in this case would thus be
        `dp[-k + dp[-k + 1][1] + 1][0] + arr[-k]`
    where `arr` contains the bricks' scores.

    Repeating the above argument for the other two types of moves (i.e. taking 2 bricks or taking 3 bricks) yields
    the score in all three cases:
        Taking 1 brick score:       dp[-k + dp[-k + 1][1] + 1][0] + arr[-k]
        Taking 2 bricks' score:     dp[-k + dp[-k + 2][1] + 2][0] + arr[-k] + arr[-k + 1]
        Taking 3 bricks' score:     dp[-k + dp[-k + 3][1] + 3][0] + arr[-k] + arr[-k + 1] + arr[-k + 2]
    The optimal score for the state when we have `k` bricks left is thus the MAXIMUM of these three scores. The number
    of bricks taken naturally follows.
    """

    # Create the table
    dp = [(0, 0) for _ in range(n + 1)]  # First element is the max score, second element is number of bricks to take
    
    # Set base cases
    dp[-1] = (arr[-1], 1)                      # When there is 1 brick left, it is optimal to just take that brick
    dp[-2] = (arr[-1] + arr[-2], 2)            # When there are 2 bricks left, it is optimal to just take both bricks
    dp[-3] = (arr[-1] + arr[-2] + arr[-3], 3)  # When there are 3 bricks left, it is optimal to just take the three bricks
    
    # Process the rest of the cases
    for bricks_left in range(4, n + 1):
        # Consider all possible moves that we can take and the maximum score in each case
        take1brick  = dp[-bricks_left + dp[-bricks_left + 1][1] + 1][0] + arr[-bricks_left]
        take2bricks = dp[-bricks_left + dp[-bricks_left + 2][1] + 2][0] + arr[-bricks_left] + arr[-(bricks_left - 1)]
        take3bricks = dp[-bricks_left + dp[-bricks_left + 3][1] + 3][0] + arr[-bricks_left] + arr[-(bricks_left - 1)] + \
                      arr[-(bricks_left - 2)]
        
        # Determine the best option
        options = [take1brick, take2bricks, take3bricks]
        best_option = max(options)
        
        # Update the DP table
        dp[-bricks_left] = (best_option, options.index(best_option) + 1)  # 2nd element is the number of bricks taken
    
    # Return the score for the initial case of having all the bricks
    return dp[-n][0]

# INPUT
t = int(input())

for _ in range(t):
    n = int(input())
    A = [int(x) for x in input().split()]

    # PROCESSES
    # Solve the problem using the function
    answer = solution(n, A)

    # OUTPUT
    print(answer)
# FUNCTIONS Let's start simple: considering the base cases.     - When there is one brick left, we should obviously take the only brick left.     - When there are two bricks left, we should take both bricks.     - When there are three bricks left, we should take all three bricks.      The intresting part starts when there are 4 bricks left.      Suppose we are left with the bricks         [1, 2, 3, 4]     and it is our turn to make a move. What is our optimal play? Well, we can either take one brick, two bricks, or     three bricks.         - If we take 1 brick, opponent is left with [2, 3, 4] which he will obviously take all of them. We score 1.         - If we take 2 bricks, opponent is left with [3, 4] which he will obviously take all of them. We score            1 + 2 = 3.         - If we take 3 bricks, opponent is left with [4] which he will obviously take. We score 1 + 2 + 3 = 6.      Let's analyse our thought process. What are we considering when we are making this argument?      For starters, we are assuming that the opponent is making optimal play. But optimal play is also what WE are     aiming for. Thus we can conclude that the opponent is using the SAME STRATEGY as we are.      Now let's finally introduce some DP terminology. Define the DP array as follows:         dp[-i] = (optimal score, number of bricks taken in this move)     where `dp[-i]` represents that tuple in the case where there are `i` bricks left (hence the minus sign).      Back to our problem. Suppose we start with $k$ bricks remaining and we take one brick. What will our opponent's     move be? Or rather, what is the *state* that our opponent will be in? Well, if we take one brick, our opponent will     be left with $k - 1$ bricks, so the state is `dp[-(k-1)] = dp[-k + 1]`. Now our opponent's move will be     `dp[-k + 1][1]` (since the second value of the DP state is the number of bricks that we should take) and we'll be     left with `(k-1) - dp[-k + 1][1]` bricks. The state that WE need to play is now `dp[-((k-1) - dp[-k + 1][1])]`     which simplifies to `dp[-k + dp[-k + 1][1] + 1]`. The score we would attain in this case would thus be         `dp[-k + dp[-k + 1][1] + 1][0] + arr[-k]`     where `arr` contains the bricks' scores.      Repeating the above argument for the other two types of moves (i.e. taking 2 bricks or taking 3 bricks) yields     the score in all three cases:         Taking 1 brick score:       dp[-k + dp[-k + 1][1] + 1][0] + arr[-k]         Taking 2 bricks' score:     dp[-k + dp[-k + 2][1] + 2][0] + arr[-k] + arr[-k + 1]         Taking 3 bricks' score:     dp[-k + dp[-k + 3][1] + 3][0] + arr[-k] + arr[-k + 1] + arr[-k + 2]     The optimal score for the state when we have `k` bricks left is thus the MAXIMUM of these three scores. The number     of bricks taken naturally follows. # Create the table # First element is the max score, second element is number of bricks to take # Set base cases # When there is 1 brick left, it is optimal to just take that brick # When there are 2 bricks left, it is optimal to just take both bricks # When there are 3 bricks left, it is optimal to just take the three bricks # Process the rest of the cases # Consider all possible moves that we can take and the maximum score in each case # Determine the best option # Update the DP table # 2nd element is the number of bricks taken # Return the score for the initial case of having all the bricks # INPUT # PROCESSES # Solve the problem using the function # OUTPUT