Go Coding with Asparagos: Fair Play in Watermelon Football

#go #programming #humor #algorithms

Who becomes the referee in the Great Watermelon Football Final?

Hi! I'm Asparagos - an asparagus who codes in Go. Here you’ll find everyday problems that a typical veggie might struggle with — and my Go solutions to them. Today we are solving the problem of Watermelon Football 🍉.

Problem

Welcome to The Great Watermelon Football Final! The watermelons are ready, and the stakes are high. There’s just one task left: we must split the players into two teams.

The watermelons are standing in a row, each with a rating. We must remove exactly one watermelon (don’t worry, this one becomes the referee). The remaining watermelons are split into two teams by index in the remaining row:

Team Even: players at even indices

Team Odd: players at odd indices

The total rating of both teams must be equal.

How many choices of the referee (how many indices to remove) make the teams' total ratings equal?

Input 🍈

rating []int - the ratings of the watermelons, len(rating) > 2.

Output 🥭

An integer representing the number of ways to choose one watermelon to remove (the referee) so that the remaining players can be split by index into two teams with equal total rating.

Examples 🥝:

Example 1

Input: rating = [1, 3, 2, 1, 2, 2]

Output: 2

We can remove the 2nd watermelon (rating 3), remaining players are [1, 2, 1, 2, 2].
Team Even: 1 + 1 + 2 = 4, Team Odd: 2 + 2 = 4.

We can remove the 4th watermelon (rating 1), remaining players are [1, 3, 2, 2, 2].
Team Even: 1 + 2 + 2 = 5, Team Odd: 3 + 2 = 5.
Example 2

Input: rating = [5, 7, 3, 8, 1]

Output: 1

We can remove the 4th watermelon (rating 8), remaining players are [5, 7, 3, 1].
Team Even: 5 + 3 = 8, Team Odd: 7 + 1 = 8.
Example 3

Input: rating = [1, 2, 3, 4]

Output: 0

There are no ways to remove one watermelon and obtain equal team totals.

Solution 💡

First, we calculate the total sums at even and odd indices: evenSum and oddSum.
We iterate through the watermelons' ratings and consider removing the current one at index ind. To check whether this removal builds equal teams, we use even/odd prefix sums before ind and compare the new even/odd sums after the removal (remember: all indices to the right shift left by 1, so their parity changes):

a. After removing index ind, all elements to the right that were at even indices become odd. Their total is evenSum - prefixEvenSum. Adding the odd prefix on the left, we get newOddSum = prefixOddSum + (evenSum - prefixEvenSum). If the current index is even, we must subtract its value r from newOddSum (because it was counted on the even side before removal). Then update prefixEvenSum += r.

b. Symmetrically, elements to the right that were at odd indices become even, their sum is oddSum - prefixOddSum. Adding the even prefix on the left, we get newEvenSum = prefixEvenSum + (oddSum - prefixOddSum). If the current index is odd, subtract r from newEvenSum, then update prefixOddSum += r.

c. If newOddSum == newEvenSum, increment count.

func countWaysToMakeTeams(rating []int) int {
    oddSum := 0
    evenSum := 0
    for ind, r := range rating {
        if ind%2 == 0 {
            evenSum += r
        } else {
            oddSum += r
        }
    }
    var prefixOddSum, prefixEvenSum, count int
    for ind, r := range rating {
        newOddSum := prefixOddSum + (evenSum - prefixEvenSum)
        newEvenSum := prefixEvenSum + (oddSum - prefixOddSum)
        if ind%2 == 0 {
            newOddSum -= r
            prefixEvenSum += r
        } else {
            newEvenSum -= r
            prefixOddSum += r
        }
        if newOddSum == newEvenSum {
            count++
        }
    }
    return count
}