The Bear's Den

Enter at your own risk

31 January 2025 Challenge 306

Transposed Games

Task 1: Odd Sum

Submitted by: Mohammad Sajid Anwar

You are given an array of positive integers, @ints.

Write a script to return the sum of all possible odd-length subarrays of the given array. A subarray is a contiguous subsequence of the array.

Example 1

Input: @ints = (2, 5, 3, 6, 4)
Output: 77

Odd length sub-arrays:
(2) => 2
(5) => 5
(3) => 3
(6) => 6
(4) => 4
(2, 5, 3) => 10
(5, 3, 6) => 14
(3, 6, 4) => 13
(2, 5, 3, 6, 4) => 20

Sum => 2 + 5 + 3 + 6 + 4 + 10 + 14 + 13 + 20 => 77

Example 2

Input: @ints = (1, 3)
Output: 4

Solution

This is another case where turning the viewing angle may lead to a different approach.

Instead of enumerating all odd length sub-arrays and sum over these, we count the sub-arrays an element is contained in as its weight. The sum over all elements multiplied with their weight gives the requested sum, too.

The weights are independent from the actual array elements, as these are a function of the array length only.

Let us consider a list \((e_1,\ldots,e_n)\) of length \(n\). There are \(k = \lfloor \frac{n + 1}{2} \rfloor\) possible odd sub-array lengths \((l_1,\ldots,l_k) \text{ where } l_j = 2j - 1\).

If an element \(e_i\) is a member of two different sub-arrays of length \(l\), then \(e_i\) must be located at different positions in these sub-arrays. Therefore the number of appearances of an element \(e_i\) in a sub-array of length \(l_j\) is limited by these constraints:

Taking the minimum over these constraints for all \(i, j\) results in a matrix \(c_{ij}\) with the number of appearances of element \(e_i\) in sub-arrays of length \(l_j\). We find the weights \((w_1,\ldots,w_n)\) as

\[w_i = \sum_{j=1}^k c_{ij}\]

Finally we calculate the vector product of \(e\) and \(w\) as the requested sum:

\[s = \sum_{i=1}^n e_i w_i\] 
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
use experimental 'signatures';

sub weight ($n) {
    my $k = int +($n + 1) / 2;
    cat((1 + sequence $n)->(*$k),
        ($n - sequence $n)->(*$k),
        (1 + 2 * sequence $k)->(,*$n),
        ($n - 2 * sequence $k)->(,*$n)
    )->mv(2, 0)->minover->sumover;
 }

sub odd_sum {
    my $l = long [@_];
    inner($l, weight($l->dim(0)))->sclr;
}

The weights for several lengths \(n\) form a triangle similar to Pascal’s triangle. These look like:

[1]
[1 1]
[2 2 2]
[2 3 3 2]
[3 4 5 4 3]
[3 5 6 6 5 3]
[4 6 8 8 8 6 4]
[4 7 9 10 10 9 7 4]
[5 8 11 12 13 12 11 8 5]
[5 9 12 14 15 15 14 12 9 5]

See the full solution to task 1.

Task 2: Last Element

Submitted by: Mohammad Sajid Anwar

You are given a array of integers, @ints.

Write a script to play a game where you pick two biggest integers in the given array, say x and y. Then do the following:

a) if x == y then remove both from the given array
b) if x != y then remove x and replace y with (y - x)

At the end of the game, there is at most one element left.

Return the last element if found otherwise return 0.

Example 1

Input: @ints = (3, 8, 5, 2, 9, 2)
Output: 1

Step 1: pick 8 and 9 => (3, 5, 2, 1, 2)
Step 2: pick 3 and 5 => (2, 2, 1, 2)
Step 3: pick 2 and 1 => (1, 2, 2)
Step 4: pick 2 and 1 => (1, 2)
Step 5: pick 1 and 2 => (1)

Example 2

Input: @ints = (3, 2, 5)
Output: 0

Step 1: pick 3 and 5 => (2, 2)
Step 2: pick 2 and 2 => ()

Solution

Apparently, step 3 in example 1 does not conform to the game’s rules: Here we should pick 2 and 2 to arrive at the final (1). However, the result matches.

For efficiency we sort the integers and insert a non-zero difference using a binary insert.

Then the implementation is straightforward:

use strict;
use warnings;
use List::MoreUtils qw(nsort_by binsert);

sub last_element {
    my @list = nsort_by {$_} @_;
    while (@list > 1) {
        my ($m1, $m2) = splice @list, -2;
        my $diff = $m2 - $m1;
        next unless $diff;
        binsert {$_ <=> $diff} $diff, @list;
    }
    $list[0] // 0;
}

See the full solution to task 2.

If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.