site.base_url }}/">The Bear's Den -->

The Bear's Den

Enter at your own risk

Even More Special Levels

Task 2: Equalize Array

Submitted by: Mohammad Sajid Anwar

You are give an array of integers, @ints and two integers, $x and $y.

Write a script to execute one of the two options:

Level 1:
Pick an index i of the given array and do $ints[i] += 1

Level 2:
Pick two different indices i,j and do $ints[i] +=1 and $ints[j] += 1.

You are allowed to perform as many levels as you want to make every elements in the given array equal. There is cost attach for each level, for Level 1, the cost is $x and $y for Level 2.

In the end return the minimum cost to get the work done.

Example 1

Input: @ints = (4, 1), $x = 3 and $y = 2
Output: 9

Level 1: i=1, so $ints[1] += 1.
@ints = (4, 2)

Level 1: i=1, so $ints[1] += 1.
@ints = (4, 3)

Level 1: i=1, so $ints[1] += 1.
@ints = (4, 4)

We performed operation Level 1, 3 times.
So the total cost would be 3 x $x => 3 x 3 => 9

Example 2

Input: @ints = (2, 3, 3, 3, 5), $x = 2 and $y = 1
Output: 6

Level 2: i=0, j=1, so $ints[0] += 1 and $ints[1] += 1
@ints = (3, 4, 3, 3, 5)

Level 2: i=0, j=2, so $ints[0] += 1 and $ints[2] += 1
@ints = (4, 4, 4, 3, 5)

Level 2: i=0, j=3, so $ints[0] += 1 and $ints[3] += 1
@ints = (5, 4, 4, 4, 5)

Level 2: i=1, j=2, so $ints[1] += 1 and $ints[2] += 1
@ints = (5, 5, 5, 4, 5)

Level 1: i=3, so $ints[3] += 1
@ints = (5, 5, 5, 5, 5)

We performed operation Level 1, 1 time and Level 2, 4 times.
So the total cost would be (1 x $x) + (3 x $y) => (1 x 2) + (4 x 1) => 6

Solution

Update from previous post:

I knew this task was tricky. As pointed out by Luis in his blog, taking the maximum number as the target is not always optimal.

There is a very special set of conditions:

In that case, we must not use ‘level 1’ to increment the single non-maximal element but instead increment the smallest element by two and all other elements by one using ‘level 2’.

The solution becomes a bit more complex now:

use strict;
use warnings;
use PDL v2.077;
use PDL::NiceSlice;

sub equalize_array ($x, $y, @ints) {
    my $ints = pdl @ints;
    return 0 if $ints->dim(0) < 2;
    my $target = maximum $ints;
    my $force2 = $ints->dim(0) > 2 && $ints->dim(0) % 2 &&
        ($ints->dim(0) + 1) * $y / 2 < $x;
    my $steps = $ints->dim(0) * $target - sum($ints);
    return $x * ($ints->dim(0) * $target - sum($ints)) if $y >= 2 * $x;

    my $cost = 0;
    while () {
        my $min = $ints->index(minimum_n_ind($ints, 2));
        if ($min((1)) == $target) {
            if ($min((0)) != $target && $force2) {
                $target++;
                redo;
            }
            return $cost + $x * ($target - $min((0)));
        }
        $min += 1;
        $cost += $y;
    }
}

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.