Fair Rations · Coding Gym

See the original problem on HackerRank.

You are the benevolent ruler of Rankhacker Castle, and today you’re distributing bread. Your subjects are in a line, and some of them already have some loaves. Times are hard and your castle’s food stocks are dwindling, so you must distribute as few loaves as possible according to the following rules:

Every time you give a loaf of bread to some person , you must also give a loaf of bread to the person immediately in front of or behind them in the line (i.e., persons \(i+1\) or \(i-1 \)).
After all the bread is distributed, each person must have an even number of loaves.

Given the number of loaves already held by each citizen, find and print the minimum number of loaves you must distribute to satisfy the two rules above. If this is not possible, print NO.

For example, the people in line have loaves \(B=[4,5,6,7]\). We can first give a loaf to \(i=3\) and \(i=4\) so \(B=[4,5,7,8]\). Next we give a loaf to \(i=2\) and \(i=3\) and have \(B=[4,6,8,8]\) which satisfies our conditions. We had to distribute \(4\) loaves.

Input Format

The first line contains an integer \(N\), the number of subjects in the bread line.

The second line contains \(N\) space-separated integers \(B[i]\).

Constraints

\(2 \leq N \leq 1000\)
\(1 \leq B[i] \leq 10\), where \(1 \leq i \leq N\)

Output Format

Print a single integer that denotes the minimum number of loaves that must be distributed so that every person has an even number of loaves. If it’s not possible to do this, print NO.

Solutions

First of all, we can observe that the parity of the sum of all the loaves will never change because we always distribute 2 loaves at a time. This means that if the initial sum of the array is odd, we can never satisfy the rule consisting in having each person with an even number of loaves. This is just an observation that will be useful later. We do not need to check if the sum is odd in advance.

The strategy to solve the algorithm could be to simply iterate the array and add one loaf to any person holding an odd number of loaves and to the following one. Visually:

At the end of the scan, if the last person holds an even number of loaves then the algorithm has distributed the minimum amount of loaves and at the same time all the people have an even number of loaves. On the other hand, if the last person has an odd number of loaves then it means the problem could not be solved and the answer is “NO”.

This is a possible encoding of such an idea in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


constexpr bool isodd(int i) { return i%2 == 1; }

int main()
{
    int n; cin >> n;
    vector<int> v(n);
    copy_n(istream_iterator<int>(cin), n, begin(v));

    auto cnt = 0;
    for (auto i=0; i<n-1; ++i)
    {
        if (isodd(v[i]))
        {
            v[i]++; // useless, just for clarity
            v[i+1]++;
            cnt+=2;
        }
    }
    cout << (isodd(v.back()) ? "NO" : to_string(cnt));
}

The dual (iterating right to left) of the algorithm works exactly the same way:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


constexpr bool isodd(int i) { return i%2 == 1; }

int main()
{
    int n; cin >> n;
    vector<int> v(n);
    copy_n(istream_iterator<int>(cin), n, begin(v));

    auto cnt = 0;
    // backwards
    for (auto i=n-1; i>0; --i)
    {
        if (isodd(v[i]))
        {
            v[i-1]++;
            cnt+=2;
        }
    }
    cout << (isodd(v.front()) ? "NO" : to_string(cnt));
}

Alternative solution, without if, by alepez

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int main() {
    int count = 0;
    int n; std::cin >> n;
    int l; std::cin >> l;
    while (--n) {
        int r; std::cin >> r;
        count += l & 1;
        l      = r + (l & 1);
    }
    std::cout << ((l & 1) ? "NO" : std::to_string(count * 2)) << "\n";
}

Haskell solution by alepez

1
2
3
4
5
6
7
8


main :: IO()
main = do
  _ <- getLine
  input <- getContents
  let lst = read <$> words input :: [Int]
  let fn (cnt, l) r = if (odd l) then (cnt + 2, r + 1) else (cnt, r)
  let (cnt, l) = foldl fn (0, 0) lst
  putStrLn $ if (odd l) then "NO" else (show cnt)

Another approach by umuril_lyerood consists in iteratively calculating the distance between the odd values of the initial array. Basically, any odd value will “propagate” +1 until another odd value is found. The idea is coded in Python here below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def fairRations(B):
    pane = 0
    indice = -1
    for i, person in enumerate(B):
        if person%2!=0:
            if indice == -1:
                indice = i
            else:
                pane += i - indice
                indice = -1
    if indice != -1:
        return "NO"
    return pane * 2 # we distribute 2 loaves every time

Greedy nature and proof

The algorithm presented falls into the category of Greedy Algorithms: such algorithms construct a solution to the problem by always making a choice that looks the best at the moment. A greedy algorithm never takes back its choices, but directly constructs the final solution. For this reason, greedy algorithms are usually very efficient.

The difficulty in designing greedy algorithms is to find a greedy strategy that always produces an optimal solution to the problem. The locally optimal choices in a greedy algorithm should also be globally optimal. It is often difficult to argue that a greedy algorithm works.

We could prove the algorithm is optimal and correct (credits to HackerRank’s original editorial):

The algorithm prints NO only if no valid distribution exists

At the beginning we observed that if the initial sum of the array is odd, we can never satisfy the rule consisting in having each person with an even number of loaves. If we run our algorithm, the last element will have the same parity as the original sum of the array (because it never changes). The algorithm prints “NO” if the last element (or first - in the dual version) is odd (meaning that the original sum was odd).

The algorithm is optimal (it distributes the minimum amount of loaves)

Let’s prove the dual of the original algorithm.

There is not benefit in giving bread to the same pair of adjacent people more than once (observation: we could even map the problem from the space of “numbers” to the space of “booleans” - either even or odd - the algorithm does not change).

We prove this algorithm is optimal by induction.

Let \( i \) be the index of the last odd value in the array (meaning that all the following elements are even) - E.g.:

We have 3 cases:

such an index does not exist: the problem is already solved
\( i=0 \): the problem cannot be solved since the sum is odd (all the following elements are even)
\( i>0 \): the element at position \( i \) can become even

We have two ways to make \( arr[i] \) even:

add 1 to both \( arr[i] \) and \( arr[i+1] \), or
add 1 to both \( arr[i] \) and \( arr[i-1] \)

Our algorithm chooses the latter and, since the next odd index \( j \) is before i (\( j<i \)), it works by induction.

We can prove that choosing the former is wrong: If we give bread to \( arr[i] \) and \( arr[i+1] \) then \( arr[i+1] \) becomes odd (values following \( i \) are even). Then to make it even, we have no choice but to give bread to \( arr[i+2] \), and so on. At the end of the array we can never make the last element even! This means the choice is not correct.

math ad hoc