I am writing this blog to get the consults form the higher ranked programmers in this platform. In the last contest (div4) I have solved 3 questions correctly, but my rating decreased. why ????

I participated in Good Bye 2025 and solved only Problem A.

I spent most of my time on Problem C ("First or Second"). I tried many approaches:

1. Recursive solution — simulated removing first or second child.
2. Added memoization with str(arr) as key.
3. Got MLE ("Need a bigger sleigh") on test 3.

Recursion solution :

def maximum_earn(arr):
    if len(arr) == 1:
        return 0
    op1 = arr[0] + maximum_earn(arr[1:])           # remove first
    op2 = -arr[1] + maximum_earn([arr[0]] + arr[2:])  # remove second
    return max(op1, op2)

Recursion + memoization :

memo = {}

def maximum_earn(arr):
    if len(arr) == 1:
        return 0
    key = str(arr)
    if key in memo:
        return memo[key]
    op1 = arr[0] + maximum_earn(arr[1:])
    op2 = -arr[1] + maximum_earn([arr[0]] + arr[2:])
    memo[key] = max(op1, op2)
    return memo[key]

I then tried a greedy idea: choose which child remains, and compute the best $$$X$$$.

My first greedy formula:

If child $$$i$$$ remains, $$$X = \text{sum}(a[0:i]) - \text{sum}(a[i+1:])$$$

It worked on small cases but failed on [7, -6, -1, -8, -8] (got 24, expected 29).

I realized:
- For elements before the survivor, I can sometimes choose signs (e.g., subtract a negative to add value).
- So I changed the left part to sum(abs(x) for x in arr[:i]).

This is my final code (O(n²) — works on samples but TLE on large inputs):

import sys

def maximum_earn(arr):
    n = len(arr)
    maxx = float('-inf')
    
    for i in range(n):
        # Left part: you can choose signs → use absolute values
        left_sum = sum(abs(x) for x in arr[:i])
        # Right part: you must subtract → contribution = -sum(arr[i+1:])
        right_sum = sum(arr[i+1:])
        current = left_sum - right_sum
        if current > maxx:
            maxx = current

    return maxx

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    print(maximum_earn(a))

It gives 29 for the last sample, but TLE on large inputs due to O(n²).